Fair Attribute Completion on Graph with Missing Attributes

Recent work promotes fairness in graph-based machine learning (Bose & Hamilton, 2019; Rahman et al., 2019; Dai & Wang, 2021; Wang et al., 2022). They can be roughly divided into three categories, i.e., the pre-processing methods, in-processing methods, and post-processing methods.

The pre-processing methods are applied before training downstream tasks by modifying training data. For instance, Fairwalk (Rahman et al., 2019) improves the sampling procedure of node2vec (Grover & Leskovec, 2016). Our FairAC framework can be viewed as a pre-processing method, as it seeks to complete node attributes and use them as input of graph neural networks. However, our problem is much harder than existing problems, because the attributes of some nodes in the graph are entirely missing, including both the sensitive ones and non-sensitive ones. Given an input graph with missing attributes, FairAC generates fair and complete feature embeddings and thus can be applied to many downstream tasks, such as node classification, link prediction (Liben-Nowell & Kleinberg, 2007; Taskar et al., 2003), PageRank (Haveliwala, 2003), etc. Graph learning models trained on the refined feature embeddings would make fair predictions in downstream tasks.

There are plenty of fair graph learning methods as in-processing solutions. Some work focus on dealing with unfairness issues on graphs with complete features. For example, GEAR (Ma et al., 2022) mitigates graph unfairness by counterfactual graph augmentation and an adversarial learning method to learn sensitive-invariant embeddings. However, in order to generate counterfactual subgraphs, they need precise and entire features for every node. In other words, it cannot work well if it encounters a graph with full missing nodes since it cannot generate counterfactual subgraph based on a blank node. But we can deal with the situation. The most related work is FairGNN (Dai & Wang, 2021). Different from the majority of problem settings on graph fairness. It learns fair GNNs for node classification in a graph where only a limited number of nodes are provided with sensitive attributes. FairGNN adopts a sensitive classifier to predict the missing sensitive labels. After that, it employs a classic adversarial model to mitigate unfairness.Specifically, a sensitive discriminator aims to predict the known or estimated sensitive attributes, while a GNN model tries to fool the sensitive discriminator and meanwhile predicts node labels. However, it cannot predict sensitive information if a node misses all features in the first place and thus will fail to achieve its final goal. Our FairAC can get rid of the problem because we recover the node embeddings from their neighbors. FairAC learns attention between neighbors according to existing full attribute nodes, so we can recover the node embeddings for missing nodes from their neighbors by aggregating the embeddings of neighbors. With the help of the adversarial learning method, it can also remove sensitive information. In addition to attribute completion, we have also designed novel de-biasing strategies to mitigate feature unfairness and topological unfairness.

The problem of missing attributes is ubiquitous in reality. Several methods (Liao et al., 2016; You et al., 2020; Chen et al., 2020; He et al., 2022; Jin et al., 2021; 2022; Tu et al., 2022; Taguchi et al., 2021) have been proposed to address this problem. GRAPE (You et al., 2020) tackles the problem of missing attributes in tabular data using a graph-based approach. SAT (Chen et al., 2020) assumes that the topology representation and attributes share a common latent space, and thus the missing attributes can be recovered by aligning the paired latent space. He et al. (2022) and Jin et al. (2021) extend such problem settings to heterogeneous graphs. HGNN-AC (Jin et al., 2021) is an end-to-end model, which does not recover the original attributes but generates attribute representations that have sufficient information for the final prediction task. It is worth noting that existing methods on graph attribute completion only focus on the attribute completion accuracy or performance of downstream tasks, but none of them takes fairness into consideration. Instead, our work pays attention to the unfairness issue in graph learning, and we aim to generate fair feature embeddings for each node by attribute completion, which contain the majority of information inherited from original attributes but disentangle the sensitive information.

Let $\mathcal{G=(V,E,X)}$ denote an undirected graph, where $\mathcal{V}=\{v_{1},v_{2},...,v_{N}\}$ is the set of $N$ nodes, $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of undirected edges in the graph, $\mathcal{X}\in\mathbb{R}^{N\times D}$ is the node attribute matrix, and $D$ is the dimension of attributes. $\mathcal{A}\in\mathbb{R}^{N\times N}$ is the adjacency matrix of the graph $\mathcal{G}$, where $\mathcal{A}_{ij}=1$ if nodes $v_{i}$ and $v_{j}$ are connected; otherwise, $\mathcal{A}_{ij}=0$. In addition, $\mathcal{S}=\{s_{1},s_{2},...,s_{N}\}$ denotes a set of sensitive attributes (e.g., age or gender) of $N$ nodes, and $\mathcal{Y}=\{y_{1},y_{2},...,y_{N}\}$ denotes the node labels. The goal of fair graph learning is to make fair predictions of node labels with respect to the sensitive attribute, which is usually measured by certain fairness notations like statistical parity (Dwork et al., 2012) and equal opportunity (Hardt et al., 2016). Statistical Parity and Equal Opportunity are two group fairness definitions. Their detailed formulations are presented below. The label $y$ denotes the ground-truth node label, and the sensitive attribute $s$ indicates one’s sensitive group. For example, for binary node classification task, y only has two labels. Here we consider two sensitive groups, i.e. $s\in\{0,1\}$.

• •

  Statistical Parity (Dwork et al., 2012). It refers to the equal acceptance rate, which can be formulated as:

  $$P(\hat{y}|s=0)=P(\hat{y}|s=1),$$

  (1)

  where $P(\cdot)$ denotes the probability that $\cdot$ occurs.

• •

  Equal Opportunity (Hardt et al., 2016). It means the probability of a node in a positive class being classified as a positive outcome should be equal for both sensitive group nodes. It mathematically requires an equal true positive rate for each subgroup.

  $$P(\hat{y}=1|y=1,s=0)=P(\hat{y}=1|y=1,s=1).$$

  (2)

In this work, we mainly focus on addressing unfairness issues on graphs with missing attributes, i.e., attributes of some nodes are totally missing. Let $\mathcal{V}^{+}$ denote the set of nodes whose attributes are available, and $\mathcal{V}^{-}$ denote the set of nodes whose attributes are missing, $\mathcal{V}=\{\mathcal{V}^{+},\mathcal{V}^{-}\}$. If $v_{i}\in\mathcal{V}^{-}$, both $\mathcal{X}_{i}$ and $s_{i}$ are unavailable during model training.

With the notations given below, the fair attribute completion problem is formally defined as:

Problem 1. Given a graph $\mathcal{G=(V,E,X)}$, where node set $\mathcal{V}^{+}\in\mathcal{V}$ with the corresponding attributes available and the corresponding sensitive attributes in $\mathcal{S}$, learn a fair attribute completion model to generate fair feature embeddings $\mathcal{H}$ for each node in $\mathcal{V}$, i.e.,

where $f$ is the function we aim to learn. $\mathcal{H}$ should exclude any sensitive information while preserve non-sensitive information.

We propose a fair attribute completion (FairAC) framework to address Problem 1. Existing fair graph learning methods tackle unfairness issues by training fair graph neural networks in an end-to-end fashion, but they cannot effectively handle graphs that are severely biased due to missing attributes. Our FairAC framework, as a data-centric approach, deals with the unfairness issue from a new perspective, by explicitly debiasing the graph with feature unfairness mitigation and fairness-aware attribute completion. Eventually, FairAC generates fair embeddings for all nodes including the ones without any attributes. The training algorithms are shown in Algorithm 1.

To train the graph attribute completion model, we follow the setting in (Jin et al., 2021) and divide the nodes with attributes (i.e., $\mathcal{V}^{+}$) into two sets: $\mathcal{V}_{keep}$ and $\mathcal{V}_{drop}$. For nodes in $\mathcal{V}_{keep}$, we keep their attributes, while for nodes in $\mathcal{V}_{drop}$, we temporally drop their attributes and try to recover them using our attribute completion model. Although the nodes are randomly assigned to $\mathcal{V}_{keep}$ and $\mathcal{V}_{drop}$, the proportion of $\mathcal{V}_{drop}$ is consistent with the attribute missing rate $\alpha$ of graph $\mathcal{G}$, i.e., $\alpha=\frac{|\mathcal{V}^{-}|}{|\mathcal{V}|}=\frac{|\mathcal{V}_{drop}|}{|\mathcal{V}^{+}|}$.

Different from existing work on fair graph learning, we consider unfairness from two sources. The first one is from node features. For example, we can roughly infer one’s sensitive information, like gender, from some non-sensitive attributes like hobbies. It means that non-sensitive attributes may imply sensitive attributes and thus lead to unfairness in model prediction. We adopt a sensitive discriminator to mitigate feature unfairness. The other source is topological unfairness introduced by graph topological embeddings and node attribute completion. To deal with the topological unfairness, we force the estimated feature embeddings to fool the sensitive discriminator, by updating attention parameters during the attribute completion process.

As illustrated in Figure 1, our FairAC framework first mitigates feature unfairness for nodes with attributes (i.e., $\mathcal{V}_{keep}$) by removing sensitive information implicitly contained in non-sensitive attributes with an auto-encoder and sensitive classifier (Section 3.2.1). For nodes without features (i.e., $\mathcal{V}_{drop}$), FairAC performs attribute completion with an attention mechanism (Section 3.2.2) and meanwhile mitigates the topological unfairness (Section 3.2.3). Finally, the FairAC model trained on $\mathcal{V}_{keep}$ and $\mathcal{V}_{drop}$ can be used to infer fair embeddings for nodes in $\mathcal{V}^{-}$.

The overall loss function of FairAC is formulated as:

where $\mathcal{L}_{F}$ represents the loss for mitigating feature unfairness, $\mathcal{L}_{C}$ is the loss for attribute completion, and $\mathcal{L}_{T}$ is the loss for mitigating topological unfairness. $\beta$ is a trade-off hyperparameter.

The proposed FairAC framework could be viewed as a generic data debiasing approach, which achieves fairness-aware attribute completion and node embedding for graphs with missing attributes. It can be easily integrated with many existing graph neural networks (e.g., GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2018), and GraphSAGE (Hamilton et al., 2017)) for tasks like node classification. In this work, we choose the basic GCN model for node classification and assess how FairAC enhances model performance in terms of accuracy and fairness.

Datasets. In the experiments, we use three public graph datasets, NBA, Pokec-z, and Pokec-n. A detailed description is shown in supplementary materials.

Baselines. We compare our FairAC method with the following baseline methods: GCN (Kipf & Welling, 2016), ALFR (Edwards & Storkey, 2015), ALFR-e, Debias (Zhang et al., 2018), Debias-e, FCGE (Bose & Hamilton, 2019), and FairGNN (Dai & Wang, 2021). ALFR-e concatenates the feature embeddings produced by ALFR with topological embeddings learned by DeepWalk (Perozzi et al., 2014). Debias-e also concatenates the topological embeddings learned by DeepWalk with feature embeddings learned by Debias. FairGNN is an end-to-end debias method which aims to mitigate unfairness in label prediction task. GCN and FairGNN uses the average attribute completion method, while other baselines use original complete attributes.

Evaluation Metrics. We evaluate the proposed framework with respect to two aspects: classification performance and fairness performance. For classification, we use accuracy and AUC scores.As for fairness, we adopt $\Delta SP$ and $\Delta EO$ as evaluation metrics, which can be defined as:

The smaller $\Delta SP$ and $\Delta EO$ are, the more fair the model is. In addition, we use $\Delta SP$+$\Delta EO$ as an overall indicator of a model’s performance on fairness.