On the Discrimination Risk of Mean Aggregation Feature Imputation in Graphs
Authors: Arjun Subramonian
Kai-Wei Chang
Yizhou Sun
Venue: NeurIPS 2022 Accept (2022)
Keywords: imputation
fairness
graphs

Abstract: In human networks, nodes belonging to a marginalized group often have a disproportionate rate of unknown or missing features. This, in conjunction with graph structure and known feature biases, can cause graph feature imputation algorithms to predict values for unknown features that make the marginalized group's feature values more distinct from the the dominant group's feature values than they are in reality. We call this distinction the discrimination risk. We prove that a higher discrimination risk can amplify the unfairness of a machine learning model applied to the imputed data. We then formalize a general graph feature imputation framework called mean aggregation imputation and theoretically and empirically characterize graphs in which applying this framework can yield feature values with a high discrimination risk. We propose a simple algorithm to ensure mean aggregation-imputed features provably have a low discrimination risk, while minimally sacrificing reconstruction error (with respect to the imputation objective). We evaluate the fairness and accuracy of our solution on synthetic and real-world credit networks.

On the Discrimination Risk of Mean A Aggregation Feature Imputation in Graphs
Arjun Subramonian UCLA arjunsubecs ucla. edu
Kai-Wei Chang UCLA kwchangges www.. edu
Yizhou Sun UCLA
yzsunOcs. www.essuccll.oo
Abstract
In human networks, nodes belonging to marginalized group often have a dispro- portionate rate of unknown missing features. This, in conjunction with graph structure and known feature biases, can cause graph feature imputation algorithms predict values for unknown features that make the marginalized group's feature values more distinct from the the dominant group's 's feature values than they are reality. We call this distinction the discrimination risk. We prove that higher discrimination risk can amplify the unfairness of machine learning model ap- plied to the imputed data. We then formalize general graph feature imputation framework called mean aggregation imputation and theoretically and empirically characterize graphs in which applying this framework can yield feature values with high discrimination risk. We propose a simple algorithm to ensure mean aggregation-imputed features provably have low discrimination risk, while min- imally sacrificing reconstruction error (with respect to the imputation objective). We evaluate the fairness and accuracy of our solution on synthetic and credit networks.
Introduction
Machine learning (ML) methods 2 3 4 have been successfully applied to graph-structured data such social networks, product graphs, and molecules 66 7 aid in important problems like content recommendation, product recommendation, and molecular property prediction 8 10 [1]. However, many methods rely on fully-observed features for each node, which are not available for privacy reasons, consequence of exclusionary data collection practices, or due to the high expenses involved in feature annotation [12 [3]
[4]. As result, the development of algorithms to leverage graph's 's structure and known node feature values to impute unknown or missing features has emerged as an important research area [5
[3
In human networks, nodes belonging to a marginalized group (e.g., on the basis of race, gender, disability, etc.) often have disproportionate rate of unknown features compared to the dominant group because marginalized communities may be more reluctant to share their data, annotators erase their data, and they are sidelined in data collection 17
20 Furthermore, node neighborhoods are often associated with group membership 21 22 especially in homophilic graphs where nodes belonging the same group have higher likelihood of being connected 233. Homophily can be due to social stratification [24] or the limited collection of lines-links (i.e., edges between nodes
belonging to different groups) 23 7 Moreover, known feature values can tainted and proxies for
group membership [T8, 25) Hence, even if graph feature imputation algorithms do not have direct access to the group membership of node, these algorithms are influenced by unknown feature rate disparities, graph structure, and known feature values. In fact, they can predict values for unknown features that cause the the marginalized group's 's feature values to be more distinct from the dominant group's feature values than they are in reality.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

To illustrate this phenomenon, let's consider an automated candidate screening system based on the job applicant network shown in Figure [ where nodes represent applicants and edges between applicants indicate that they have similar past work experiences. Each node has one feature: the number of years that the applicant has previously worked. Furthermore, each node belongs to one of two groups, the disabled community Q or the able-bodied community ] All the nodes in R have a known feature value of years, while all the nodes in Q have unknown feature values; however, in reality, all the nodes in Q also have a feature value of 5 years. Additionally, all the nodes in Q are connected to each other but have few links (if any) to nodes in R because of systemic barriers including hiring discrimination and lack of accommodations
(27]. Consequently, after applying the graph feature imputation algorithm Feature Propagation [16], because of the disparate rates of unknown features between the groups and structure of the graph, the nodes in Q will have, on average,
feature values that are more distinct from the feature values of the nodes in R than the ground truth.
Q19
Qm
Q
Figure I: A job applicant network. After applying Feature Propagation [6),, the nodes in Q will have feature values that are more distinct from the feature values of the nodes I than the ground truth.
We call this distinction in imputed feature values between the marginalized and dominant groups the discrimination risk. In this paper, we present theoretically-jusifffi discrimination risk of imputed features. We further prove that a higher discrimination risk can amplify the unfairness of ML model applied to the imputed data, which can be especially dangerous, unethical, and illegal in high-stakes applications like automated candidate screening and loan approval (8 29 30 3T. For instance, in the automated candidate screening example, model applied to the imputed data may more easily learn to identify and reject disabled job applicants because they appear to have fewer years of work experience than bodeed applicants, thereby reinforcing systemic discrimination against the disabled community [27].
formulation of the
We also formalize general graph feature imputation framework called mean aggregation imputa- tion that encompasses common cnrfuusion-based imputation algorithms in the literature. Subsequently, we theoretically and empirically characterize graphs in which applying mean aggregation feature imputation can yield a high discrimination risk, without making any assumptions about the underlying distributions of unknown features or graph structure. To the best of our knowledge, are the first to study the effect of graph feature imputation on the fairness of models. This is challenging because must consider biases stemming from graph structure.
Furthermore, we propose a simple algorithm to ensure mean aggregation-imppun features provably have low discrimination risk, while minimally sacrificing reconstruction error (with respect to the imputation objective). We do so by viewing mean aggregation imputation through the lens of gradient descent and projecting imputed feature values onto the feasible space of feature values with low discrimination risk. We empirically evaluate the fairness and accuracy of our solution on synthetic and real-world credit networks, finding that it improves fairness without significant loss in reconstruction eтror on the synthetic datasets but doesn't 't improve fairness on the real-world datasets. We close by discussing the limitations of our solution.
Related work
Feature imputation Feature imputation algorithms leverage known feature values predict unknown feature values (and sometimes update known feature values). For example, unknown feature values may be filled as the mean of known values [16). However, more intricate feature imputation methods have been proposed in the ML, statistics, and epidemiology literature, with popular approaches including matrix completion
32
35 nearest neighbors (36 37], multiple imputation via
conditional models 38, 39 40 and causal inference [41 42 Notably, while feature imputation
may be applied data with unknown feature values prior to the data being passed to ML. model,
In reality, disability is fluid and complex identity that should not be reduced to binary 26

---

feature imputation is distinct from label prediction with missing data, wherein models work directly with unknown feature values 45
50]; we do not consider the latter paradigm in this paper. Works have extended feature imputation approaches for tabular data to incorporate
47
49
graph structure [51 52). Graph feature imputation using deep learning methods is also gaining traction [3 54 15 However, [66] proposes non-neural diffusion-based approach called Feature
Propagation that imputes graph features by minimizing the graph's 's Dirichlet energy.
Fairness of missing data and feature imputation Works have theoretically and empirically in- vestigated the impact of missing data [55] 56 19 57 58 and feature imputation on the fairness of ML models [56) [39 60, 61 30 62). These works consistently find that missing data can amplify biases, and some show that in practice, feature imputation can yield less unfair (relative to excluding missing data) but nevertheless discriminatory model outcomes. However, these works only study
Furthermore, they often adapt models to directly work with missing data rather than mitigate the unfairness of feature imputation itself. Despite the prevalence of graph feature imputation methods, to the best of our knowledge, there is no research on their influence the fairesss of models. Some works have explored fairness constraints in semi-supervised settings (64 (5), but they assume that node features are entirely available, which is not the case in feature imputation.
tabular data and do not consider biases that emerge from graph structure 20 22 63
Fair graph machine learning We focus on group fairness, which ensures model predictions exhibit some form of parity between different groups [66 [1 67 [29 68 [69]. Works have studied (amongst other fairness formulations) statistical parity, wherein a model predicts the positive outcome the same rate for different groups, and equalized odds, in which the accuracy of model predictions is equivalent across different groups 77].. In the automated candidate screening example, statistical parity would imply that all candidates have an equivalent opportunity to pass screening regardless of group membership, while equalized odds would mean that, regardless of group membership (i.e., P(2/ Q) PP[ZSS R)), candidates are classified with an equivalent accuracy by the automated screening model (i.e., P(Z S = Q) = S = Rt). When ground-truth labels are tainted (e.g., the screening system is trained with sexist hiring data), we may prefer statistical parity to equal opportunity. While our theoretical study of discrimination risk is aligned with statistical parity, we empirically explore the effect of mean aggregation imputation with lower discrimination risk on both the demographic parity and equalized odds of models. Mechanisms for improving group fairness have been categorized into pre-processing
[22], training-time (21 23 71), and post- Our work is similar to pre-processing, as we seek to lower the discrimination risk of imputed training data towards improving model faimess. There exist many works on modifying graph structure to mitigate topology-inducee biases 73 74 22
processing 72 73..
71 75 76.. However, because graph semantics (especially for large graphs) are difficult interpret, it is unclear if the solutions that these papers propose preserve the semantics of the original graph. On the other hand, our work does not modify graph structure and instead optimally transforms imputed features to have a low discrimination risk. (77) investigates the faimess of graph neural networks in the presence of limited group membership information but does not consider imputation; in contrast, our work assumes group membership is fully available but features are not.
3 Discrimination risk and model unfairness
To understand how feature imputation could amplify the unfairness of ML model, we now present a theoretically-justin
metric called the discrimination risk, which applies beyond the setting of graphs and is agnostic to model architecture and labels. (We explore discrimination risk in the context of graphs in Section 55) Suppose we have an arbitrary data distribution DD and two groups: marginalized group Q and a dominant group R. For any data instance (z,, s) ~ D. let be the d-dimensional feature values of the instance (where x; denotes the i-th entry of x), let y E y be its label, and let E {Q, Rt} be its group membership. We assume that we can observe the group membership of any data instance and that no instance can belong to both the marginalized and dominant groups.
X
Definition Diseriminattin Risk) We define the discrimination risk of D as:
(1) We now explore the relevance of discrimination risk to model unfairness. Let D' be the data distribution with ground-truth features and D be the distribution with imputed features. We will show that if Rp > RD. imputation may amplify model unfairness.
RD ()) Q] - E ((....)))D(( = R |o
3

---

To be concrete, let's again consider the example of the automated candidate screening system. Let P(S E {Q) be the distribution over the group membership of job applicants. Furthermore, let P(X' E X be the distribution over the ground-truth feature values of applicants (e.g., number of years previously worked, highest degree, etc.) In contrast, let P(x E X) be the distribution over imputed feature values of applicants. Let IP(Y E )') be the distribution over ground-truth applicant labels (e.g., whether an applicant should be hired, a screening score for an applicant, etc.) Now, let h' be a model trained on samples from D' (without direct access to S), and f be another model trained on samples from D (without direct access to S). Additionally, let IP Z E V) be the distribution over the predictions of it' instances sampled from P(X'), and let PZZ E )) be the distribution over the predictions of h on instances sampled from P(X).
We have the dependencies S + X' and S - X because disability affects the number of years previously worked by a job applicant. Additionally, S + X because S can influence the feature imputation algorithm (as illustrated in Figure[]) Furthermore, we assume that it' and h have access to the feature values of an applicant, but not the applicant's group membership, and that the association of S with Z' through Y can be fully explained by X', Thus, Z' is conditionally independent of S given X'. Similarly, we assume that the association of S with Z through can be fully explained by X, so Z is conditionally independent of S given X.
Because we are interested in how feature imputation may amplify model unfairness. we investi- gate when the statistical parity or total variation distance drv (P = Q), P RR) > drv (F(' S = Q). = R)) 778, where P(Z]S Q) is the prediction distribution con- ditioned on group-Q membership. dAv(A. B) measures the distance between two probability distributions A and B as supse= AAxx) B(x) Intuitively, drv (P = Q), P = R)) captures how much the prediction distribution of h absolutely differs between Q and R, and thus it quantifies the (statistical parity) unfairness f. We now discuss the relationships of drv (P(Z'|S = P(,P(Z R)) to (P('(5 = dTv = Q), P(X|S= R)). We begin with the following lemma from [79].
= Rt) and (S Q), P(Z S It)) to
Lemma 1 (Corollary 17 from (79) By the Data Processing Inequality, drv (P = Q('P(Z'SS = R)) S dry (P'''S = Q).
R)) and drv (P(Z)S Q),
R)) S drv(( = P( R)).
Please refer Section A. for the proof of Lemma 1. At high level, Lemma 1 states that the statistical parity unfairness of a model is upper-bounded by the statistical parity distance of the feature distributions between the groups We now use Lemma to prove the following theorem that connects drv (Pv'(( = P(Z)S R2)) to RD and drv (P(2S = P() = R)) to RDD
Theorem 1 Suppose P(X'|S Q) = (V/: P)); It) Wunn Pp) = Q)
N(Q Mq); and [X|S R) [ ER). We then get the following bounds:
(Tv( Q), R))
det En R
Amstea 12l x -tr(2' 2igg
p'
(P(((())=))))PLL = Ri) E
11-
V1
det Eg
Neuta 1977
Trmmse Aooona Pig J Pll
det Ni
where 0 C'C
S and S C S d. Please refer to Section A.2 for the proof of Theorem 1.
This result suggests that minimizing Rp can minimize the unfairness of the model h applied to the imputed data. Furthermore, it is possible that RD RD:, in which case feature imputation may amplify the unfaimesss of model. While we leverage strong generative assumptions in Theorem 1, it plausible that S Q and X' R are normally-disg dirtally-disrributed. Furthermore, mean aggregation imputation (Section 4 produces approximately normal X|S Q and X R (by the Central Limit Theorem). We additionally note that the lower bounds do not require the feature values to be normally distributed; the bounds only assume their distributions have finite covariance. Finally, for arbitrary distributions, matching even an infinite number of moments is not sufficient to bound their distance [80].
While R.p applies beyond graphs and is agnostic to model architecture and labels, in practice, is important to consider model complexity and task context. We also add that Rp risk bears resemblance to the Average Treatment Effect studied in causality [8]] Moreover, [59 proposes a metric also

---

called discrimination risk which quantifies how much the deviation of imputed feature values from the ground-trui -ound-truthht feature values differs across groups; this quantity is aligned with the equalized odds of model applied to the imputed data. In contrast, Ro simply measures how much imputed features differ across groups, enabling its computation when ground-truth feature values are not available, and is aligned with the statistical parity of model. We leave extending our definition of discrimination risk to other formulations fairness as future work 770.
Graph feature imputation
We would like to investigate the discrimination risk of graph feature imputation. Prior to doing so, we present general framework called mean aggregation imputation that encompasses common non-neural diffusion-based graph feature imputation algorithms in the literature.
Suppose we have undirected weighted homogeneous graph G (V, E). Each node has features, hence the node feature matrix X E Rxx, where N [V] (i.c., the cardinality of V). For simplicity, we assume that d = 1. The feature value is unknown for some nodes G (denoted as the set U), and known for others (denoted the set K). The feature value of each node is either known or unknown (i.e., U K = V and n K = 0). Let Xg refer to the feature values of the nodes set
S. Assume without loss of generality that X XK
Furthermore, let A RNXN denote the X
weighted adjacency matrix of G. where Ag is the nonnegative weight corresponding to the edge from node j to node i. Additionally, let As,s, denote the submatrix of A with rows belonging the
ARK AUK
AKU
nodes in set S1 and columns belonging to the nodes in S2. Let :
D is the ADu
diagonal degree matrix, i.e., D;; = Σn Ay and D Dr 0
Du
Definition 2 (Mean Aggregation Feature Imputation) Denote the feature values at iteration of mean aggregation feature imputation ((),, Furthermore, let xL) refer to the feature values of the nodes in set iteration t. Then, each iteration
Mx(++1 == () = |ī 0
TMX + [11 [) Iull
0 0 0
Mx
(2)
where M N + R is diagonal invertible map, T' E RNNN is right-stochastic matrix, and ee [0, is a regularization hyperparameter.
When d > 1, we apply mean aggregation feature imputation to each channel independently and it only works with continuous (not discrete) features. Mean aggregation encompasses common graph feature imputation methods, including Global Mean (predicts unknown feature values as the uniform mean of known feature values), Neighbor Mean (predicts unknown feature values as the degree- weighted mean of the known feature values for neighboring nodes), Feature Propagation (predicts unknown feature values that minimize the Dirichlet energy of the graph while preserving known feature values), and Graph Regularization (predicts feature values via smoothness constraint and a fitting constraint for the known features). For proofs, refer to fection[A.3 Despite Neighbor Mean, Feature Propagation, and Graph Regularization being intended for homophilic graphs (16), mean aggregation feature imputation encompasses algorithms that could perform well on heterophilic graphs as well with appropriate choice of T [16]. We also note that T cannot be A, this might cause feature values to explode over multiple iterations.
Discrimination risk of mean aggregation feature imputation
To understand how mean aggregation feature imputation may amplify the unfaimess of MI. model, we theoretically characterize graphs in which mean aggregation imputation increases the discrimination risk, without making assumptions about the underlying distributions of unknown features or graph structure.
We begin by defining new notation. In particular, we first focus on the case of a single feature (i.e., 1), and extend our analysis to the case d > 1 in Section A.5 Let X. be the feature of a node
Incorporating associations between features is promising direction of research.
5

---

Let Q denote the set of nodes that belong to the marginalized group, and R denote the set of nodes that belong the dominant group. We assume that Q U R = V and Q n R = 0. We define the discrimination risk after / iterations of mean aggregation imputation as:
R (+) = o [X R=,-((x(']]]
where the expectations are taken uniformly over the nodes in each set. Now, define X := M. Then, modified version of the discrimination risk after iterations of mean aggregation imputation is R(() == [ [__= In Theorem 2, we bound the discrimination risk R(0)
of the imputed features with respect to R(0). We bound R rather than R(() for simplicity; however, we empirically validate that the bound properties also hold for R( in Section 7 Define
( == [ and P == [x Furthermore, let g(t) denote the maximal deviation
of the feature values at iteration t, i.e., AqI E Q, [X PQ Σ ma [X -x
42 1 ((0)
and Vri E R. | P < max (t - x < o(0) Additionally, define Ts := Edes, Eoes, Tha.
Theorem 2 Let the contraction coefficient :=
Tk +
To- Bnk
[
[R]
Then, S 1, and:
(-1
max a
Σ 1=0
σ(0) 0
S R( S R2R100 +2
Σ a
((0)
1=0
27
lim (()) 1100
a <1
1 a
Please refer Section A.4 for a proof of Theorem 2. Theorem shows that the bounds the discrimination risk contract more slowly (with more iterations of mean aggregation feature imputation) with larger a. Furthermore, the upper bound on the discrimination risk is larger with larger a and may depend on the initial unknown feature values.
5.1 Analysis of Theorem 2
Theorem 2 allows for interesting interpretations of how graph properties like the rate of unknown features, group size, and graph structure affect the discrimination risk of mean aggregation imputation. Below, successively vary each property (holding the other properties constant) and investigate its impact on a, and in turn the discrimination risk. We focus on Feature Propagation [16), but our analysis may be easily extended other mean aggregation imputation algorithms. We assume for simplicity that all edges have a weight of 1.
Unknown feature rates A low unknown feature rate for both groups disparate unknown feature rates across the groups can increase a, and thus the discrimination risk of mean aggregation-
imputed features. Suppose the intra-link rate P((u,)) E Elu E Q Q)
P((u, v)
Elu E R E R) = 2 and inter-link rate P((u,)) v) E Elu E Q E R)
= P( v) E
Elu E E = Furthermore, assume equal (relative) group sizes, i.e., Q
R
Then, TR-Onu Tn-onu+RTn-en +RTnnonx = Ta-onu Egerr Eren Ter [Q1
Enegnu Eren D Aur
By decompo-
N/2
N/2
N/2
sition, Dyy = =uEo Aqu + EvER Agu Q + H
N Therefore, T [
Z. H(P(EEUJEEQ) (QIII)) N²/4
LP(c E U|C E Q). where P(u E Ulv E Q) is the unknown feature rate for group Q. Similarly, Rn
Evegnu Erer Age
(((onuixIn)
N²/1
N²/1
[R]
Ulu E R). Thus, a = | - PP E U|u E Q) - PP((c E U|v E R)). This aligns with 60
finding that imputation fairness can be influenced by the imbalance of feature missingness across groups, although 600 studies equalized odds rather than statistical parity fairness.
Group sizes Group size alone may not affect or the discrimination risk of mean augregation-immuute features. Suppose the intra-link rate P((u, v) E Flu E Q, v E Q) P((u,u)) E Flu E R, v E
R) 1/ and inter-link rate P((u, v) E Elu E Q E R) = P((u, v) Elu R. E Q)

---

Furthermore, assume equal unknown feature rates, i.e., P(u E 0 E Q) = P(u E -
Then, TR soru+9TR sO Exconu E.CR for
Excone E,cr Div Agr Dag
N. Therefore,
[Q]
QI
[Q]
= 2.
Ta TR-QNU+ōTR-gn
Exeone EEER Agr [(QQnUI(RR)
201111(RR) (R)
1R N. Similarly,
121
1Q)-N/22
1Q1-N/2
121-N/2
TQ- +on
IQ] Thus, a= R
12 1-
[1]
Graph structure A low inter-link to intra-link ratio can increase a and the discrimination risk of mean ingregation-impute features. Suppose we have equal unknown feature rates, i.e., P(u U Q) P(e E U|v E R) 2. Furthermore, assume equal (relative) group sizes, i.e..
QQ = ii = Then,
Evcgro Erer Tor Eergno Erer Dag Age Dag
N/2 EnEQ Aqu + EnER Age P(u,,v) EluEQU Q)QQ+ (((,( v) E Lilu E R2 ERUUQU Q)
N/2
N ([(((,,)) E Elu Q v E Q) + P((, v) Blu R2 U. E @Q]. Therefore, TR- +onoooo
[4]
P( PIw.:EEEEEQQQQQ)RRLLEEEEEEEE
Mo R ME RREQ 1+
N2/4
2
Ne. oje (EQ
To To- Po-Ro++BT4 - Similarly,
1 2
Thus,
PIE R..Q))) M(N.))ER)EQQ..EE)
[R]
1-
Because G is undirected,
VED.EER
P((u.v) E E P((, E E R) and v( Elu Q Q)
P((u,v) E UEE
Ultimately, our theoretical (Section 5 and empirical (Section B.5
characterizations of a and the
discrimination risk can be leveraged audit real-world graph data for structural factors that contribute to the unfairness of mean aggregation feature imputation and ML models applied to the imputed data.
6 Fairer graph feature imputation
We propose a simple and effective solution ensure mean aggregation feature imputation provably has a low discrimination risk, while minimally sacrificing reconstruction error (with respect to the imputation objective). At a high level, we want to constrain the discrimination risk every iteration
of imputation to be at most (i.e., 14 E [0, oo), R()) <).. We do this by viewing mean aggregation imputation through a gradient descent lens and projecting imputed feature values onto the feasible space of feature values with discrimination risk most at each iteration [82] We focus on single
feature i, but our algorithms can be extended to more features by applying them to each feature separately.
We begin with the case where known feature values remain fixed (i.e., B = 0). Recall the iterative algorithm for mean aggregation feature imputation when B 0:
Mx == 6(Mx(') To 0
[ 0
(M +
Mx
I
0
We see that Vt E [0, (o0), = XK. Furthermore, define := IN M -TTM. In the case of Feature Propagation, A = IN- - DD' DD (ED-1A)D-1 AAD = IN D -D is the symmetric normalized Laplacian of G [6]. We see that x((+1) (IN X
k A As discussed in (16), we X (Au + AU) as iteration of gradient descent 1) on the objective function E(x:) f/00"
can view the update x (t-1) (with step size where Xx is constant. For Feature Propagation, is the Dirichlet energy G [6.. We now present a theorem that shows how to perform mean aggregation feature imputation with a discrimination risk of at most e when the known feature values remain fixed.
- + X KUE + AxAAKK Xx.
Theorem 3 (e-Fair Imputation, 8 0) Vanilla mean aggregation feature imputation updates x((+1) x XAvvx + (urKXK 2 where 7 1. Let e-fair mean aggregation
feature imputation instead update x x((+1) = Pw Z + PBs where:
RK-6, 6, (z7(1) < RR -
4n1l [ao
ocT Rx-eS < Rk +e .P
Pw =
Rk tc, z Rx +
o c
otherwise
cec
0,
otherwise

---

RK= =
X
Σ (EQNK
X₂
R
[Q]
KERNK
CE R U1
T
7
(
1
E PERNU
R
QEQNU
Then, assuming 0 S Amin (Avv) Amaa (Ave) < 1 (where Amin and Amaz are the minimum
and maximum eigenvalues, respectively): 1) unique optimal (with respect to é) feasible solution
Xi exists; 2) for fixed step size Y Amaz (A e-fair imputation converges as || (1 to X
(0) 1 <
Aman Amin(Auu) (Auu) Amax(Aur)
Xi [1: 3) for fixed step size y S Amax (Aou) f-fair imputation converges
Please refer Section A.6 for a proof of Theorem 3. The convergence of our solution to the unique optimal (with respect to E) feasible solution implies that our solution provably has a discrimination risk of at most e while minimally sacrificing reconstruction error (with respect to the objective). Furthermore, because our solution simply interleaves projections into the mean aggregation imputation framework, it preserves the framework's speed and scalability [[6]. We similarly have a solution when 3 > 0 (i.e., when the known node feature values do not remain fixed) which we present in Section A.7 Choosing e, due to its uninterpretable nature, can be difficult in practice; we encourage work on making more intelligible.
7
Experimental results and discussion
We empirically evaluate the fairness and reconstruction error of our solution on various mean aggregation feature imputation algorithms and synthetic and real-world datasets. We find that while our solution yields improved fairness without a significant loss in reconstruction error on the synthetic datasets, there is not improvement in faimess on the real-world datasets. All our code may be found in the supplementary material.
Datasets We construct undirected two-block synthetic networks (SBM) using StochsttccBlocckooelleeett
from PyTorch Geometric 83 (where one block corre- sponds to the marginalized group Q and the other block to the dominant group R) with various (relative) group sizes and inter- and intra-link rates (more information in Section [B.I]. SBM does not have a corresponding task, i.e., the nodes do not have labels. We also use the real-world Credit defaulter and German credit networks from 29 (there exist limited "natively" graph real-world datasets with sensitive attributes available). The Credit defaulter network consists of 30,000 nodes representing individuals, with edges between them indicating similar spending and payment patterns. The corresponding task is to predict whether an individual will default on their credit card payment or not, and the groups are those 25 years old or younger and those above the age of 25 (more information in Section B.I). The German credit network comprises 1,000 nodes representing clients in a German bank who are connected if they have similar credit accounts. The corresponding task to predict whether client has good or bad credit risk, and the groups are men and women (more information in Section B.1 We refrain from using the Recidivism graph so as not to support the development of carceral technology 85
from 29
Protocols and performance evaluation By default, none of the datasets contain unknown or missing features. Despite the real-world prevalence of missing features, most publicly-availant graph datasets inherently do not have missing node features because current graph ML techniques predominantly rely on fully-observable features. Hence, similarly [16], to simulate diverse scenarios with unknown features, for each group, we independently at random mark node feature values as unknown with a different probability. Nodes, even within the same group. may have different unknown features. In this way, we simulate missing completely at random (MCAR) and missing at random (MAR) on our data. We experiment with all 25 combinations of unknown feature rates of {0.1, 0.3, 0.5, 0.7, 0.9) for the groups. We choose this scheme to study the effect of disparate unknown feature rates across the groups, which reflects the real world [17 [8 19 20). Empirically characterizing the real-world distributions of node feature missingness requires further study. We also encourage empirical work on other unknown feature schemes, including missingness based on node degree or marking all or none of the features for each node unknown.
In reality, gender is neither binary nor static, and treating it as such can produce harms
84
8

---

To impute unknown features, we use the vanilla mean aggregation imputation algorithms overviewed in Section Global Mean (GM), Neighbor Mean (NM), Feature Propagation (FP), and Graph Regularization (GR) (with 3 = 0.25), and their f-iair counterparts (for E {0.0, 0.025, 0.05)). For models, we use a linear classifier (linear), two-layer MLP (mlp), and two-layer Graph Convolutional Network (gen) (2 (more information in Section B.3). We train all models on the imputed data, but validate and test on fully-observed data. Because there are no previous works (to the best of our knowledge) that directly address the unfairness of graph feature imputation, we do not have baselines against which to compare.
To evaluate imputed features for SBM, since we don't 't have labels, we employ relative reconstruction error RE [16). For the weal-world datasets, we consider the test accuracy (Acc) of models applied to the imputed data. To evaluate group fairness, we compute the discrimination risk (DR) of the imputed data. For SBM, we also train models on the imputed data to predict group membership and calculate the test accuracy of the models on identifying group membership (which we refer to as MT)
[66 (1]. of the models, defined as [PZ = 1|5 Q) -PZ 1|8 R)] (78), and test equalized odds (EO), defined as [P = 1|s = Q, Y=
To evaluate group fairness for the real-world datasets, we use the test statistical parity (SP)
R, = 87], Please refer to Section B.4 for more details on the metrics. For all metrics, we report the mean and standard error over 5 runs using different random seeds. On each run, a new dataset (in the case of SBM) is generated, new splits created, and new model is trained.
Q1. Does the contraction coefficient align with the discrimination risk of mean aggregation imputation across graphs with different properties? Figures 2 12 in the Appendix show that for SBM, discrimination risk and a generally have a strong positive association over unknown feature rates, group sizes, and inter-link rate to intra-link rate ratios, which substantiates Theorem 2. This association is weaker for Global Mean and Neighbor Mean. Refer to Section B.5 for more details.
Q2. Does e-fair mean aggregation imputation (compared to regular mean aggregation imputa- tion) improve the group fairness of a model applied the imputed data? Table shows that, for SBM, e-fair mean aggregation imputation achieves comparable reconstruction error to its vanilla counterpart while greatly reducing the discrimination risk and test group membership identification accuracy for all models. As expected, we see that the discrimination risk of e-fair imputation is at most 6, and discrimination risk and test group membership identification accuracy are positively associated, which substantiates Theorem 1. Furthermore, the reconstruction error for c-fair FP and GR (which leverage graph structure and are thus more susceptible to graph structural bias) are much lower than that of the naïve e-fair GM (which does not consider graph structure), but fair FP and GR reduce the discrimination risk and test group membership identification accuracy for all models to similar levels as fair GM. However, the test group membership identification accuracy generally decreases less as e decreases for mdp and gen than it does for linear, which suggests that minimizing the discrimination risk of imputed features is more effective removing linearly-encodde group membership information than non- lincarl encoded information. Furthermore, e-fair feature imputation does not guard against group membership information that gen learns via graph structure during training. We have similar findings when averaging over different relative group sizes (refer to Table 3 and combinations of inter- and intra-link rates (refer to Table
In contrast, Tables 2 and 6 (in the Appendix) show that, for the real-world datasets, regular mean aggregation imputation and its e-fair counterpart yield comparable test accuracy and statistical parity fairness for all models. In the case of Credit defaulter, our solution even appears to exacerbate the unfairness of gen. We find similar results for equalized odds, as shown in Tables (5) and 7 Notably, we were unable to reproduce similar unfairness results to those in [29), even when all features are known. More deeply understanding why our method does not work on the real-world datasets is an important and interesting future work; we would like to analyze the modularity of the real-world networks, as well as the distribution of node degrees, labels, and features across groups to diagnose sources of failure.
8 Conclusion
We prove that a higher discrimination risk can amplify the unfairness of a ML model applied to imputed data. We formalize a general graph feature imputation framework called mean aggregation imputation and theoretically and empirically characterize graphs which applying the framework can yield high discrimination risk. We propose simple and effective solution to ensure mean
9

---

Table I: Reconstruction error (RE), discrimination risk (DR), and test group membership identi- fication accuracy (MT) of all models averaged over all 25 combinations of unknown feature rates of {0.1, 0.3, 0.5, 0.7, 0.9} for each group in SBM. We use 0.5 relative group sizes and 0.5 inter- and intra-link rates.
Method
RE
DR 4
Mitinoor +
MImly
MI J
O-Fair GM
1.21 = 0.021
0
0.602 + 0.098
0.669 + 0.019
0.504 + 0.038
0.025-Fair GM
1.204 = 0.021
0.021 0.002
0.72 + 0.087
0.683 + 0.01
0.551 = 0.069
0.05-Fair GM
0.02
0.034 0.005
0.736 + 0.037
0.69 0.014
0.535 0.058
Regular GM
1=
0.051 + 0.015
0.817 = 0.02
1817=00001
0.651 0.089
O-Fair NM
1.19 = 0.02
0++
0.599 + 0.094
0.686 + 0.021
0.507 + 0.04
0.025-Fair NM
L.88 0.02
0.02 - 0.002
0.72 = 0.084
0.706 + 0.013
0.552 0.059
0.05-Fair NM
1.175 = 0.019
0.033 0.004
0.734 0.037
0.706 0.02
0.539 0.052
Regular NM
0.977 = 0.002
0.014 0.048
0.828 0.021
0.818 0.013
0.631 0.094
O-Fair FP
1,184 0.020
0
0.6 0.096
0.702 + 0.02
0.505 + 0.034
0.025-Fair FP
1.176 = 0.020
0.018 = 0.003
0.724 0.014
0.562 0.058
0.05-Fair FP
1.169 0.019
0.025 0.006
0.03
0.723 + 0.018
0.531 0.058
Regular FP
0.977 = 0.003
0.028 0.009
0.814 0.023
0.817 0.012
0,612 = 0.079
O-Fair GR
1.006 = 0.004
0+0
0.588 + 0.093
0.713 + 0.022
0.511 + 0.039
0.025-Fair GR
1.005 0.004
0.023 + 0.002
0.757 = 0.055
0.741 + 0.012
0.577 0.078
0.05-Fair GR
1.003 0.004
0.039
0.006
0.772 + 0.027
0.744 + 0.016
0.538 0.066
Regular GR
0.977 = 0.003
0.021 0.007
0.814 = 0.024
0.821 + 0.01
0.604 0.08
Table 2: Test accuracy (Acc) and statistical parity (SP) of all models averaged over all 25 combina- tions of unknown feature rates of {0.1, 0.3, 0.5, 0.7, for each group in German credit
Method
AcCitaso 1
Acc
Acc.en 1
SP iinear
SP.igg
SP gem 4
0.0-Fair GM
0.700
0.006
0.707 + 0.003
0.699 0.002
0.051 0.016
0.028 + 0.004
0.011 + 0.01
0.025 Fair GM
0.705
0.003
0.707 + 0.003
0.698 0.002
0.044 + 0.012
0.028 + 0.007
0.02 + 0.026
0.05-Fair GM
0.704
= 0.007
0.708 0.004
0.697 + 0.002
0.034 0.009
0.029 + 0.003
0.013 = 0.00G
Regular GM
0.701
0.002
0.708 + 0.004
0.699 0.001
0.043 0.01
0.025 + 0.005
0.006 0.005
0.0-Fair NM
0.699 0.005
0.706 1 0.003
0.697 0.003
0.053 0.015
0.033 + 0.007
0.007 0.006
0.025-Fair NM
0.006
0.706 + 0.003
0.697 + 0.002
0.041 0.009
0.037 + 0.007
0.015 0.013
0.05-Fair NM
0.7 0.006
0.706 - 0.003
0.697 0.002
0.046
0.033 + 0.005
0,01 101=000 0.003
Regular NM
0.7 0.003
0.708 + 0.001
0.698 + 0.001
0.011
0.034 0.007
0.016 0.00T
0.0-Fair FP
0.694
0.021
0.713 + 0.011
0.704 0.007
0.012 0.012
0.025 + 0.025
0.019 0.039
0.025-Fair FP
0.708 = 0.012
0.706 + 0.012
0.689 + 0.027
0.024
0.026 + 0.026
0.026 = 0.057
0.U5-Fair
0.702 0.03
0.706 0.011
0.708 0.046
0.01 0.078
0.026
Regular FP
0.7 : 0.024
0.708 + 0.012
0.698 + 0.01
0.063 + 0.069
0.03 + 0.02
0.007 + 0.01
O.D- GR
0.698 = 0.005
0.703 + 0.004
0.608 + 0.001
+
0.021 + 0.003
0.006 = 0.007
0.025-Fair GR
0.702 = 0.004
0.702 : 0.002
0.7 = 0.001
0.041 +
0.025 + 0.002
0.008 + 0.01
0.05-Fair GR
0.699 0.001
0.703
1 0.003
0,699 + 0.003
0.00
0.021 1 0.004
0.005 0.005
Regular GR
0.697 0.003
0.703 + 0.003
0.7 0.001
0.038 + 0.017
0,027 + 0.005
0.01 + 0.009
aggregation-impuut features provably have a low discrimination risk, while minimally sacrificing reconstruction error (with respect to the imputation objective).
Our analysis and solution, like many fair MI. algorithms, assume that groups are discrete and that group membership is known and static, which is not true in reality [82 84 26). Furthermore, we don't 't consider fairness the intersections of different groups [88 89 or operationaliizatons of fairness beyond the parity of two non-overlapping groups [90). Furthermore, while fairness is often framed as sufficient for the creation of ethical systems, this is often not the case. For instance, c-fair mean aggregation imputation may be used to train a "fairer" model that diversifies news recommendations to social media users 77, but this model could recommend hostile or intolerant news sources to LGBTQIA+ users and cause psychological harm 82).
Acknowledgments and Disclosure of Funding
This work was partially supported by NSF III- (I-1775119, NSF 1937599, NSF 1927554, NSF 2119643, Okawa Foundation Grant, Amazon Research Awards, Cisco research grant USA000EP280889, Sloan Research Fellow, Picsart Gifts, and Snapchat Gifts.
10

---

References
[1] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfar- dini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80, 2009.
[2] Thomas N. Kipf and Max Welling, Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of the 5th International Conference on Learning Representations, ICLR 17, 2017.
[3] William L.. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. Proceedings of the 31 International Conference on Neural Information Processing Systems, NIPS' 17, page 1025-1035, Red Hook, NY, USA, 2017. Curran Associates Inc.
[4] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio', and Yoshua Bengio. Graph attention networks. ArXiv, abs/1710. 10903, 2018.
[5] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. ArXiv, abs/ abss//997.0491,, 2020.
[6] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. ArXiv, 0bbs22005.00683 2020.
[7] Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. On dyadic fairness: Exploring and mitigating bias in graph connections. In International Conference Learning Representations, 2021.
[8] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation, 2019.
[9] Shiwen Wu, Wentao Zhang, Fei Sun, and Bin Cui. Graph neural networks in recommender systems: A survey. ArXiv, abs/2011.02266 2020.
[10] Shichang Zhang, Ziniu Hu, Arjun Subramonian, and Yizhou Sun. Motif-driven contrastive learning of graph representations, 2021.
[11] Oliver Wieder, Stefan Kohlbacher, Mélaine Kuenemann, Arthur Garon, Pierre Ducrot, Thomas Seidel, and Thierry Langer. compact review of molecular property prediction with graph neural networks. Drug Discovery Today: Technologies, 37:1-12, 2020.
[12] Jeffrey M. Wooldridge. Inverse probability weighted estimation for general missing data problems. Journal of Econometrics, 141(2):281-1301) 2007.
[13] Jonathan A. C. Sterne, Ian R. White, John B. Carlin, Michael Spratt, Patrick Royston, Michael G. Kenward, Angela M. Wood, and James R. Carpenter. Multiple imputation for missing data in epidemiological and clinical research: potential and pitfalls. The BMJ, 338, 2009.
[14] Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang. and Ed Chi. Fairness without demographics through adversarially reweighted learning. In Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 728-740. Curran Associates, Inc., 2020.
[15] Indro Spinelli, Simone Scardapane, and Aurelio Uncini. Missing data imputation with penrsarialll-trriine graph convolutional networks. Neural networks: the official journal of the International Neural Network Society, 129:249-260 2020.
[16] Emanuele Rossi, Henry Kenlay, Maria Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael Bronstein. On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features, 2021.
[17] Solon Barocas and Andrew Selbst. Big data's disparate impact. Calif. Rev. 104:671, 2016.

---

[18] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairmlbook.org. 2019. http://wwe
fairmlbook http:://aa..aaarrabboo.. org
[19] Fernando Martinez-Plumed, C. Ferri, David Nieves, and José Hernández-Orallo. Missing the missing values: The ugly duckling of fairness machine learning. International Journal of Intelligent Systems, 36:3217-3258, 2021.
[20] Dana Pessach and Erez Shmueli. A review on fairness in machine learning. ACM Comput. Surv., 55(3), feb 2022.
[21] John Palowitch and Bryan Perozzi. Monet: Debiasing graph embeddings via the metadata- orthogonal training unit. ArXiv, abs/1909. 11793, 2019.
[22] Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. Edits: Modeling and mitigating data bias for graph neural networks. In Proceedings of the ACM Web Conference 2022, WWW
'22, page 1259-1269, New York, NY, USA, 2022. Association for Computing Machinery.
[23] Donald Loveland, Jiayi Pan, Aaresh Farrokh Bhathena, and Yiyang Lu. Fairedit: Preserving fairness in graph neural networks through greedy graph editing. ArXiv, abs/2201.03681, 2022.
[24] Bas Hofstra, Rense Corten, Frank van Tubergen, and Nicole B. Ellison. Sources of segrega- tion in social networks: A novel approach using facebook. American Sociological Review, 82(3):625-656, 2017.
[25] Tianlu Wang, Jieyu Zhao, Mark Yatskar, Kai-We Wei Chang, and Vicente Ordonez. Balanced datasets are not enough: Estimating and mitigating gender bias in deep image representations. In ICCV, 2019.
[26] Sharon N. Barnartt. Disability as a fluid state: Introduction. 2010.
[27] Mason Ameri, Lisa A. Schur, Meera Adya, F. Scott Bentley, Patrick F. McKay, and Douglas L. Kruse. The disability employment puzzle: field experiment on employer hiring behavior. ILR Review, 7 71:329-364, 2015.
[28] Ifeoma Ajunwa. An auditing imperative for automated hiring. DecisionSciRN: Recruiting & Hiring (Sub-Topic), 2019.
[29] Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a unified framework for fair and stable graph representation learning. In UAI, 2021.
[30] Christo Wilson, Avijit Ghosh, Shan Jiang, Alan Mislove, Lewis Baker, Janelle Szary, Kelly Trindel, and Frida Polli. Building and auditing fair algorithms: A case study in candidate screening. In Proceedings of the 2021 ACM Conference on Fairness, Accountabiliry, and Trans- parency, FAceT 21, page 666 677, New York, NY, USA, 2021. Association for Computing Machinery.
[31] Elizabeth Anne Watkins, Michael Mckenna, and Jiahao Chen. The four-fifths rule is disparate impact: a woeful tale of epistemic trespassing in algorithmic faimesss. ArXiv, abs/2202.09519, 2022.
[32] Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9:717-772, 2009.
[33] Diederik P. Kingma and Max Welling, Auto-encoding variational bayes. CoRR, abs/1312.6114 2014.
[34] Trevor Hastie, Rahul Mazumder, Jason D. Lee, and Reza Zadeh. Matrix completion and low-rank svd via fast alternating least squares. J. Much. Learn. Res., 16(1):3367-3402, jan 2015.
[35] Jinsung Yoon, James Jordon, and Mihaela van der Schaar. Gain: Missing data imputation using generative adversarial nets. ArXiv, abs/1806.022 029200,0222......00 2018.
12

---

[36] LAWRENCE R. LANDERMAN, KENNETH C. LAND, and CARL F. PIEPER. An empirical evaluation of the predictive mean matching method for imputing missing values. Sociological Methods & Research, 16333,333,, 1997.
[37] Olga Troyanskaya, Michael Cantor, Gavin Sherlock, Pat Brown, Trevor Hastie, Robert Tib- shirani, David Botstein, and Russ B. Altman. Missing value estimation methods for DNA microarrays. Bioinformatics, 17(6):520-5255 06 2001.
[38] Trivellore E. Raghunathan. James M. Lepkowski. John Van Hoewyk, and Peter W. Solenberger. A multivariate technique for multiply imputing missing values using a sequence of regression models. Survey Methodology, 27:85-95, 2001.
[39] Daniel J. Stekhoven and Peter Bühlmann. MissForest- non- pon-aaaattttn missing value imputa- tion for mixed-type data. Bioinformatics, 28(1):112-1188 10 2011.
[40] B. Jafrasteh, Daniel Hern' andezz-Lbato,, Sim on Pedro Lubi ann- and Isabel Benavente- Ferne, Gaussian processes for missing value imputation. ArXiv, has/2204.046444 2022.
[41] Ilya Shpitser, Karthika Mohan, and Judea Pearl. Missing data as a causal and probabilistic problem. In UAI, 2015.
[42] Peng Ding and Fan Li. Causal inference: A missing data perspective. arXiv: Methodology, 2017.
[43] Zoubin Ghahramani and Michael Jordan. Supervised learning from incomplete data via an em approach. In J. Cowan, G. Tesauro, and J. Alspector, editors, Advances in Neural Information Processing Systems, volume 6. Morgan- Kaufmann, 1993.
[44] David Williams, X. Liao, Ya Xue, and Lawrence Carin. Incomplete-dat data classification using logistic regression. Proceedings of the 22nd international conference on Machine learning. 2005,
[45] Kristiaan Pelckmans, Jos De Brabanter, Johan A. K. Suykens, and Bart De Moor. Handling missing values in support vector machine classifiers. Neural networks: ; the official journal of the International Neural Network Society, 18 5-6:684 92, 2005.
[46] Jing Xia, Shengyu Zhang, Guolong Cai, Li Li, Qing Pan, Jing Yan, and Gangmin Ning. Adjusted weight voting algorithm for random forests in handling missing values. Pattern Recognit., 69:52-60, 2017.
[47] Marek Smieja, Lukasz Struski, Jacek Tabor, Bartosz Zieliński, and Przemystaw Spurek Processing of missing data by neural networks. In NeurlPS, 2018.
[48] Jiaxuan You, Xiaobai Ma, Daisy Yi Ding, Mykel Kochenderfer, and Jure Leskovec. Handling missing data with graph representation learning. ArXiv, abs/2010.16118 2020.
[49] Hibiki Taguchi, Xin Liu, and Tsuyoshi Murata. Graph convolutional networks for graphs containing missing features. Future Gener. Comput. Syst., 117:155- 168, 2021.
[50] Bo Jiang and Ziyan Zhang. Incomplete graph representation and learning via partial graph neural networks, 2020.
[51] Mark Huisman. Imputation of missing network data: Some simple procedures. J. Soc. Struct., 10, 2009.
[52] Vassilis Kalofolias, Xavier Bresson, Michael M. Bronstein, and Pierre Vandergheynst. Matrix completion on graphs. ArXiv, abs/1408. 1717, 2014.
[53] Rianne van den Berg, Thomas Kipf, and Max Welling. Graph convolutional matrix completion. ArXiv, hhs//706.02266 2017.
[54] Jason S. Hartford, Devon R. Graham, Kevin Leyton-Browe and Siamak Ravanbakhsh. Deep models of interactions across sets. In ICML, 2018.
13

---

[55] Betsy Anne Williams, Catherine F, Brooks, and Yotam Shmargad. How Algorithms Discrimi- nate Based on Data They Lack: Challenges, Solutions, and Policy Implications. Journal of Information Policy, 8(1):78-115, 03 2018.
[56] Christian Fricke. Missing Fairness: The Discriminatory Effect of Missing Values in Datasets on Fairness in Machine Learning. Master's 's thesis, Aalto University. School of Science, 2020.
[57] Naman Goel, Alfonso Amayuelas, Amit Deshpande, and Ajay Sharma. The importance of mod- eling data missingness in algorithmic faimess: A causal perspective. ArXiv, abs/2012.11448. 2021.
[58] Yiliang Zhang and Qi Long, Assessing fairesss in the presence of missing data. In M. Ranzato, A. Beygelzimer, Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 16007-16019. Curran Associates, Inc., 2021.
[59] Haewon Jeong, Hao Wang, and Flávio du Pin Calmon. Fairness without imputation: A decision tree approach for fair prediction with missing values. ArXiv, abs/2 11122100911441 2021.
[60] Yiliang Zhang and Qi Long. Fairness in missing data imputation, 2021.
[61] Hadis Anahideh, Nazanin Nezami, and Denisa Gándara. Auditing fairness and imputation impact in predictive analytics for higher education. ArXiv, abs/2 109.0790, 2021.
[62] Manvi Choudhary, Charlotte Laclau, and Christine Largeron. A survey on faimess for machine learning on graphs. ArXiv, 0bs/2205500539 2022.
[63] Wenbin Zhang, Jeremy C. Weiss, Shuigeng Zhou, and Toby Walsh. Fairness amidst non-iid graph data: A literature review. ArXiv, abs/2202.07170,, 2022.
[64] Tao Zhang, Tianqing Zhu, Mengde Han, Jing Li, Wanlei Zhou, and Philip S. Yu. Fairness constraints in semi-supervised learning, 2020.
[65] Joymallya Chakraborty, Quang Huy Tu, Suvodeep Majumder, and Tim Menzies, Can we achieve fairness using superviid learning?, 11 2021.
[66] Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 3289-3295. International Joint Conferences on Artificial Intelligence Organization, 2019.
[67] Maarten Buyl and Tijl De Bie. DeBayes: Bayesian method for debiasing network embeddings. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1220-1229. PMLR, 13-18 Jul 2020.
[68] Jing Ma, Ruocheng Guo, Mengting Wan, Longqi Yang, Aidong Zhang, and Jundong Li. Learning fair node representations with graph counterfactual faimesss. Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining. 2022.
[69] Jian Kang. Yan Zhu, Yinglong Xia, Jiebo Luo, and Hanghang Tong. Rawlsgen: Towards rawlsian difference principle on graph convolutional network. In Proceedings of the ACM Web Conference 2022, WWW '22, page 1214-1225, New York, NY, USA, 2022. Association for Computing Machinery.
[70] Sahil Verma and Julia Rubin. Fairness definitions explained. In Proceedings of the Interna- tional Workshop on Software Fairness, FairWare '18 page 1-7, New York, NY, USA, 2018. Association for Computing Machinery.
[71] Sean Current, Yuntian He, Saket Gurukar, and Srinivas Parthasarathy. Fairmod: Fair link prediction and recommendation via graph modification. ArXiv, abs/2201.11596. 2022.
[72] Bose and William I.. Hamilton. Compositional fairness constraints for graph embeddings. In ICML, 2019.
14

---

[73] Farzan Masrour, Tyler Wilson, Heng Yan, Pang-Ning Tan, and Abdol Esfahanian. Bursting the filter bubble: Fairness-aware network link prediction. Proceedings of the AAAI Conference on Artificial Intelligence, 34(01):841-88) -848, Apr. 2020.
[74] Indro Spinelli, Simone Seardapane, Amir Hussain, and Aurelio Uncini. Biased edge dropout for enhancing fairness in graph representation learning. ArXiv, 0bs/2204.11210, 2021.
[75] Nan Wang, Lu Lin, Jundong Li, and Hongning Wang. Unbiased graph embedding with biased graph observations. In Proceedings of the ACM Web Conference 2022, WWW '22, page 1423-1433, New York, NY, USA, 2022. Association for Computing Machinery.
[76] Yanying Li, Xiuling Wang. Yue Ning, and Hui Wang. Fairlp: Towards fair link prediction on social network graphs. In Proceedings of the 16th International AAAI Conference on Web and Social Media, 2022.
[77] Enyan Dai and Suhang Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, WSDM '21, page 680-688, New York, NY, USA, 2021. Association for Computing Machinery.
[78] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 12, page 214-226, New York, NY, USA, 2012. Association for Computing Machinery.
[79] Han Zhao and Geoff Gordon. Inherent tradeoffss in learning fair representations. In Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[80] Bruce G. Lindsay and Prasanta Basak. Moments determine the tail of a distribution (but not much else). The American Statistician, 54:248 251, 2000.
[81] Jasjeet S. Sekhon. The neyman- rubin model of causal inference and estimation via matching methods. 2008
[82] Arjun Subramonian. On dyadic fairness: Exploring and mitigating bias in graph connections. In ICLR Blog Track, 2022. ttap://icct-blog-trackk wtw.b//oogrrrrr.gguibboooooooeee faiiii//s
[83] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with Py PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[84] Sunipa Dev. Masoud Monajatipoor, Anaelia Ovalle, Arjun Subramonian, J. M. Phillips, and Kai Wei Chang. Harms of gender exclusivity and challenges non-binary representation in language technologies. ArXiv, abs/2108. 11.22108..2..... 12084, 2021.
[85] Lelia Hampton. Black feminist musings on algorithmic oppression. Proceedings of the 2 ACM Conference on Fairness, Accountability, and Transparency, 2021.
[86] Brian Hu Zhang. Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, AIES 18, page 335-340, New York, NY, USA, 2018. Association for Computing Machinery.
[87] Moritz Hardt, Eric Price. and Nathan Srebro. Equality of opportunity in supervised learning. ArXiv, abs//610.02411 2016.
[88] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimess gerry- mandering: Auditing and learning for subgroup faireess. In ICMI., 2018.
[89] Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Sorelle A. Friedler and Christo Wilson, editors, Proceedings of the 1st Conference on Fairness, Accountability and Transparency, volume 81
of Proceedings of Machine Learning Research, pages 77-91. PMLR, 23-24 Feb 2018.
15

---

[90] Abigail Z. Jacobs and Hanna Wallach. Measurement and faimess. In Proceedings of the 2021 ACM Conference on Fairness, Accountabilityy and Transparency, FAccT '21, page 375-385, New York, NY, USA, 2021. Association for Computing Machinery.
[91]
Clément L. Canonne. A short note on an inequality between kl and 2022.
[92]
John C. Duchi. Derivations for linear algebra and optimization. 2016.
[93] Jacob Steinhardt. Lecture notes for stat260 (robust and nonparametric statistics). 2021.
[94] Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems, volume 16. MIT Press, 2004.
[95] Amir Beck. Proximal-based methods tutorial, 2021.
[96] Lieven Vandenberghe. Ece236c optimization methods for large-scale systems course notes, 2021.
[97] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[98] Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. CoRR, abs/ 1bs/,4 2015.
[99] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(56):192--1955 1958, 2014.
[100] Organizers of QueerInAI, Ashwin S, William Agnew, Hetvi Jethwani, and Arjun Subramonian. Rebuilding trust: Queer ai approach to artificial intelligence risk management, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] (We transparently discuss the limitations of theoretical results, formalizations, and experimental results throughout the paper, directly before or after they are presented.)
(c) Did you discuss any potential negative societal impacts of your work? [Yes] (We refrain from using recidivism prediction dataset and inferring identity from data for ethical reasons in Sections and B.4 and discuss potential negative societal impacts of our work in Section 8
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] (We enumerate all assumptions in the theorem statements or in the paragraphs leading up to the theorems.)
(b) Did you include complete proofs of all theoretical results? [Yes] (We do so in Section
3. If you experiments...
16

---

(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] (All experiment code and relevant dependencies and instructions are included in the supplemental material.)
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] (All training details are specified in Sections 7 B.1 B.2 and
B.3
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] (We report metrics with their mean and standard error computed over 5 runs with different random seeds, as discussed in Section 7
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] (We do so in Section B.3)
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? Yes] (We cite the original creators of all datasets, code, and libraries Sections 7 and
B and include URL.s.)
(b) Did you mention the license of the assets? [Yes] (All code and datasets are used in accordance with their license, as explained Sections B.2 and B.3)
(c) Did you include any new assets either in the supplemental material or as a URL? [Ye]] (The code for running the experiments in Sections and B are included in the supplemental material. We do not create any new datasets.)
(d) Did you discuss whether and how consent was obtained from people whose data you'l rr using/curating? [Yes] (The real-world datasets are used in accordance with their MIT license, as explained in Section B.I)
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] (We so in Section [B.I)
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
17


Reviews:
[{"review_id": "zWNhWkFjZZW", "reviewer": "Reviewer_qNJZ", "summary": "This paper provides theoretical analysis on the estimation error of fairness, in the setting where missing data is present. In particular, the authors consider the “discrimination risk” as the fairness metric. The paper also includes some numerical experiments to validate the theoretical findings.", "questions": "Please refer the Weaknesses part.", "limitations": "None", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weaknesses: 1)The authors claim that the solution they provided have a low discrimination risk (while minimally sacrificing utility) and improve the fairness of models. In addition to the fairness, the underline data distribution should be hold after imputation, which directly affect the effectiveness of the models. 2)While the theoretical results can be useful in understanding the behavior of fairness estimation under different settings, I am not sure if they will have much practical impact. 3)In Theorem 3, R_K is a scalar while Z_U is a vector or matrix, that means R_K and Z_U cannot be compared, please explain the corresponding constraint conditions in P_W and P_B. 4)There are three missing data contexts: missing completely at random (MCAR), missing at random (MAR) and missing not at random (MNAR), does the findings in this paper be adequate for all the three missing data contexts?\n\nOverall, the paper is well-written, and the contributions and limitations are clearly described. While the theoretical perspective for fairness estimation with missing data for graph data is novel, I am leaning towards reject due to concerns about practical impact, as mentioned above.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rj5ZPemwhQ", "reviewer": "Reviewer_Ne2Y", "summary": "The authors studied the effect of graph feature imputation on the fairness of models. Specifically, they defined the discrimination risk (measures how much features differ between groups) and showed that statistical parity is upper-bounded by the discrimination risk. Based on a general graph feature imputation framework that includes several existing imputation methods as examples, the authors analyzed the cases in which applying this imputation framework leads to higher discrimination risk and proposed a $\\epsilon$-fair imputation method for low discrimination risk. The proposed method empirically showed improvement on synthetic datasets but not on real-world credit datasets.", "questions": "Please see the weaknesses above.", "limitations": "Yes, the authors discussed the limitation.\n", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The authors analyzed the effect of graph feature imputation on the fairness of models, which is an important problem and often encountered in practice.\n* The authors theoretically (Theorem 2) and empirically (Appendix) investigated how the graph properties affect $\\alpha$, which helps interpret the impact of existing imputation methods on the statistical parity.\n* The authors also proposed a solution to control discrimination risk under the general mean aggregation feature imputation framework.\n\nWeaknesses:\n* Could the authors explain in which cases statistical parity is preferable to predictive parity and why they focused on statistical parity in this problem?\n* It seems to me that all the analysis is limited to two groups starting from the definition of discrimination risk. How generalizable the current results are to multiple groups?\n* It is not clear to me the impact of graph properties on the proposed $\\epsilon$-fair imputation method in Theorem 3.  \n* Empirical evidence of the effectiveness of the proposed solution is limited. \n* It would be better to shorten some long sentences for easier interpretation, such as lines 5-9. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "g-hLl76C6rh", "reviewer": "Reviewer_6GqN", "summary": "[Last minute review invitation so limited time] \n\nThis paper highlights the concern of unfair discrimination caused by imputation of missing feature values in graphs. A measure of this discrimination risk is formed, based on the difference of the expected value of the feature values between a minority / marginalized group and a dominant group. This work goes further by forming a generalised method of mean aggregation feature imputation in order to analyse the effects of imputation in theory and in practise with a number of approaches that are special cases of the generalised method, and introduce a modified form to address the discrimiation risk within an epsilon bound. They show that the theory supports their claims. Empirical evaluation on simulated stochastic block model (SBM) data also supports their cliams and their method to address the problem behaves as expected. However, on real data the results are not as expected, leading to future research to investigate.", "questions": "Does [15] do node feature imputation, I don't recall that paper discussing this?\n\nIt's not completely clear how the Mean Aggregation Feature method can encompass the Graph Regularisation, is it that T can be replaced with the weighted adjcency matrix after some normalisaiton to be a stochastic matrix, maybe good to clarfiy briefly in the main text?\n\nFor Theorem 2, is the maximal deviation the deviation from the mean of the group value or the maximum deviation between any two feature values, I believe it is the later but good to clarify in the main text?\n\nTo clarify the conclusion on connections within groups (intra) and between groups (inter), if there are more intra-connections than inter-connections the discrimintation risk is higher?\n\nNone of the example datasets have missing features; can you comment on why not as we would hope to see this problem in real world example data. Furthermore, by randomly removing features, how close to reality is this, what kind of distributions do missing features have in the real world?\n", "limitations": "The paper is good at showing the limitations, where by the experiments on real-world data did not show improvements. A hypothesis for this is put forward - that there is discrimination existing in the known labelled data and so it is not able ot improve the discrimination risk. However, this work seems to be heading in a very good direction to address this discrimination risk issue, however, the more interesting question arising is why this did not work on the real data, and can this be more deeply investigated? So why this didn't work on the real data is a very interesting question that is raised in this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\n========\nStrength. In the growing area of graph neural networks this paper highlights a potential risk of discriminating against minority / marginalized groups when imputing feature values for graph nodes.\nWeakness. Although in theory this is a genuine problem, the paper does not strongly support that this is a real-world phenomena nor that their method can address this.\n\nQuality and Clarity\n===============\nStrength. A very well written paper. Easy to follow, lots of relevant citations, well writtne, clear mathematics explained clearly.\nWeakenss. Deeper into the paper it was tricky to follow some of the claims and quite often the reader is pointed to the appendix for further details. This is okay as long as it is possible to grasp the intuition of the claim from the main text in my opinion.\n\nSignificance\n==========\nStrength. The problems with discrimination for real world applications of machine learning like credit risk is genuine and of high importance in my opinion, and very well motivated in this paper. I would even add that in my countries this type of discrimination is even illegal, like in the US they have disparate impact labour laws to protect against this type of discrimination.\nWeakness. Although it feels as though the idea of feature imputation causing this problem is logical, as explained with illustrations and supported by theory and experiments on simulated data, none of the real-world data they experimented on had missing feature values, which leads us to believe that this is not a common problem in reality, and furthermore the experiments on the real-world data were not clear that there was any improvements when trying to reduce the discrimination risk by removing feature values (to simulate missing feature values) and then using their method to impute them. Although it was commented that the author(s) believe this is likely due to the large amount of discrimination already in the known features, this was not supported by investigation, which maybe could reveal something more about this?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OWBS0n0ADwq", "reviewer": "Reviewer_QttQ", "summary": "The authors consider the problem of fairness when imputing features in a group setting where on average there is higher difference to ground truth among the marginal groups vs the dominant groups. Experiments are shown on both synthetic and real-world fairness-utility tasks.\n\n", "questions": "(A) If we do not the group information of the applicants/samples, how does the algorithm work? Do you use the group information only for the discrimination risk but not for the feature imputation step?\n\n(B) How do we use the correlated features in the imputation process since occupation/title is correlated with salary? ", "limitations": "However, most of the results on real-world datasets are not providing any of the promised lift in terms of fairness. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written with both theoretical results in main paper as well as extensive experiments. In particular, the limitations of the approach on real-world datasets is clearly highlighted.\n\nThe setting is interesting because fairness on graphs has not been theoretically studied given the practical importance of the problem. The authors propose a discrimination measure which is broadly applicable, not limited by models or graphs, and show that it closer to the statistical parity often used in fairness literature.\n\nI checked over the main Theorems and proof sketches but did not look over the supplementary in detail.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MxkIv6m9oCC", "reviewer": "Reviewer_zs22", "summary": "This paper discusses some of the problems related to fairness that can occur when a machine learning model is applied to graph data with missing values. Fairness is considered concerning two groups, a marginalized group ($Q$) and a dominant group ($R$). It seeks to derive theoretical results relating the Total Variation Distance between the conditional prediction distribution given imputed features and ground truth features with a measure the authors term the Discrimination Risk---defined to be the minimum  L1 distance between the mean (imputed) feature for marginalized and non-marginalized groups (with the minimum taken across feature dimensions). The paper then investigates feature imputation in graph data, aiming to derive an algorithm for iteratively imputing missing data while controlling the Discrimination Risk. Performance evaluation is then done on synthetic Stochastic Block Model (SBM) data and on credit datasets. \n", "questions": "-I think, in line 172 of p. 4, \"$a$\" should read \"$a_i$\".\n\n-In Lemma 1, it would appear difficult to interpret the Total Variation distance inequalities, as lefthand and righthand side quantities are defined over a different support ($Z$ (low dimensional) and $X$ (presumably high dimensional). \n", "limitations": "- One limitation is that, for a given graph imputation model, it is unclear what a reasonable baseline DR would be (a problem made more pronounced by the fact that it depends on the scale of the covariate data). Therefore, the choice of $\\epsilon$ in the algorithmic component is hard to make in practice and a function of human judgement. \n\n- Knowledge of marginal and dominant groups is required a priori. While in some situations, there may be little debate about this fact, in other situations, the question of who is in fact marginalized can be politically contentious or simply difficult to make. ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The overall idea for this paper is strong. Missing data is certainly a prevalent problem and to my knowledge there is not much work connecting the imputation and fairness in the graph context. Therefore, solutions to the problem identified by the paper would in my view be valuable. The evaluation procotol is reasonably strong, and the theoretical results intriguing. \n\nNevertheless, there are several things that I currently perceive to be weaknesses with the paper. \n\nThe notion of Discrimination Risk (DR) is central to the paper. As written, the theoretical results related to DR depend on covariates being bounded/continuous. Moreover, it is unclear whether the DR value is used for mathematical convenience or because it captures a true quantity of interest related to fairness. For example, the DR value is defined in Equation 1 to be the minimum L1 distance across dimensions between the mean (imputed) feature for marginalized and non-marginalized. Adding additional random covariates would bring this measure to 0 (i.e., the expected value of the minimum of a set of random variables scales with n or in this case d). Also, if there is one dimension where marginalized and dominant groups are equal in the covariate space, the measure is also 0. It could be the authors meant to write max instead of min, as in Equation 3, an apparently different definition of DR is introduced. (One other point is that the DR measure assumes the existence of exclusive marginalized and dominant groups viewed asymetrically, conversely, the absolute value in Equation 1 will penalize deviations symmetrically.) \n\nThe confusion related to DR is also related to a more general point about the paper presentation. Parts of the paper are hard to follow. Some of this would be improved with a more consistent emphasis in the paper. The paper starts off with a fairly clear introduction regarding graph imputation, but third section makes no real mention of graph data; graphs are then re-introduced in the fourth section. Some of the claims in the abstract are also somewhat too strong or potentially misleading in my view (especially the \"minimally sacrificing utility\" point; this isn't false, but the \"utility\" meant here is not related to social utility as sometimes understood, but to the specific objective function in line 265 of p. 7). \n\nRegarding the simulation design -- First, the two real-world datasets are not \"natively\" actually network or graph data. Edges between units simply represent unit-level similarity (i.e. do units share spending patterns?; do units have similar credit accounts?). This limits our ability to access performance in actual network data where relations between units are not just deterministic functions of the pairwise unit-level covariates.\n\nSecond, the critical contribution that the papers seeks to make is to devise strategies for missing data imputation in graph data. Therefore, it would seem appropriate to have the missingness mechanism be correlated with graph specific quantities (e.g., non-central nodes are more likely to have missingness or something of the sort). \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IbO3bWwt9Zs", "reviewer": "Reviewer_dRAB", "summary": "This paper studies the effect of mean aggregation feature imputation in graphs over marginalized and dominant groups. The main conclusion is that mean aggregation imputation may harm fairness between those two groups. To alleviate this unfairness, the paper proposes a corrected graph feature imputation algorithm that considers the feature unfairness in their updates.", "questions": "1. The contraction coefficient alpha is hard to interpret in Theorem 2. As explained in line 209, T is a right-stochastic matrix without an explicit form. So it is hard to judge the scale of alpha.\n2. Theorem 2 can be explained as the discrimination risk is upper-bounded by the initial difference between two instances either within the marginalized group or within the dominant group. That seems not to be a good sign since diversity may show up within each group. Does that mean the diversity among data also harms fairness?\n3. In Theorem 3 it seems that epsilon-fair computation does not affect the convergence rate of X_U, since the convergence rate relies on eigenvalues of Delta_{UU} only, and the graph topology is not modified. Does that mean epsilon-fair computation can do as well as vanilla mean aggregation feature imputation given enough data?", "limitations": "This paper studies mean aggregation feature imputation and its harm to fairness. Several things are not covered. First, the analysis of the classification model (X->Y) seems over-simplified. Second, the paper considers the simplest case that the dataset only consists of two discretized, non-overlapping groups.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. This paper articulated the source of unfairness can propagate from mean aggregation feature imputation to discrimination in model predictions. The propagation effect can break into two parts. First, the discrimination can propagate from input to output (Theorem 1). Second, the iterated mean aggregation feature imputation algorithm can exaggerate the input discrimination (Theorem 2).\n2. The paper proposes an algorithm to compensate for the discrimination across groups in each iteration. The algorithm can provably satisfy epsilon-fairness.\n3. Empirical result shows a clear tradeoff between utility and fairness, which is expected.\n\nWeaknesses: \n1. It is hard to get the intuition behind the fair graph feature imputation algorithm. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept