Fair Attribute Completion on Graph with Missing Attributes
Authors: Dongliang Guo
Zhixuan Chu
Sheng Li
Venue: ICLR 2023 poster (2023)

Abstract: Tackling unfairness in graph learning models is a challenging task, as the unfairness issues on graphs involve both attributes and topological structures. Existing work on fair graph learning simply assumes that attributes of all nodes are available for model training and then makes fair predictions. In practice, however, the attributes of some nodes might not be accessible due to missing data or privacy concerns, which makes fair graph learning even more challenging. In this paper, we propose FairAC, a fair attribute completion method, to complement missing information and learn fair node embeddings for graphs with missing attributes. FairAC adopts an attention mechanism to deal with the attribute missing problem and meanwhile, it mitigates two types of unfairness, i.e., feature unfairness from attributes and topological unfairness due to attribute completion. FairAC can work on various types of homogeneous graphs and generate fair embeddings for them and thus can be applied to most downstream tasks to improve their fairness performance. To our best knowledge, FairAC is the first method that jointly addresses the graph attribution completion and graph unfairness problems. Experimental results on benchmark datasets show that our method achieves better fairness performance with less sacrifice in accuracy, compared with the state-of-the-art methods of fair graph learning. Code is available at: https://github.com/donglgcn/FairAC.

Published as a conference paper at ICLR 2023
FAIR ATTRIBUTE COMPLETION ON GRAPH WITH MISSING ATTRIBUTES
Dongliang Guo', Zhixuan Chu², Sheng Li Universiiy of Georgia, Ant Group, 'University of Virginia dg548836uga. edu, chuzhixuan czx@al ieaiaaiaainneee com, shengli@virginia.co
ABSTRACT
Tackling unfairness in graph learning models is a challenging task, as the unfair- ness issues on graphs involve both attributes and topological structures. Exist- ing work on fair graph learning simply assumes that attributes of all nodes are available for model training and then makes fair predictions. In practice, how- ever, the attributes of some nodes might not be accessible due to missing data or privacy concerns, which makes fair graph learning even more challenging. In this paper, we propose FairAC, fair attribute completion method, to comple- ment missing information and learn fair node embeddings for graphs with miss- ing attributes. FairAC adopts an attention mechanism deal with the attribute missing problem and meanwhile, it mitigates two types of unfairness, i.e., fea- ture unfairness from attributes and topological unfairness due to attribute com- pletion. FairAC can work on various types of homogeneous graphs and generate fair embeddings for them and thus can be applied to most downstream tasks to improve their fairness performance. To our best knowledge, FairAC is the first method that jointly addresses the graph attribution completion and graph unfair- ness problems. Experimental results on benchmark datasets show that our method achieves better fairness performance with less sacrifice in accuracy, compared with the state-of-the-aar art methods of fair graph learning. Code is available at: /ett:s:///iithuu.com/ce
INTRODUCTION
Graphs, such as social networks, biomedical networks, and traffic networks, are commonly ob- served in many real-world applications. A lot of graph-based machine learning methods have been proposed in the past decades, and they have shown promising performance in tasks like node simi- larity measurement, node classification, graph regression, and community detection. In recent years, graph neural networks (GNNs) have been actively studied (Scarselli et al., 2008 Wu et al., 2020 Jiang et al. 2019 2020 Zhu al. c0 Hua et al. 2020 Chu et al. (021). which can model graphs with high-dingg dimenssiini attributes in the non- Lunn-Euliienn space and have achieved great success in many areas such as recommender systems (Sheu et al. 2021). However, it has been observed that many graphs are biased, and thus GNNs trained on the biased graphs may be unfair with respect to certain sensitive attributes such demographic groups. For example, in social network, the users with the same gender have more active connections, the GNNs tend to pay more attention such gender information and lead to gender bias by recommending more friends the same gender identity while ignoring other attributes like interests. And from the data privacy perspective, possible to infer one's sensitive information from the results given by GNNs (Sun) et al. 2018). In time when GNNs are widely deployed in the real world, this severe unfairness is unacceptable. Thus, fairness in graph learning emerges and becomes notable very recently.
user with
Existing work on fair graph learning mainly focuses on the pre-processing, in-processing, and post- processing steps in the graph learning pipeline in order to mitigate the unfairness issues. The pre- processing approaches modify the original data to conceal sensitive attributes. Fairwalk (Rahman et al. (019) is a representative pre- proppsscs method, which enforces each group of neighboring nodes equal chance to be chosen in the sampling process. In many in processing methods, the most popular way is to add a sensitive discriminator as a constraint, order to filter out sensitive information from original data. For example, FairGNN (Dai & Wang 202T) adopts sensitive

---

Published as a conference paper at ICLR 2023
classifier to filter node embeddings. CFC (Bose& & Hamilton 2019) directly adds filter layer to deal with unfaimess issues. The post- pootessoesssing methods directly force the final prediction to satisfy faimess constraints, such as (Hardt et al., (016).
When the graphs have complete node attributes, existing fair graph learning methods could obtain promising performance both faimess and accuracy. However, in practice, graphs may contain nodes whose attributes are entirely missing due to various reasons (e.g., newly added nodes, and data privacy concerns). Taking social networks as an example, a newly registered user may have incomplete profiles. Given such incomplete graphs, existing fair graph learning methods would fail, as they assume all the nodes have attributes for model training. Although FairGNN (Dai & Wang 2021) also involves the missing attribute problem, it only assumes that part of the sensitive attributes are missing. To the best of our knowledge, addressing the unfairness issue on graphs with some nodes whose attributes are entirely missing has not been investigated before. Another relevant topic is graph attribute completion (Jin et al. 202T] Chen et al.) 2020). It mainly focuses on completing a precise graph but ignores the unfaimeess issues. In this work, aim to jointly complete a graph with missing attributes and mitigate unfairness at both feature and topology levels.
In this paper, we study the new problem of learning fair embeddings for graphs with missing at- tributes. Specifically, we aim to address two major challenges:
(1) how to obtain meaningful node embeddings for graphs with missing attributes, and (2) how to enhance faimess of node embeddings with respect to sensitive attributes. To address these two challenges, we propose a Fair Attribute Completion (FairAC) framework. For the first challenge, embeddings for nodes with attributes and meanwhile we adopt an attention mechanism to aggregate feature information of nodes with missing attributes from their direct neighbors. Then, we address the second challenge by mitigating two types of unfairness, i.e., feature unfairness and topological unfairness. We adopt a sensitive discriminator to regulate embeddings and create a bias-free graph.
adopt autoencoder obtain feature
The main contributions of this paper are as follows: (I) We present a new problem of achieving fairness on graph with missing attributes. Different from the existing work, we assume that the attributes of some nodes are entirely missing. (2) We propose a new framework, FairAC, for fair graph attribute completion, which jointly addresses unfairness issues from the feature and topology perspectives. (3) FairAC is a generic approach to complete fair graph attributes, and thus can be used in many graph-based downstream tasks. (4) Extensive experiments on benchmark datasets demon- strate the effectiveness of FairAC in eliminating unfairness and maintaining comparable accuracy.
RELATED WORK
2.1 FAIRNESS IN GRAPH LEARNING
Recent work promotes fairness in graph-based machine learning (Bose & Hamilton, 2019 Rah- man 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 applied before training downstream tasks by modifying train- ing data. For instance, Fairwalk (Rahman et al., (019) improves the sampling procedure of node2vec (Grover & Leskovee (0166). 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 unfaireess 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-ine invvriiant embeddings. However, in order generate counterfactual sub- graphs, they need precise and entire features for every node. In other words, it cannot work well encounters graph with full missing nodes since it cannot generate counterfactual subgraph based
2

---

Published as a conference paper at ICLR 2023
Topological node embedding))
Attertion matii
1
Fs
74
%
Advemorial werming
7s
Berudlive Clossiffer (6g)
encoder
decoddrr
Feature embeddingtt)
Artwrsaniia leamn
Receretrration lose
Comptettio
Figure 1: Overview of our FairAC framework. FairAC is composed of three major modules, i.e., an autoencoder for embedding nodes, an attributes completion module, and sensitive classifiers for mitigating feature unfairness and topological unfairness. The solid circles indicate nodes with full attributes, while the empty circles indicate nodes without any attributes.
on blank node. But we can deal with the situation. The most related work is FairGNN (Di & Wang 202T). Different from the majority of problem settings on graph fairness. It learns fair GNNs for node classification in graph where only limited number of nodes are provided with sensitive attributes. FairGNN adopts a sensitive classifier to predict the missing sensitive labels. After that, it employs classic adversarial model to mitigate Mnfairness.Specificclll
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 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 recover the node embeddings from their neigh- bors. 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 embed- dings 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.
2.2 ATTRIBUTION COMPLETION ON GRAPHS
The problem of missing attributes is ubiquitous in reality. Several methods (Liao et al. 2016 You
let al. 2020 Chen et al. 2020 He et al. 2022 Jin et al., 2021 2022 Tu et al. 2022 Taguchi et al., 202T have been proposed address this problem. GRAPE You al.) 2020) tack es 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 heterogeneous graphs. HGNN-AC (Jin et al. (021) 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 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 faimess 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.
3 METHODOLOGY
3.1 PROBLEM DEFINITION
Let g = (V, Exx' denote an undirected graph, where V = {Ui, U2 UN} is the set of N nodes, E C V x V is the set of undirected edges in the graph, X N is the node attribute matrix, and is the dimension of attributes. A E N* is the adjacency matrix of the graph G, where Aij 1 if nodes vú and ny connected; otherwise, Arg = In addition, S = {81, 82,
3

---

Published as a conference paper at ICLR 2023
Algorithm FairAC framework algorithm
Input: G = (V, x),
Output:
Autoencoder
fAE.
Sensitive
classifier
C..
Attribute
completion
fAC
1: Obtain topological embedding T with DeepWalk
2: repeat
3: Obtain the feature embeddings H with fAE
4: Optimize the C. by Equation 6
5: Optimize fAE to mitigate feature unfairness by loss LF
6:
Divide V+ into Vkeep and Varop based on
7: Obtain the feature embeddings of nodes with missing attributes Värop by SAC
8:
Optimize fAc to achieve attribute completion by loss Lc Optimize fAC to mitigate topological unfairness by loss Cr
9:
10:
until convergence
11: return fAE, C., SAC
denotes set of sensitive attributes (e.g., age or gender) of N nodes, and y {yr, 92. ... yx denotes the node labels. The goal of fair graph learning is to make fair predictions of node labels with respect the sensitive attribute, which is usually measured by certain fairness notations like statistical parity (Dwork et al., 2012) and equal opportunity (Hardt et al., (016)) Statistical Parity and Equal Opportunity are two group fairness definitions. Their detailed formulations are presented below. The label y denotes the mround-truth node label, and the sensitive attribute indicates one's 's sensitive group. For example, for binary node classification task, only has two labels. Here we consider two sensitive groups. i.e. {0, 1}.
Statistical Parity (Dwork et al. 2012). It refers to the equal acceptance rate, which can be formulated as:
P(j]= = 0) = P(jis = 1);
where P.-) denotes the probability that occurs.
Equal Opportunity (Hardt et al., 2016). It means the probability of a node positive class being classified as positive outcome should be equal for both sensitive group nodes. It mathematically requires an equal true positive rate for each subgroup.
P = 1/y = 1, = 0) = P(g = 1ly 1, 1).
(2)
In this work, mainly focus addressing unfairness issues graphs with missing attributes, i.e., attributes of some nodes are totally missing. Let V denote the set of nodes whose attributes are available, and V denote the set of nodes whose attributes missing, V (V+ V If V- both X; and 8; are unavailable during model training.
With the notations given below, the fair attribute completion problem is formally defined as:
Problem I. Given graph G X), where node set V+ E V with the corresponding attributes available and the corresponding sensitive attributes in S, learn fair attribute completion model to generate fair feature embeddings 'H for each node in V, i.e.,
f(g,S) + H. where f is the function we aim to learn. H. should exclude any sensitive information while preserve non-sensitive information.
(3)
3.2 FAIR ATTRIBUTE COMPLETION (FAIRAC) FRAMEWORK
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 new perspective, by explicitly debiasing the graph with feature unfairness mitigation and faimess-- aware attribute completion. Eventually, FairAC generates fair embeddings for all nodes including the ones without any attributes. The training algorithms are shown in Algorithm
4

---

Published as a conference paper at ICLR 2023
To train the graph attribute completion model, we follow the setting in (Jin et al. 2021) and divide the nodes with attributes (i.e., V*) into two sets: Vkeep and Varop. For nodes in Vkeeps we keep their attributes, while for nodes in Varops temporally drop their attributes and try to recover them using our attribute completion model. Although the nodes are randomly assigned to Vkeep and Varop: the proportion of Varop is consistent with the attribute missing rate of graph 9, i.e., [
1
Different from existing work fair graph learning, consider unfairness from 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 sensitive discriminator to mitigate feature unfairness. The other souree is topological unfairness introduced by graph topological embeddings and node attribute completion. To deal with the topological un- fairness, we force the estimated feature embeddings fool the sensitive discriminator, by updating attention parameters during the attribute completion process.
As illustrated in Figure | our FairAC framework first mitigates feature unfairness for nodes with attributes (i.e.. Vkeep) by removing sensitive information implicitly contained in non-sensitive at- tributes with an auto-encoder and sensitive classifier (Section 3.2.1]. For nodes without features (i.e.. Varop). FairAC performs attribute completion with attention mechanism (Section 3.2.2) and meanwhile mitigates the topological unfairness (Section B.2.3). Finally, the FairAC model trained on Vkeep and Varop can be used to infer fair embeddings for nodes in V
The overall loss function of FairAC is formulated as:
C LF + Lo BLT,
(4)
where LE represents the loss for mitigating feature unfaimess, Lc is the loss for attribute comple- tion, and Lr the loss for mitigating topological unfairness. /3 is trade-off hyperparameter.
3.2.1 MITIGATING FEATURE UNFAIRNESS
The nodes in Veeep have full attributes X, while some attributes may implicitly encode information about sensitive attributes and thus lead to unfair predictions. To address this issue, FairAC aims to encode the attributes X3 of node i into fair feature embedding H4. Specifically, we use simple autoencoder framework together with a sensitive classifier. The autoencoder maps X; into embedding Hi, and meanwhile the sensitive classifier C. is trained in an adversarial way, such that the embeddings are invariant to sensitive attributes.
The autoencoder contains encoder fE and decoder fo- fæ encodes the original attributes X; to feature embeddings H4, i.e., H4 = (xx),, and fn reconstructs attributes from the latent embeddings, i.e., &₂ fo (H+), where the reconstructed attributes & should be close to X, as possible. The loss function of the autoencoder is written as:
Autoencoder.
Lac
Σ
V x.)
(S)
Dkeepl
iEVycop!
Sensitive classifier The sensitive classifier C. is a simple multilayer perceptron (MLP) model. It takes the feature embedding H, as input and predicts the sensitive attribute s,, i.e., 5; CHH.)). When the sensitive attributes are binary, we can use the binary cross entropy loss to optimize C,:
Lc,
Σ
log 6, + +1 s;) log -6)-
[Kkeep
VEVeccy
With the sensitive classifier C., we could leverage it to adversarially train the autoencoder, such that fE is able to generate fair feature embeddings that can fool C.. The loss Lp written as: LF = Lue BLc..
3.2.2 COMPLETING NODE EMBEDDINGS VIA ATTENTION MECHANISM
For nodes without attributes (Varap). FairAC makes use topological embeddings and completes the node embeddings Herop with attention mechanism.
5

---

Published as a conference paper at ICLR 2023
Topological embeddings. Recent studies reveal that the topology of graphs has similar semantic information as the attributes (Chen et al. 2020, McPherson et al., 2001 Pei et al. 2020 Zhu et al, 2020). Inspired by this observation, assume that the nodes' topologiaa information can reflect the relationship between nodes' attributes and the attributes of their neighbors. There are lot of off-the-shelf node topological embedding methods, such DeepWalk (Perozzi et al.) (014) and node2vec (Grover & Leskovec] 2016). For simplicity, we adopt the DeepWalk method to extract topological embeddings for nodes in
Attention mechanism. For graphs with missing attributes, a commonly used strategy is to use average attributes of the one-hop neighbors. This strategy works in some cases, however, simply averaging information from neighbors might be biased, the results might be dominated by some high-degree nodes. In fact, different neighbors should have varying contributions to the aggregation process in the context of fairness. To this end, FairAC adopts attention mechanism Vaswani et al.) 2017) to learn the influence of different neighbors or edges with the awareness of fairness, and then aggregates attributes information for nodes in Värop-
Given a pair of nodes (u, a) which are neighbors, the contribution of node v is the attention atta, which is defined nodes u and v, respectively. Specifically, we only focus on the neighbor pairs and ignore those node pairs that are not directly connected. Attention((.") denotes the attention between two topological embeddings, i.e., Attention T,) o WT)), where W is the learnable parametric matrix, and a an activation function. After we get all the attention scores between one node and its neighbors, we can get the coefficient of each pair by applying the softmax function:
atl Attention(Ta, Tø), where Tu,, Tú are the topological embeddings of
exp(attu..)
Cu, softmax(atta..)) EVEN, exp(attu..)
where Cu,v is the coefficient of node pair (u, v), and Nu is the set of neighbors of node For node u, FairAC calculates its feature embedding H. by the weighted aggregation with multi-head attention:
1 K
N.
Ho.
(8)
k=lxEN
where K is the number of attention heads. The loss for attribute completion with topological em- bedding and attention mechanism is formulated as:
Lo
Σ [Vropl <EVerop!
(AA (H)).
3.2.3 MITIGATING TOPOLOGICAL UNFAIRNESS
The attribute completion procedure may introduce topological unfairness since we assume that topology information is similar to attributes relation. It is possible that the completed feature em- beddings of Varop would unfair with respect to sensitive attributes S. To address this issue, FairAC leverages sensitive classifier C, to help mitigate topological unfairness by further updating the attention parameter matrix W and thus obtaining fair feature embeddings H. Inspired by (Gong al. 2020), expect that the feature embeddings fool the sensitive classifier C. to predict the probability distribution close to the uniform distribution over the sensitive category, by minimizing the loss:
LT
Σ VEVarop
8; log &4 + (1 8s) log (1 62).
(10)
Varopl
3.3 FAIRAC FOR NODE CLASSIFICATION
The proposed FairAC framework could be viewed as a generic data debiasing approach, which achieves faimess--waae attribute completion and node embedding for graphs with missing attributes. 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. this work, we choose the basic GCN model for node classification and assess how FairAC enhances model performance in terms of accuracy and fairness.

---

Published as a conference paper at ICLR 2023
Table 1: Comparisons of our FairAC method and baselines on three graphs. M refers missing or
not. M is true means that some nodes' attributes are entirely missing and the ratio is controlled by a. Otherwise, full attributes are provided. The attribute missing rate set 0.3. GCN and FairGNN are trained averaging attribute completed graphs. Bold fonts denote the best results.
Datasct
Method
M
Acc f
AUC
ASP L
AEO L
ASP+ABO L
GCN
70.66:0.24
74.2340.63
3,43+2.44
2.74
6,1633.1
ALFR
6..3+1.3
71.5+0.3
2.3+0.9
3.2+1.5
5.5+2.4
A
X
66.0=t0.4
72.9+1.0
4.71188
4.7+17
9,443.4
NBA
Dehias
X
63.1+11.1
71.3+0077
2.5
3.1+1.9
5.643.4
Debias-e
65.6++2.4 x
72.9+112
5.3+0.9
3.1+1.3
8,44222
FOGE
X
66.011155
73.611.
2,91100
3.0112
5,942.2
FairGNN
70.73=0.44
76.77:10.1
0.95
163=0.67
2.58
FairAC (Ours)
70.66+00.73
74.44+00.67
0.28+
0.63+0.34
0.91+0.559
GCN
67.4-0.88
72.04+1.78
1,96+0.64
4.17+0.54
6.12+1.18
ALFR
X
65.410.33
71.310.3
2.810.5
1.100.
3,9
ALFR-e
68.010.6
74.010.7
5.810.4
2.820.8
8.611.2
Pokeo-z
Debias
65.2+00.7
71.4+00.6
1.9+0.6
1.9+0.4
3.8+1.0
Debias-c
x
67.5+0.7
74.2+00.7
4.7+1.0
3.0+1.4
7.742.44
FOGE
X
65.9100.
71.010.2
3.110.5
1.710.6
4.8.1.11
FairGNN
66.5410..45
70.10.00.07
0.95
1.6310.67
2.5811
FairAC (Ours)
66.94.1..14
72.87.0..13
0.1910.07
0.12
0.31
GCN
66.12.0.88
71.5+0.11
0.46+0.11
1.11
1.87+0.24
ALFR
x
63.1+0066
67.7+0.5
3.05+0.5
3,9+0.6
3.95+1.1
ALFR-e
X
66.2.10.4
71.91110
4.111.88
4.6.1.77
8.7.3.5
Pokec-n
Debias
62.6.11.1
67.910.7
2.411.5
2.6.1.9
5.0.13.4
Debias-c
65.6#2.4
71.7+1.2
3,6+0.9
4.4+1.3
8.0
FOGE
6..8+115
69.5+1.5
4.1+10
5.5+12
9.64222
FairGNN
68.54:10455
70.10+10.07
0.76+L0.15
0.48
1.24
FairAC (Ours)
66.35-40.24
72.32++0.08
0.27+0012
0.14
0.41+00.23
EXPERIMENTS
In this section, we evaluate the performance of the proposed FairAC framework three benchmark datasets terms of node classification accuracy and fairness w.r.t. sensitive attributes. We compare FairAC with other baseline methods in settings with various sensitive attributes or different attribute missing rates. Ablation studies are also provided and discussed.
4.1 DATASETS AND SETTINGS
Datasets. In the experiments, detailed description is shown in supplementary materials.
three public graph datasets, NBA, Pokec-z, and Pokec-n. A
Baselines. We compare our FairAC method with the following baseline methods: GCN (Kipf & Welling 2016), ALER (Edwards & Storkey 2015). ALFR-e, Debias (Zhang et al., 2018), Debias- e, FCGE (Bose& Hamilton, 2019), and FairGNN Dai Wang 2021). ALFR concatenates the feature embeddings produced by ALFR with topological embeddings learned by Deep Walk (Perozzi 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.
We evaluate the proposed framework with respect to two aspects: classifica- tion performance and faimess performance. For classification, we use accuracy and AUC scores.As for fairness, we adopt ASP and AO as evaluation metrics, which can be defined as:
Evaluation Metries.
ASP = P(jss 0) P(i]s 1),
(11)
AEO P 1 1 1,
P(ù 1/y 1,8 1).
(12)
The smaller ASP and AEO are, the more fair the model is. addition, we use ASP+AEO as an overall indicator of model's performance fairness.

---

Published as a conference paper at ICLR 2023
Table 2: Comparisons of our method with the baselines on pokec-z dataset with four levels of attribute missing rates FairAC generates fair and complete node features, and then GCN is trained for node classification. BaseAC a simplified version of FairAC, which only has the attention-basee attribute completion module, but does not contain the module for mitigating feature unfairness and topological unfairness. Bold fonts denote best results.
at
Method GCN
Acc (%)
AUC (%)
ASP (%)
AEO (%)4
ASP+AEO 4
66.10
69.14
0.88
0.20
1.08
0.1
FairGNN
69.37
76.93
0.17
0.29
0.46
BaseAC (Ours)
66.37
69.34
0.07
1.46
1.53
FairAC (Ours)
66.33
69.35
0.14
0.37
0.51
GCN FairGNN
67.40
72.04
1.96
4.17
6.12
0.3
66.54
70.10
0.95
1.63
2.58
BaseAC (Ours)
66.10
69.67
0.78
1.57
2.35
FairAC (Ours)
66.94
72.87
0.19
0.12
0.31
GCN
66.41
70.14
0.07
2.11
2.18
0.5
FairGNN
66.25
70. 13
0.47
1.71
2.18
BaseAC (Ours)
66.13
69.93
0.38
1.60
1.98
FairAC (Ours)
66.45
72.95
0.14
1.06
1.20
GCN FairGNN
66.99
73.13
0.57
1.74
2.31
0.8
66.60
71.35
0.94
0.09
1.03
BaseAC (Ours)
66.06
71.21
0,08
2.20
2.28
FairAC (Ours)
66.10
71.66
0.01
0.69
0.70
4.2
RESULTS AND ANALYSIS
4.2.1
UNFAIRNESS ISSUES IN GRAPH NEURAL NETWORKS
According the results showed in Table ! they reveal several unfairness issues in Graph Neural Networks. We divided them into two categories.
Feature unfairness Feature unfairness is that some non-sensitive attributes could infer sensitive information. Hence, some Graph Neural Networks may Iearn this relation and make unfair prediction. In most cases, ALER and Debias and FCGE have better fairness performance than GCN method. contain proxy variables of sensitive attributes which would lead to biased prediction. Thus, ALFR and Debias methods that try to break up these connections are able to mitigate feature unfairness and obtain better faimess performance. These results further prove the existence of feature unfairness.
as expected because the non-sensitive features may
Topological unfairness Topological unfairness is sourced from graph structure. In other words, edges in graph, i.c. the misrepresentation due to the connection (Mchabi et al., 2021) can bring topological unfairness. From the experiments, ALFR-e and Debias-e have worse fairness performance than ALFR and Debias, respectively. It shows that although graph structure can improve the classification performance, it will bring topological unfair- ness consequently. The worse performance on fairness verifies that topological unfairness exists in GNNs and graph topological information could magnify the discrimination.
4.2.2 EFFECTIVENESS OF FAIRAC ON MITIGATING FEATURE AND TOPOLOGICAL UNFAIRNESS
The results of our FairAC method and baselines in terms of the node classification accuracy and fairnsss metrics on three datasets are shown in Table The best results are shown in bold. Generally speaking, have the following observations. (1). The proposed method FairAC shows comparable classification performance with these baselines, GCN and FairGNN. This suggests that our attribute completion method is able preserve useful information contained in the original attributes. (2).
8

---

Published as a conference paper at ICLR 2023
FairAC outperforms all baselines regarding faimess metrics, especially in ASP+AEO. FairAC outperform baselines that focus on mitigate feature faimess, like ALFR, which proves that FairAC also mitigate topological unfairness. Besides, it is better than those who take topologiaal fairness into consideration, like FCGE, which also validates the effectiveness of FairAC. FairGNN also has good performance on fairness, because it adopts discriminator deal with the unfairness issue. Our method performs better than FairGNN in most cases. For example, our FairAC method can significantly improve the performance in terms of the fairness metric ASP+ AEO, i.e., 65%, 87%, and 67% improvement over FairGNN on the NBA, pokec-z, pokec-n datasets, respectively. Overall, the results Table | validate the effectiveness of FairAC in mitigating unfairness issues.
4.3 ABLATION STUDIES
Attribute missing rate In our proposed framework, the attribute missing rate indicates the in- tegrity of node attribute matrix, which has a great impact on model performance. Here we investigate the performance of our FairAC method and baselines dealing with graphs with varying degrees of missing attributes. In particular, we set the attribute missing rate to 1, 0.3, 0.5 and 0.8, and evaluate FairAC and baselines the pokec-z dataset. The detailed results presented in Table 2 From the table, we have the following observation that with varying values of a, FairAC is able to maintain its high fairness performance. Especially when a reaches 0.8, FairAC can greatly outperform other methods. It proves that FairAC is effective even if the attributes are largely missing.
The effectiveness of adversarial learning A key module in FairAC is adversarial learning, which is used to mitigate feature unfairness and topological unfairness. To investigate the contribution of adversarial learning in FairAC, we implement a BaseAC model, which only has the attention-based attribute completion module, but does not contain the adversarial learning loss terms. Comparing BaseAC with FairAC in Table 2 we can find that the fairesss performance drops desperately when the adversarial training loss is removed. Since BaseAC does not have an adversarial discrimina- tor to regulate feature encoder well as attribute completion parameters, unable mitigate unfairness. Overall, the results confirm the effectiveness of the adversarial learning module.
Parameter analysis We investigate how the hy- perparameters affect the performance of FairAC. The most important hyperparameter in FairAC is B. which adjusts the trade-off between fairness and at- tribute completion. We report the results with differ- ent hyperparameter values. We set 3 to 0.2, 0.4, 0.7, 0.8 and 0 that is equivalent to the BaseAC, We also fix other hyperparameters by setting to 0.3. As shown in Figure 2 we can find that, as 3 increases, the fairness performance improves while the accu- racy of node classification slightly declined. There- fore, it validates our assumption that there is trade- off between fairness and attribute completion, and our FairAC is able to enhance fairness without com- promising too much on accuracy.
3.5
Aoo
2.5
0.5
0.1
0.2
0.3
0.4
0.5
0.
0.7
0.5
Figure 2: Accuracy and ASP+AFO of FairAC when varying on Pokec-z dataset with a = 0.3.
CONCLUSIONS
In this paper, we presented novel problem, i.c., fair attribute completion on graphs with missing attributes. To address this problem, we proposed the FairAC framework, which jointly completes the missing features and mitigates unfairness. FairAC leverages the attention mechanism to complete missing attributes and adopts a sensitive classifier to mitigate implicit feature unfairness as well as topological unfairness graphs. Experimental results on three real-world datasets demonstrate the superiority of the proposed FairAC framework over baselines in terms of both node classification performance and faimess performance. As a generic fair graph attributes completion approach, FairAC can also be used in other graph-based downstream tasks, such as link prediction, graph regression, pagerank, and clustering.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This research supported by the Cisco Faculty Award and Adobe Data Science Research Award.
REFERENCES
Avishek Bose and William Hamilton. Compositional fairness constraints for graph embeddings. In International Conference Machine Learning, pp. 715-724. PMLR, 2019.
Xu Chen, Siheng Chen, Jiangchao Yao, Huangjie Zheng. Ya Zhang, and Ivor W Tsang. Learning attribute- graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
Zhixuan Chu, Stephen L Rathbun, and Sheng Li. Graph infomax adversarial learning for treatment effect estimation with networked observational data. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pp. 176-188680 184, 2021.
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, pp. 680-688, 2021.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Con- ference, pp. 214-226, 2012.
Harrison Edwards and Amos Storkey. Censoring representations with an adversary, 2015. URL
https: wwt/abs/////ooooooooot.opp...srr abs/ 1511.01110 05897
Sixue Gong, Xiaoming Liu, and Anil K Jain. Jointly de-biasing face recognition and demographic attribute estimation. In Europeun Conference Computer Vision, pp. 330-347. Springer, 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs Advances in Neural Information Processing Systems, 30, 2017.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning, Advances in Neural Information Processing Systems, 29, 2016.
Taher H Haveliwala. Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. IEEE Transactions on Knowledge and Data Engineering, 15(4):784-796, 2003.
Dongxiao He, Chundong Liang, Cuiying Huo, Zhiyong Feng, Di Jin, Liang Yang, and Weixiong Zhang. Analyzing heterogeneous networks with missing attributes by unsupervised contrastive learning. IEEE Transactions on Neural Networks and Learning Systems, 2022.
Yuncheng Hua, Yuan-Fang Li, Guilin Qi, Wei Wu, Jingyao Zhang, and Daiqing Qi. Less is more: Data-efficient complex question answering over knowledge bases. Journal of Web Semantics, 65: 100612, 2020.
Xiaodong Jiang, Pengsheng Ji, and Sheng Li. Censnet: convolution with edge-node switching in graph neural networks. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 2656-2662, 2019.
Xiaodong Jiang, Ronghang Zhu, Pengsheng Ji, and Sheng Li. Co-embedding of nodes and edges with graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
Di Jin, Cuiying Huo. Chundong Liang, and Liang Yang. Heterogeneous graph neural network via attribute completion. In Proceedings of the Web Conference 2021, pp. 391-400, 2021.
10

---

Published as a conference paper at ICLR 2023
Di Jin, Rui Wang, Tao Wang. Dongxiao He, Weiping Ding, Yuxiao Huang, Longbiao Wang, and Witold Pedrycz. Amer: A new attribute-man mrribbt network embedding approach. IEEE Transac- tions Cybernetics, pp. 1-14, 2022. doi: 10.1 w..1109/TCYB.222..3313
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.09977 2016.
Lizi Liao. Qirong Ho, Jing Jiang, and Ee-Peng Lim. Slr: A scalable latent role model for attribute completion and tie prediction in social networks. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pp. 1062-1073. IEEE, 2016.
David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7):001--103 2007.
Jing Ma, Ruocheng Guo, Mengting Wan, Longqi Yang, Aidong Zhang, and Jundong Li. Learning fair node representations with graph counterfactual fairness. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pp. 695-703, 2022.
Miller McPherson, Lynn Smith-Lovin, and James Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(():415-444, 2001.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Computing Surveys (CSUR). 54(6):1-35, 2021.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social represen- tations. In Proceedings of the 20th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 701-710, 2014.
Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. In Proceedings of the Twenty-Eighth International Joint Conference on Arti- ficial Intelligence, IJCAI-19, 19, pp. 3289-3295. International Joint Conferences on Artificial Intel- ligence Organization, 7 2019. doi: 10. 10.24963/jjcai.200 2019/456. httpttss: //doi. org/1C.
24963/1jcai. 20199//5....1.56...
Benedek Rozemberczki, Oliver Kiss, and Rik Sarkar. Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs, Proceedings of the 29th ACM Inter- national Conference Information and Knowledge Management (CIKM '20,, pp. 3125-3132. ACM, 2020.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trunsactions on Neural Networks and Learning Systems, 20(1):61-80, 2008
Heng-Shiou Sheu, Zhixuan Chu, Daiqing Qi, and Sheng Li. Knowledge-guided article embedding refinement for session-basee news recommendation. IEEE Transactions Neural Networks and Learning Systems, 33( (112177791117927, 2021.
Lichao Sun, Yingtong Dou, Carl Yang, Ji Wang, Philip S Yu, Lifang He, and Bo Li. Adversarial 2018.
attack and defense on graph data: A survey. arXiv preprint
Hibiki Taguchi, Xin Liu, and Tsuyoshi Murata. Graph convolutional networks for graphs containing missing features. Future Generation Computer Systems, 117:155-168, 2021.
Lubos Takac and Michal Zabovsky. Data analysis in public social networks. In International scien- tific conference and international workshop present day trends of innovations, volume 1. Present Day Trends of Innovations Lamza Poland, 2012.

---

Published as a conference paper at ICLR 2023
Ben Taskar, Ming-Fai Fai Wong, Pieter Abbeel, and Daphne Koller. Link prediction in relational data. Advances in Neural Information Processing Systems, 16, 2003.
Wenxuan Tu, Sihang Zhou, Xinwang Liu, Yue Liu, Zhiping Cai, En Zhu, Changwang Zhang, and Jieren Cheng. Initializing then refining: A simple graph attribute imputation network. In Lud De Raedt (ed.), Proceedings of the Thirty-Firsi International Joint Conference on Artificial Intelli- gence, IJCAI-22. pp. 3494-3500, International Joint Conferences on Artificial Intelligence Or- ganization, 7 2022.
doi: (0.24963/jcaai22222/533 URL attps://doll /2499/ 249637
Ejcci. 2022 485
Main Track.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Informa- tion Processing Systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018. URL
Nan Wang, Lu Lin, Jundong Li, and Hongning Wang. Unbiased graph embedding with biased graph observations. In Proceedings of the ACM Web Conference 2022, pp. 1423-1433, 2022.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 32(1):4-22) 2020.
Jiaxuan You, Xiaobai Ma. Yi Ding, Mykel J Kochenderfer, and Jure Leskovec. Handling missing data with graph representation learning. Advances in Neural Information Processing Systems, 33: 19975-19087) 2020.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adver- sarial learning. In Proceedings of the 2018 AAAI/ACM Conference on Al, Ethics, and Society, pp. 335-340, 2018.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7804, 2020.
Ronghang Zhu, Xiaodong Jiang, Jiasen Lu, and Sheng Li. Cross-domain graph convolutions for ad- versarial unsupervised domain adaptation. IEEE Transactions on Neural Networks and Learning Systems, 2021a
Ronghang Zhu, Xiaodong Jiang, Jiasen Lu, and Sheng Li. Transferable feature learning on graphs across visual domains. In 2021 IEEE International Conference on Multimedia and Expo (ICME), pp. 1-6. IEFF, 2021b.
Ronghang Zhu, Zhiqiang Tao, Yaliang Li, and Sheng Li. Automated graph learning via popula- tion based self-tuning gen. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2096 2100, 2021c
12

---

Published as a conference paper at ICLR 2023
Table 3: Statistics of three graph datasets.
Dataset
NBA
Pokec-z
Pokec-n
of nodes
403
67,797
66,569
# of edges
16,570
882.765
729,129
Density
0.10228
0.00019
0.00016
A APPENDIX
A.I DATASETS AND SETTINGS
Datasets. In the experiments, we use three public graph datasets, NBA, Pokec-z, and Pokec-n. The detailed explanation is shown in supplementary materials. The NBA dataset (Dai & Wang. 2021] is extended from a Kaggle dataset containing around 400 NBA basketball players. It provides the performance statistics of those players in the 2016-2017 season and their personal profiles, e.g., nationality, age, and salary. Their relationships are obtained from Twitter. We use their nationality, whether one is U.S. player or oversea player, the sensitive attribute. The node label is binary, indicating whether the salary of the player is over median or not. Pokec (Takac & Zabovsky 2012) an online social network Slovakia, which contains millions of anonymized data of users. has variety of attributes, such as gender, age, education, region, etc. Based on the region where users belong to, (Dai Wang, 2021) sampled two datasets named as: Pokec-z and Pokec-n, In our experiments, we consider the region or gender as sensitive attribute, and working field as label for node classification. The statistics of three datasets are summarized in supplementary materials. The statistics of three datasets are summarized in Table 3
Baselines.
We compare our FairAC method with the following baseline methods:
GCN (Kipf & Welling 2016) with average attribute completion. GCN is classical graph neural network model, which has obtained very promising performance in numerous applications. The standard GCN cannot handle graphs with missing attributes. In the experiments, we use the average attribute completion strategy to preprocess the feature matrix, by using the averaged attributes of one's neighbors approximate the missing attributes. After average attribute completion, GCN takes the graph with completed feature matrix as inputs learn node embeddings and predict node labels.
ALFR (Edwards & Storkey 2015) with full attributes. This a pee-ppreessseeee pee-prceessig method. It utilize discriminator to remove the sensitive feature information in feature embeddings produced by an Autoencoder. Since this method need full sensitive attributes and full fea- tures, we give them complete information. In other words, the missing rate is set to 0.
ALFR-e with full attributes. Based on ALFR, ALFR-e utilize the topological informa- tion. It concatenates the feature embeddings produced by ALFR with topological embed- dings learned by DeepWalk (Perozzi et al. 2014). It also relys on complete information.
Debias (Zhang et al., 2018) with full attributes. This is an in-processing method. applies a discriminator on node classifier in order make the probability distribution be the same w.r.t. sensitive attribute. Since the discriminator needs the full sensitive attributes, we provide full node features.
Debias-e with full attributes. Similar to ALFR-e. It also concatenates the topological embeddings learned by DeepWalk (Perozzi et al. 2014) with feature embeddings learned by Debias.
FCGE (Bose & Hamilton, 2019) with full attributes. learns fair node embeddings in graph without node features through edge prediction only. An discriminator is also applied to mitigate sensitive information in topological perspective.
FairGNN (Dai & Wang 2021) with average attribute completion. Although FairGNN trains sensitive attribute discriminator adversarial regularizer enhance the fairness
13

---

Published as a conference paper at ICLR 2023
Table 4: Comparisons of our method with the baselines on pokec-n dataset with three levels of attribute missing rates a. FairAC generates fair and complete node features, and then GAT is trained for node classification. Bold fonts denote the best results.
Method GAT
Ace (%)f
AUC (%)t
ASP (%)
AEO (%)
ASP+AEO
67.77
73.57
1.02
3.38
3,40
0.3
FairGNNN
66.55
68.64
0.45
0.99
1.44
FairAC (Ours)
67.25
72.96
0.23
0.10
0.33
GAT
68.59
73.97
0.30
1.96
2.26
FairGNN
68.09
72.22
0.81
1.55
2.36
FairAC (Ours)
66.36
70.66
0.09
0.32
0.41
GAT FairGNN
67.59
71.62
3.69
7.15
10.84
0.7
62.36
67.99
2.95
3.55
6.50
FairAC (Ours)
66.64
69.59
0.18
4.19
4.37
of GNNs, it still cannot deal with graphs with missing attributes. Thus, use the average attribute completion method to complete the feature matrix, and then train a FairGNN model for node classification.
Implementation Details. Each dataset is randomly split into 75%/25% training/test set as Dai
& Wang, (02T). Besides, randomly drop node attributes based the attribute missing rate, o, which means the attributes a x [V] nodes will be unavailable. For each datasets, we choose specific attribute as the sensitive attribute. In particular, region, and nation are selected as the sensitive attribute for the pokec, and nba datasets, respectively. Unless otherwise specified, we generate 128 128-dimension node embeddings and the attribute missing rate a 0.3, and set the hyperparameters of FairAC as: B = for pokec-z and nba datasets, and / = 0.5 for pokec-n dataset. adopt Adam (Kingma Ba 2014) with the learning rate of 0.001 and weight decay as le 5. We adopt the DeepWalk (Perozzi et al. 2014) method to generate topological embedding for each node. Specifically, we use the Deep Walk implementation provided by the Karate Club library (Rozemberezki et al. 2020). We set walk length as 100, embedding dimension 64, window size as 5, and epochs as I0. To evaluate fairness of compared methods, we follow the widely used evaluation protocol in fair graph learning and set threshold for accuracy, because there is trade-off between accuracy and fairness. Since we mainly focus on the fairness metric, we set the accuracy threshold that all methods can satisfy. evaluated and standard dsviation(std), We estimate the std of ASP+ A EO by adding std of ASP and AEO,
models three times and calculated the mean
because for some methods, we use the reported data from Dai Wang 2021 which does provide the metric.
A.2 ADDITIONAL EXPERIMENTS
Evaluations on GAT VVelikovvi et al. 2018) model. As discussed the main paper, the pro- posed FairAC method can be easily integrated with existing graph neural networks. Extensive sults in Section of the main paper demonstrate that the combination of FairAC and GCN performs very well. In this section, we integrate FairAC with another representative graph neural network model, GAT (Veličković et al. 2018). The results of our method and two main baselines in terms of the node classification accuracy and fairness metries are shown in Table 4 In these experiments, FairAC generates fair and complete node features, and then GAT is trained for node classification. We also investigate the performance of our FairAC method and baselines on dealing with graphs with varying degrees of missing attributes. We set the attribute missing rate to 0.1, 0.3, 0.5 and 0.7, and evaluate FairAC and baselines on the Pokec-n dataset. In addition, we set /3 1.0. The best results are shown in bold. Generally speaking, have the following observations. (1). The pro- posed method FairAC shows comparable classification performance with two baselines, GAT and FairGNN. This suggests that our attribute completion method is able to work well under different downstream models. It further demonstrates that FairAC can preserve useful information implied in the original attributes. (2). FairAC has comparable results with two baselines regarding fairness
14

---

Published as a conference paper at ICLR 2023
metrics. Especially when is greater than 0.3, FairAC can greatly outperform other methods, which proves that FairAC effective even if the attributes are largely missing. Overall, the results in Table 4 validate the effectiveness of FairAC in mitigating unfairness issues and show the compatibility with varying downstream models.
15


Reviews:
[{"review_id": "wooqvSgFusb", "reviewer": "Reviewer_ntMx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In practice, due to the lack of data or privacy issues, the attributes of some nodes may not be accessible, which makes fair graph learning more challenging. This paper proposes a fair attribute completion method FairAC to supplement the missing information, learn the fair node embedding of the missing attribute graph, and adopt a attention mechanism to deal with the attribute missing problem to improve their performance.\nThe author claims that FiairAC is the first method to jointly solve the problem of graph attribute completion and graph unfairness. The experimental results show that this method has lower sacrifice and better fairness in fair learning.", "summary_of_the_review": "My research field is not related to this manuscript and I am not very familiar with the research content. ", "strength_and_weaknesses": "The author claims that FiairAC is the first method to jointly solve the problem of graph attribute completion and graph unfairness.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "goi29XXcayM", "reviewer": "Reviewer_ifZW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper considers the problem of fair attribute completion on graphs with missing attributes. The authors proposed the FairAC framework, which jointly completes the missing features and mitigates unfairness. FairAC leverages the attention mechanism to complete missing attributes and adopts a sensitive classifier to mitigate implicit feature unfairness as well as topological unfairness on graphs. Experimental results on three real-world datasets demonstrate the superiority of the proposed FairAC framework over baselines in terms of both node classification performance and fairness performance.", "summary_of_the_review": "The paper considers the problem of fair attribute completion on graphs with missing attributes and proposes the FairAC framework. The novelty of the problem has not been clarified clearly, and the empirical results seem not that powerful compared to FairGNN. \n\nOverall, I do not recommend acceptance.\n\n%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\nThanks for the response. It addresses my questions and I raise the score.", "strength_and_weaknesses": "Strength:\n- The topic of fair attribute completion on graphs with missing attributes is relevant and natural.\n- The pre-processing idea has the potential to be applied to multiple downstream tasks to improve their fairness performance.\n\nWeaknesses:\n- The novelty of the problem has not been clarified clearly. The authors mentioned that FairGNN [Dai & Wang (2021)] also involves the missing attribute problem, and claimed that the paper only assumes that a part of the sensitive attributes is missing. However, I don't see many differences between partial missing and full missing for nodes. What makes the full missing setting more challenging? What is the technical difficulty of proposing methods under this setting compared to the partial missing setting? These problems should be discussed more.\n- The empirical results seem not that powerful to me. The performance of FairAC is quite close to FairGNN, sometimes better and sometimes worse with slight differences. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RJChjbRN1b", "reviewer": "Reviewer_Rh4z", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In this paper, the authors study an important graph embedding issue, i.e., fairness on attribute-missing graphs. They propose a new fair attribute completion method to solve it by considering both feature and topological unfairness. The experiments show comparable results of the proposed method on some benchmarks.", "summary_of_the_review": "The paper has studied a very interesting problem. Besides, the idea of the paper is novel and the work is technique solid.", "strength_and_weaknesses": "Strengths\n\n1.\tThe topic is interesting and important for the graph representation learning community.\n\n2.\tThis work introduces a valuable learning problem, i.e., fairness on a graph with missing attributes. The paper is well-organized and easy to follow.\n\n3.\tThe idea is new, and the proposed algorithm is rational.\n\nWeaknesses:\n\n1. Some works [1-4] are not addressed in the related work section nor in the experimental evaluation. In my opinion, the authors should compare their solution with these algorithms at least in the related work section.\n\n[1] Amer: A New Attribute-Missing Network Embedding Approach. TCYB, 2022.\n\n[2] Initializing Then Refining: A Simple Graph Attribute Imputation Network. IJCAI, 2022.\n\n[3] Graph Convolutional Networks for Graphs Containing Missing Features. FGCS, 2021.\n\n[4] Heterogeneous Graph Neural Network via Attribute Completion. WWW, 2021.\n\n2. Although this paper is well-motivated, the technique contributions seem a bit weak. The used techniques such as attention mechanism, adversarial learning, and auto-encoder have been widely researched in graph domains. I wonder the reason that why combining these components contributes more to the performance.\n\n3.  According to the results from ablation studies, the effectiveness of the proposed components seems unclear. For example, Table 2 can see no difference in the performance of some datasets.\n\n4. Explain if the metric is for one experiment over randomized trials, e.g., randomized initialization. The results in Table 1 and Table 2 would be stronger if the metric reported were mean/std.\n\n5. I would discuss the difference and the connection between the proposed model and existing graph fairness methods in theory.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Gwv0W4av58u", "reviewer": "Reviewer_sBeK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper presents a method (FairAC) to jointly addresses the graph attribute completion and graph unfairness problems due to both feature unfairness and topological unfairness due to missing attributes.\nThe model uses a set of $V_{keep}$ and $V_{drop}$ nodes as in Jin et al. (2001) and uses attribute completion with attention mechanism for nodes without features (this may introduce topological unfairness which   is handled by a sensitive classifier) and uses feature unfairness mitigation for nodes with attributes by removing implicit sensitive information that is present in non-sensitive attributes via an autoencoder. Fairness is measured through Statistical Parity and Equal Opportunity. \nThe experiments compare FairAC with several baselines on three datasets. It tests node classification accuracy, fairness w.r.t. sensitive attributes, and effects of sensitive attributes, missing rates, and ablations (attribute missing rate, adversarial training loss relevance, and the tradeoff hyper parameter $\\beta$).", "summary_of_the_review": "The paper has its pros, such as the relevance, the clear stated goals and evidence that seem to support the claim and the parsimonious solution to the complex problem. However, there are several imprecisions and some statements that seem to be not directly supported by the evaluation, such as the privacy statement on inference of sensitive information. \n\n%%%Post Rebuttal Comment%%%\nThank you for the answer to my questions. This clarifies my doubts and raise my score.", "strength_and_weaknesses": "With respect to the strengths, the paper is well organized, the problem is relevant to the ML community, particularly the graph-learning and GNN and network science communities. Clear goals despite some imprecisions in the definitions. Relative parsimonious model that deals with specific sub-goals to achieve the final aim of fairness in completion.\nThere are some areas where the paper could be improved. For instance, there are several imprecisions such as in the abstract where it is stated \"FairAC can be applied to any graph and generate fair embeddings”. The evidence provided is solid but stating that it will generate fair embedding to any graph is too optimistic. The definition of matrix $\\mathcal X$ is that it has a dimension of attributes $D$ yet each of the labels (and their predictions) are defined as a unidimensional $y \\in{0,1}$. The problem definition is a little hand-wavy. What is a fair feature embedding? The concept of “fair attribute completion model”  relies on fair feature embedding and, although it is discussed in other paragraph that it is measured via Statistical Parity and Equal Opportunity, the concept is not formally defined. The feature unfairness description regarding how “some non-sensitive attributes could infer sensitive information” seems not to be measured by Statistical Parity (SP) and Equal Opportunity (EO). The former implies also a privacy concerned while SP and EO deal with fairness of representation. Finally, the statement \"removing sensitive information implicitly contained in non-sensitive attributes\" has also the implication that sensitive information removed could affect performance when the amount of datapoint from subjects belonging to a minority group is not well represented. How is that scenario handled?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster