On Dyadic Fairness: Exploring and Mitigating Bias in Graph Connections
Authors: Peizhao Li
Yifei Wang
Han Zhao
Pengyu Hong
Hongfu Liu
Venue: ICLR 2021 Poster (2021)
Keywords: algorithmic fairness
graph-structured data

Abstract: Disparate impact has raised serious concerns in machine learning applications and its societal impacts. In response to the need of mitigating discrimination, fairness has been regarded as a crucial property in algorithmic design. In this work, we study the problem of disparate impact on graph-structured data. Specifically, we focus on dyadic fairness, which articulates a fairness concept that a predictive relationship between two instances should be independent of the sensitive attributes. Based on this, we theoretically relate the graph connections to dyadic fairness on link predictive scores in learning graph neural networks, and reveal that regulating weights on existing edges in a graph contributes to dyadic fairness conditionally. Subsequently, we propose our algorithm, \textbf{FairAdj}, to empirically learn a fair adjacency matrix with proper graph structural constraints for fair link prediction, and in the meanwhile preserve predictive accuracy as much as possible. Empirical validation demonstrates that our method delivers effective dyadic fairness in terms of various statistics, and at the same time enjoys a favorable fairness-utility tradeoff.

Published as a conference paper at ICLR 2021
ON DYADIC FAIRNESS: EXPLORING AND MITIGATING BIAS IN GRAPH CONNECTIONS
Peizhao Li', Yifei Wang', Han Zhao?, Pengyu Hong', Hongfu Liu' BBaadeis University, Uniiversity of Illinois at Urbana-Champaign (peizhacli, yifeiwang hongpeng, hongfuliu @brandeis. edu banzhao@illinois.co
ABSTRACT
Disparate impact has raised serious concerns in machine learning applications and its societal impacts. In response to the need of mitigating discrimination, fairness has been regarded as crucial property in algorithmic designs. In this work, we study the problem of disparate impact on graph-structured data. Specifically, we focus on dyadic faireess, which articulates fairness concept that predictive relationship between two instances should be independent of the sensitive attributes. Based this, we theoretically relate the graph connections to dyadic fairness on link predictive scores in learning graph neural networks, and reveal that regulating weights on existing edges graph contributes to dyadic fairness conditionally. Subsequently, we propose our algorithm, FairAdj. to empirically learn fair adjacency matrix with proper graph structural constraints for fair link prediction, and in the meanwhile preserve predictive accuracy much as possible. Empirical validation demonstrates that our method delivers effective dyadic fairness terms of various statistics, and at the same time enjoys favorable faimess-utility tradeoff.
INTRODUCTION
The scale of graph- srrph-structured data has grown explosively across disciplines (e.g., social networks, telecommunication networks, and citation networks), calling for robust computational techniques to model, discover, and extract complex structural patterns hidden in big graph data. Research work has been proposed for inference learning on potential connections (Liiee-Nooell & Kleinherg 2007), and corresponding algorithms can be used for high-quality link prediction and recommendations (Adamic & Adar 2003; Sarwar et al. 2001 Qi et al., 2006). In this work, we study the potential disparate impact in the prediction of dyadic re relationships between two instances within homogencous graph.
Despite the wide applications of link prediction algorithms, serious concerns raised by disparate impact (Angwin et al., 2016 Barocas & Selbst 2016; Bose & Hamilton, 2019a Liao et al. 2020 should also be reckoned with by algorithm designers. In an algorithmic context, disparate impact often describes the disparity in influential decisions which essentially derives from the characteristics protected by anti-diserimination laws or social norms. Unfortunately, this negative impact derived from biased data and conventional algorithms occurs in many applications including link prediction. One example is that a user recommender system follows the proximity principle (individuals are more likely interact with similar individuals) existing connections with intrinsic bias. Such an operating mode would deliver biased recommendations dominated by sensitive attributes. For example, users with the same religion or ethnic group are more likely to be recommended and consequently generate segregation in social relations by long-term accumulation (Hofstra et al.) 2017). Another example can noticed in news streaming. When a news app has collected the political profile from user, in pursuit of the user preference in news streaming, the system might only deliver politicking that the user is predisposed to agree with, therefore skews a user's scope and narrows the view by selectively displaying reality (Pariser 2011). To alleviate these concerns, an algorithm should perform a link prediction without being biased by the sensitive attribute of the two instances, and should also stream diverse and preferred recommendations.
user,
Motivated by the potential bias in real cases, in this paper we propose dyadic fairness for the link prediction problem in homogeneous graphs, where the dyadic fairness criterion expects the predictions

---

Published as a conference paper at ICLR 2021
to be statistically independent of the sensitive attributes from the given two vertices. We focus scope on Graph Neural Networks (GNNs), which have already shown remarkable capacity in graph representation learning by message passing along the graph structure (Xu et al. 2018 2020 Ying let al. 2018 Wang et al. 2019: Fan et al. 2019 Li et al. 2020). Within the pipeline of GNNs, given an arbitrary graph, we theoretically anal yze the relationship between dyadic fairnsss and the graph connections. Our findings suggest adapting weights on existing edges in graph can contribute to dyadic fairness conditionally. Continuing with our theoretical findings, we propose FairAdj, an algorithm to empirically learn fair adjacency matrix by updating the normalized adjacency matrix while keeping the original graph structure unchanged. Integrating with a utility objective function, the proposed algorithm seeks supplied dyadic fairness and link predictive utility simultaneously.
Our definition of dyadic fairness in a graph context inspired by the statistical metrics in group fairness (Dwork et al. 2012 Kusner et a 2017). First, vertices in a graph are categorized into several groups according to protected attribute. Then, the dyadic fairness criterion asks some standard statistics such as positive outcomes false positive rate on link score to be approximately equalized across intra and inter groups. Essentially, such a requirement asks for a more diverse prediction between and within different groups defined by the protected attribute, hence it also allows to mitigate social segregation by asking for more interactions across different protected groups in the graph.
Empirically, present studies six real-world social and citation networks to demonstrate the effectiveness of the proposed method. We conduct evaluations towards seven measurements of both utility and dyadic faimess. Comparing
other baseline methods (Kipf & Welling) 2016b] Grover & Leskoved 2016 Rahman et al. [201)] Bose & Hamilton 2019b). we consistently observe improvements from two aspects. First, dyadic fairness metries verify that our method can minimize the statistical gap between the predictions of intra and inter links. Second, in terms of utility, our results are consistent with the existing literature (Zhao & Gordon 2019 Fish al., 2016 Calders et al. 2009). that satisfying fairness can potentially lead to a decrease in utility. However, our algorithm enjoys a more favorable fairness-utility tradeoff (same fairness but less sacrifice in utility, and vice versa) when compared to previous works. Additionally, to approach the real application cases, we also showcase a direct product that comes from dyadic fairness: our method can effectively stream more diverse recommendations containing instances holding different kinds of sensitive attributes.
2 RELATED WORK
In this section we mainly review some closely related work in both fair machine learning and graph representation learning. We also briefly describe and discuss several existing works on learning fair node representations.
Fair Machine Learning. Various types of fairness notions have been proposed and studied, in- cluding group fairness (Kusner et al.) [017]] Kearns et al.) 2018 2019). individual fairness (Dwork) al. (2022). and preference- based notions Zafar al. [017a]] Ustun et al. 2019). Embracing these definitions, relevant algorithms involving fair constraints have been proposed. [Zemel et al. (2013)
propose a method to find good representation to maximize utility while preserving both group and individual fairness. Following works on fair representation learning
autoencoder (Madras ct al. 2018) or adversarial training (Zhao & Gordon 2019 Zhao et al., 2019: Edwards & Storkey 2015 Louizos et al. 2016) to simultaneously remove the sensitive patterns while preserving enough information for prediction. /Zffar et al. (2017b) optimize for decision boundary fairness through regularization in logistic regression and support vector machines, and some other works achieve fairness by optimal transport between sensitive groups (Gordaliza et al. 2019 Jiang et al. 2011)) and fair kernel methods (Donini al., 2018). However, most proposed learning algorithms for fairness are mainly built on independent and identically distributed data, which are not suitable to be directly applied to graph-structures data with dyadic fairness.
Graph Representation Learning. Representation learning graphs is formulated to convert structural graph into a www-dimessiona space while preserving the discriminative and structural representations. Efficient graph analytic methods (Von Luxburg, 2007 Tang et al. [0055] Perozzi ctt al. 2014, Grover& & Leskoved 2016; Xu et al.] 2019) can benefit a series of downstream appli- cations including node classification (Wang al. 2017), node clustering (Nie al. 2017), link
2

---

Published as a conference paper at ICLR 2021
prediction Zhang & Chen 2018) and graph classification as well. Recently, Graph Neural Net- works (GNNs) have shown remarkable capacity in graph representation learning, with emergent varieties (Kipf & Welling 2016a Veličković al. 2017; Hamilton et al. 2017) consistently deliver- ing promising results. Our work uses GNNs for graph representation learning but targets improving dyadic fairness in link prediction.
Fair Graph Embedding. As fairness in graph graph-structured data a relatively new topic for research, only a few studies have investigated the fair issues graph representation learning. Rahman et al. (2019) first proposed Fairwalk, a random walk based graph embedding method that revises the transition probability according to the vertex's 's sensitive attributes. Following the idea of adversarially removing sensitive patterns (Madras et al. 2018). Liao et al. (2020) proposed to use adversarial training on vertex representations to minimize the marginal discrepancy. This work mainly focuses on learning node representations that are free of sensitive attributes, which is different from ours. Other works includes fair collaborative filtering (Yao & Huang 2017), item recommendation (Steck) Chakraborty et al.! 2019) in bipartite graphs, and fair graph covering problem (Rahmattalabi
2018
et al. 2019).
3 PRELIMINARIES
Let G : E) as graph with a fix set of vertices V and edges E, where vertex features with M dimensions are represented by X E RNXM A nonnegative adjacency matrix A RN describes the relations between every pair of vertices. The element aru in A represents the weight on the linkage bridging v and u, and set to zero no link exists. Every vertex holds a sensitive attribute, and we use S(v) to denotes the sensitive attribute as well as the sensitive group membership of v. Let [(v) be the set of 1-hop neighbors of v including self-loop. Edge (v, u) is called intra S(v) = S(w). and inter implies (v)) 7 S(u). |S] denotes the cardinality of group S. For a binary sensitive attribute with two groups Sy and S separated from the graph, S. == {o S, [T)) n S1 + Ø represents the set of vertices in Sp which locate on the boundary and has connections with S1, and the same for S,. Set U to be the discrete uniform distribution over the set of vertices V. Suppose bivariate link prediction function g(...) TR x RD > R. that given two vectors of the embedded vertices representations, value is obtained showing the model belief that these two vertices are potentially linked.
Having these basic notations, we consider the disparity in link prediction bridging on intra and inter sensitive groups The general purpose of dyadic fairness is to predict links independently of whether two vertices having the same sensitive attribute or not. We extend from demographic parity (Edwards) & Storkey [2055] Kipf & Welling 2016b Madras et al. [018 Zemel et al.) (2133) to formulate a specific criteria for dyadic fairness. In a binary classification problem, demographic parity expects a classifier gives positive outcomes to two sensitive groups at the same rate. We turn the two groups in the content of demographic parity into the groups of intra and inter links. Ideally, achieving dyadic fairness will bring intra and inter link predictions at the same rate from a bag of candidate links.
Having vertices representation v and u, dyadic fairness can be mathematically formulated as Definition 3.1. A link prediction algorithm satisfies dyadic faireess if the predictive score satisfy
Pr(g(u, (u) S(v)) Pr(g(u, v) ())) + S(v))
To quantify the fairesss, we establish dyadic fairness on link prediction upon fixed set of vertices, and models the expectation of absolute difference in score outcome across the groups of intra and inter links. Note that we also comprehensively evaluate our model on fairness by other four statistics gap extended from (Hardt et al. (016)) in Section 6
4 HOW GRAPH CONNECTIONS AFFECT FAIRNESS
In this section, we propose chain of theoretical analyse established on a variant of demographic parity and graph neural networks to associate dyadic faimess with graph connections. We first
Proofs for the proposition and theorem are in Appendix
3

---

Published as a conference paper at ICLR 2021
demonstrate demographic parity in the outcomes of link prediction can be sufficiently reduced to the achievement of fair vertex representations when employing an inner product function for link prediction. Suggested by the sufficiency, reveal how the pipeline of one-layer graph neural network can affect the demographic parity, and draw the conclusion that for an arbitrary graph using GNNs for embedding, properly regulating the weights existing graph connections to faireess conditionally. The theoretical findings motivate our algorithmic design as presented in the next section. Without loss of generality, in this section, we consider the sensitive attribute be binary, where two sensitive groups Su and S1 can be separated from the graph, but show the cases with sensitive attributes in multiple categorical values in our experimental section.
contribute
Proposition 4.1. For a link prediction function g(-, -) modeled as inner product g(v, u) = v Eu, where Σ + is a positive-definite matrix, 3Q > O, Ve ~ V. | I Q, for E [v] E ERM, for dyadic fairess based on demographic parity, if |B [V L Sal E [v E Sill12 S 8,
APP == (u..))Uxull(( u) (vv) = S(u)] - ((e,))xXXU (e, S(x) # S(w)) S Q (2)
Remark 1. Proposition |.1 can be applied for a general inner product function in Euclidean space, where M directionally and differently scales two input vectors. When setting K to an identity matrix, function ((.-) reduces to dot product and is widely used in a series of research work on link prediction (Kipf & Welling 2016b Trouillon et al.. 2016 Yao & Huang 2017).
The above proposition implies fair vertex representations a sufficient condition to achieve demo- graphic parity in link prediction. Suggested by the sufficiency, the approach to faimess could be reduced to achieving vertex representations with small discrepancy between sensitive groups With the proposition, we are ready to proceed understand fairness within graph neural networks and reveal how the structure or connections of a graph could affect demographic parity.
A single layer GNN can be generically written as GNN, :- p (AXWo), where p is non- linear activation function, A is the normalized adjacency matrix, and Wo is the trainable weight matrix. One GNN layer can be decomposed into two disjoint phases: a vertex feature smoothing phase over the graph using A, and a feature embedding phase using Wo and p. Concretely, we consider left normalization A- = D- A (D is the degree matrix) for feature smoothing. Equivalently, at indi- vidual level, for each vertex it is one-hop mean aaan-agggrgattion Agg(U) (t) deg (v) Ever(e) Qvu U where deg,,. (v) ;= Ever(w) Ovn stands for the weighted degree of vertex v.
We respectively abbreviate En-u[ole E Sol and Evwu(olu E Si] as po and μr. Let a denotes the maximal deviation of vertex representations, namely, Vo So. ||e pollzo I a, and Ve E St, |V0 1114alle I a. Let D := max (v) be the maximal weighted degree in G. mw == Es())((())) Gun be the summation of weights on inter links. With these notations, we show how the discrepancy between pn and μn changes after conducting feature smoothing for one time over the graph.
Theorem 4.1. For an arbitrary graph with nonnegative link weights, after conducting one mean- aggregation over the graph, the consequent representation discrepancy between two sensitive groups A E (Agg(v) (v) E 5o] ( v E Si]lla is bounded by
max(aminn l|p00 - 111 0l 00
A
Ager S amax pn lll + 2v MMa, DP
(3)
where Ominn =min (a1,02) maxx Cma (01, .2), a1 =11 111 Den
S
15
|s
Remark 2. Thcorem 4.1 shows the lower and upper bound given by the graph structure and the maximum deviation a of vertex representations in each sensitive group on demographic parity after conducting one aggregation function on vertices. The contraction coefficient Quux is maximum of two absolute terms an and 0r2, where 02 is a constant predetermined by the graph connections. It is worth pointing out that although in the worst case ammx could be 1, e.g., in a complete bipartite graph, in most practical graphs it is strictly less than I, hence the above upper bound corresponds to a contraction lemma but under some additional error introduced by deviation a. We also provide several illustrative graph diagrams for the contraction of this theorem in Appendix [
To approximate demographic parity after feature smoothing. Theorem inspires a strategy to regulate the weights on graph connections to change on in Omax as minimize the upper bound
4

---

Published as a conference paper at ICLR 2021
Algorithm 1: Algorithmic routine for FairAdj
Input: vertex features X, adjacency matrix A, GNNs parameters learning rates do and ' Normalize adjacency matrix A D-1A
Fix the elements with zero in A and select the non-zero elements for optimization while 0 A has not converged do for t = 1 to Ti optimize for utility do
L Compute Cou by Eq. (),
+ VoLuil,
0 0 + (0)
for to T2 optimize for fairness do
Z <- GNN, A),
A ZZ reconstruet graph connections
Compute Ciair by Eq. 6 97 + V Stirr
for v = 1 to projected gradient descent do
Sort non-zero elements in [Ā n5galu. in descending order: e1 2 e2 ep.
- 1ز=1 1(e, +1 e.) 2 0) 1())the indicator function
B (1- E.- 4)
for v = 1 to n> update Ā
do
[ + max n + 8, 0}
Output: Link predictive score between vertex and <- sigmoid(GNNo(v,. A) GNNo(u, A))
for one-layer mean-art meennaggreggttinn. For term 01, obviously if the summation of inter weights are too small (me 0) or too large (Ma - D. min minl [S]]). will approximate to This indicates that increasing the weights on inter links cannot always guarantee to achieve better demographic parity although inter group connections are always the minority in links, but should regulate this part to proper range depending on the size of sensitive groups and the connected situation of a graph.
We combine the upper bound with the second feature embedding phase. Here we denote n == En~u (G.N((v,, A) v e St], 0, 1, Q' == sup [I (v, A)llz
V}.
Corollary 4.1. For App on vertices after passing one layer GNN, (X, Ā) = PAXXW)) we have:
APp < Q'122122 lpóó willa s @223 (allиo M1ll2 + 2VMa),
(4)
where is the Lipschitz constant for The first inequality holds by Proposition 4.1 the second one is by Theorem[4.1] and the definition of spectral norm and Lipschitz constant, also realizing that Q' < W Multiple layers of GNNs can be reasoned out similarly.
From the above theorem, see App be processed with a tighter upper bound by regulating the weights on edges, and it is also dependent on the property of Wg. p. and the error term ((a). When setting We fixed, our theoretical findings provide feasible solution that regulating weights on graph connections can achieve better demographic parity on link prediction, and as supplementary, also indicate where or when it cannot perform well with finite layers of GNNs: (1) The solution cannot guarantee arbitrary fairness if we want to preserve the graph structure due to the resistance of ag in lower bound in Theorem 4.1 (2) When it is already fair enough in the original graph data, which means || / la is small and additional error ((a) is comparable to it, the upper bound cannot be reduced significantly and the solution may not further mitigate the bias. We include dataset to investigate the potential limitations empirically in response the above analysis in Appendix [ In the following sections, we implement the inspired algorithm and demonstrate that multiple real-world networks accept this solution with favorable results and better fairness-utilin tradeoff.
5

---

Published as a conference paper at ICLR 2021
5 LEARNING FAIR GRAPH CONNECTIONS
The above discussion indicates that when employing GNNs for graph embedding, adjusting the adjacency matrix can assist the model with achieving faimess conditionally. However, searching for the optimal adjacency matrix within hierarchical graph neural networks is non-trivial problem. In this section, continuing with the preceding analysis, we develop FairAdj algorithm to adjust the graph connections and learn fair adjacency matrix by updating A while preserving the original graph structure unchanged. In overview, we implement the algorithm by separately optimizing the parameter We of GNNs towards utility, and adjusting A towards dyadic faimess by gradient descent and empirical risk minimization with structural and right stochastic constraints. Therefore, FairAdj able to pursue the supplied dyadic fairness and link predictive utility simultaneously.
We employ variational graph autoencoder (Kipf & Welling 2016b) for feature embedding. A two-layer graph neural network is used inference model (- Z denotes the embedded representations, and dot product between embedded representations is the generative model p(-). The KL-divergence term KL L-II- punishes the discrepancy between latent distribution and a Gaussian prior. The objective function to reconstruct graph connections from latent variable can be written as:
max
Cuil := LE ((A| Z)] K KLGGNN (Z) X,A)),, 1)].
(S)
For fairness, we impel Ltair to empirically seek for better graph connections, then update Á with constraints. Specifically, we optimize the normalized adjacency matrix À as follows:
min Ltair == ||Ee,u-Ux S(e)) S(u) E, u~ S(v) * S(u]I1
A
(6)
s.t. (1). = 0, if [f 0, (2). A1 = 1, Ā 0,
where avu. takes value in Á = Z2T and is the all-one vector with size N. The two constraints are necessary for optimizing A: (1) Elements with zero value should be maintained, meaning no new links can be established during optimization. This restriction is proposed to preserve utility, due to adding fictitious links might mislead the directions of message passing, and further corrupt the representation learning. Therefore, we only adapt weights on existing edges and preserve the original graph structure. (2) In consistent with the initial left normalization A = D-1 A, the optimized matrix should still remain a right stochastic matrix. This can restrict the largest eigenvalue of adjacency matrix || 1, hence avoid numerical instabilities and exploding gradients when training Wa towards Lun In practice, we observe explosions during training with no constraints applied on À.
For the first constraint in Eq. (6), we only compute gradients and update the elements in À which have non-zero initialization. For the second one, after selecting the variable to optimize, we employ projected gradient descent by (Wang & Carreira-Perping minimizing Ltair- Once given computed gradients on A denoted V Viaiir with the corresponding learning rate 77 we have the following optimization problem that update by projecting Ā "A V frair into the feasible region with the minimum Fuclidean distance:
2013) to satisfy the constraint while
ΣιlĀ 7 V V [A (1 V.VVVla T GTair)o,.+1 10,,
min À- V
S.L. (A
and Ā (1 Crain) 20,
where [Ā]e,, are the wiwewise elements for A. namely, all the connections the update for À after projection. Since Á is row-wise independent and the objective function is strictly convex for this quadratic progra, there exists unique solution for each row. Solution details for projected gradient descent are restated as a part of our algorithmic pipeline.
Á (nA a Crar
The algorithmic routine is elaborated in Algorithm 0 and Á are optimized iteratively with T, and T3 epochs for co-adaatation. Compared adversarial training method on graph embedding (Bose) & Hamilton] 2019b), which requires hyperparameter to control the fairnes--ttiltyy tradeoff. we also find regulating the convergence of A has similar effect well. That is because the more Á changes, the further À is away from the original graph connections, and consequently, the more

---

Published as a conference paper at ICLR 2021
Table Statistic for datasets in experiments.
Dataset
# Vertex
# Edge
Class
# Intra
Inter
Intra Ratio
Inter Ratio
Dis. Ratio
Oklahoma97
3,111
73,230
2
46,368
26,862
1.92e-2
1.11e-2
1.73
UNC28
4,018
65,287
2
36,212
29,075
8.76e-3
7.38c-3
1.19
Facebookd1684
786
14,024
2
7.989
6,035
4.76e-2
4.30e-2
1.11
Cora
2,708
5,278
7
4,275
1,003
6.51e-3
3.30e-4
19.73
Citeseer
3,312
4,660
6
2,089
2.571
2.13e-3
5.70e-4
3.74
Pubmed
19,717
44,327
33,443
10,884
4.80c-4
9.00c-5
5.33
Table 2: Experimental results on UNC28.
Method
AUC 1
AP1
App 4
Arne 4
Atale 4
ApaR +
ÂYNR +
VGAE
87.63 0.56
88.69
= 0.65
2.24 +: 0.42
1,50 +
0.44 +
7.62 084
2.18 : 0.72
node2vec
87.22 + 0.30
87.10
+ 0.37
2.75
+: 0.78
1.30 4: 0.53
1.05 # 0.93
12.56 +: 1.12
2.24 4: 0.92
Fairwalk
87.18
+: 0,30
87.07
= 0.37
2.79 0,70
1.17 0.99
0.90 0.9
12.71 + 1.11
2.20 + 0.96
FairAdiiz-s
86.98
87.75 + 0.65
1.53 + 0.35
0.32 + 0.29
0.41
2.84
2.22 + 0.68
FairAd]yz=20
87.04 0.55
87.80 +: 0.65
1.57 +: 0.36
0.34 + 0.31
0.42 +: 0.35
2.76 + 0.75
2.16 +: 0.73
damage in utility but more enhancement in fairness. Thanks to this favorable property, in experiments, comparing to adversarially remove sensitive attributes, we present multiple options for T- to control the convergence and observe a more favorable -airnes--utiltty tradeoff shown by our method.
6 EXPERIMENTS
We present empirical analysis on six real-world datasets, compared with baseline methods in terms of seven evaluative metrics on both fairness and utility. Approaching to applications, we testify that our method can enhance the diversity in recommendations. Due to the space limitation, only showcase partial results but defer the rest in Appendix D Moreover, as an intermediate result, we demonstrate vertex representations embedded more fairly assessed by fair clustering in Appendix B
6.1 SETTINGS
Datasets. We conduct experiments on real-world social networks and citation networks including Oklahoma97, UNC28 (Traud et al. 2011). Facebookff 1684 Cora, Citeseer and Pubmed Okla- homa97 and UNC28 are two school social networks. A link represents friendship relation in social media, and every user has a profile for vertex features, including student/faculty status, gender (sensitive attribute), major, etc. Facebookt 1684 is a social ego network from Facebook app. As the rest three citation networks, each vertex represents an article with bag-of- descriptions as features. link stands for citation regardless the direction. We set the category of an article as the sensitive attribute. Statistic for datasets summarized in Table where #Class is the number of sensitive groups, #Intra/Inter Ratio represents the ratio that the number actual intra/inter links v.s. the number of links if the graph is fully connected. These two terms show the density of intra/inter links. Dis. Ratio (abbreviated from disparity ratio) is calculated by divide intra ratio into inter ratio. Dis. Ratio equaling to implies intra/inter connections are perfectly balanced in existing graph, and the degree of deviation from indicates how skew the link connections are.
Baselines and Protocols. We involve four baseline methods. Variational graph autoencoder (VGAE) (Kipf & Welling 2016b) inherits from variational autoencoder, which uses two GNN- layer as the inference model and leverages latent variables to reconstruct the graph connections. Node2vec (Grover & Leskovec 2016) is widely used graph embedding approach based on random walk. Fairwalk (Rahman et al. 2019 is built upon node2vec and designed specifically for fairness issues. It modifies the transition probability for one vertex according to the sensitive attribute of its neighbors. The last one is adversarial training on vertex representations (Bose & Hamilton 2019b), which aims to minimize the discrepancy between different sensitive groups by optimizing parameters in GNN. Besides the standard pipeline for utility, it additionally trains the networks to confuse a discriminator, meanwhile training the discriminator to distinguish the embedded features with different sensitive attributes. A hyperparameter À is used in the overall objective function balance
7

---

Published as a conference paper at ICLR 2021
Table Experimental results on Citeseer.
Method
AUC 1
AP
Aue
Aque +
A +
ApeR
AINK
VGAE
81.77 + 1.25
85.57 = 1.39
11.24 # 1.83
3.37
2
2.14 = 1.26
10.81 336
11.31 = 2.99
node2vec
81.21 # 1,35
84.69
= 1.26
14.49
# 3.38
4.02
2.74
6.82 = 4.62
7.37 = 1.07
12.50 4.21
Fairwalk
81.69 +: 1,50
84.97
= 1.23
13.50
+: 2,97
3.30
2:49
5.33
3.83
7.26 3.30
11.34 a: 3.19
yairAdjyz-2
80.45 1.34
84.47
1/43
9.57
2.55
2:20
1.70
9.87 3.17
10.27
3:23
yyir
78.84 + 1.38
82.74 1.46
7.81
1.85
1.06
1.30
9.22 =
10.01 3.13
6.9
0.85
lambda/12
lambda=1
lambde-5
0.8
bmbda/12
fambda=110
bmbbd=1
bmbda-5
0.75
de-
20
C.7
bmbda-11 10
bmbbd-20 20
1mmbda-30
0.6
lumbde-50
72-1
0.65
72-10
72=2
-2-20
72:55
6.5
72=10
T2=20
0.55
0.02
0.03
0.04
0.05
0.06
0.05
0.15
Ay
Age
Figure 1: Comparison with adversarial training method (Bose & Hamilton, 2019b) in terms of the tradeoff between utility and fairness. Left: UNC28; Right: Citeseer. Blue points denote FairAdj with different T2 values, red points represent (Bose & Hamilton 2019b) with different À values.
the tradeoff between utility and faimess. We vary À in experiments and make comparisons to various results given by adversarial training. For all experiments, we randomly remove 10% links from the graph and reserve them for evaluation, and equivalently, the same number of false links are sampled in the evaluation phase. For one dataset, we repeat experiments with different train/test splits for 20 times. Full experimental configurations are available in Appendix C
Metrics. We evaluate the utility of link prediction using Area Under the Curve (AUC) and Average Precision (AP). Fairness is evaluated towards App, as well as the disparity on the expected score on all the true samples Arre and false samples Aaale- Besides these, following the suggested fairness notions (Hardt et al. (2066), we compute the maximum gap of true negative rate (TNR) and false negative rate (FNR). Illustratively, let the conditional cumulative distribution function of score R be evaluated by a threshold т with a given label written as (T) := ((j (0, 1}, SE (intra, inter). With these notations, the maximum gap in true negative rate can be expressed as ATNR == max, [-
(T)]. and similar for false positive rate APNR max, (T) (r)nterr)] These two terms also reflect the disparity in true positive rate (TPR) and false positive rate (FPR) due TPR FNR and FPR TNR.
6.2 RESULTS AND ANALYSIS
Table list quantitative results on UNC28 and Citeseer comparing to VGAE, node2vee, and Fairwalk. Two choices of T2 are presented here, where T2 in smaller value pursues comparable performance in utility (a little bit lower in AUC but higher in AP) to random walk based methods, and at the same time performs much better in faireess. We also present T2 20 since observe convergence on the adjacency matrix. The results indicate that FairAdj achieves the best on various statisties for dyadic fairness and with only small sacrifice in predictive utility.
A Better Tradeoff. Figure SesureDloor plots every experimental result for our method and adversarial training with various fairness-utility regulated hyperparameters. Two observations explain why our method surpasses the adversarial technique. (1) Blue dots closer to the left top corner than the red on the whole, meaning the same level fairness is achieved with less sacrifice in utility. An explanation for this favorable property is that, the adversarial training method neglects the graph connections and
8

---

Published as a conference paper at ICLR 2021
diveraity
aiilly
uiikyy
1.03
methoo
method
FalrAd] T2-3
VGAS
0.99
3.0
Fairdd] T2-3
VGAE
0.99
Farrkd] T2-10
Fainkdj T2-10
Fairdej
2,5
Faindej
intar V.S. b.tta
0.98
Indr V.5 Inta
0.98
0.8
2.0
recal
0.97
0.07
0.7
1.5
mothod
0.8
0.96
VGAE
0.93
VGAE
FeliAd] T2-5
FelrAdi T2-5
0.3
FelrAd] 12-10
FeirAdi T2-10
0.95
Feindhi 72-20
Fatrldi 12-20
0.05
0.30
0.15
0.20
0.05
0:30
0.15
0:20
0.05
0.30
0.35
0.20
0.05
0.10
3.15
0.20
proportion
proportion
propertion
proportion
Figure 2: Diversity and utility in recommendations. Left: UNC28; Right: Citeseer. X-axis 'propor- tion' means we investigate the top x% valued links and check the ratio between inter and intra links that presented in y-axis.
only diminish the group discrepancy, where two irrelevant instances with no connection but from different groups may be closely mapped, thus greatly damage the utility. The optimization on A does facilitate the feature smoothing across groups which is not indicated in the original adjacency matrix, but still considers the graph connections. (2) Additionally, blue dots are more aggregated, suggesting methods escape from the instability of min-max optimization and acting more robust different train/test splits. However, as shown, FairAdj cannot achieve arbitrary small in App as red dots do. This is indicated in Section 4 as the first potential limitation.
Diversity in Recommendations. We examine the top-scored links in evaluation at a certain pro- portion in terms of its diversity and utility, shown Figure This exploration can be useful when conducting recommendations according to scores in descending order. For a fixed proportion, we report the diversity as the number of inter links divided by the number of intra links, and the utility as the recall rate among these recommendations. Figures show that direct product by dyadic fairness, FairAdj enhances the diversity in recommendations but is achieved at a sacrifice of utility.
7 CONCLUSION
We studied the dyadic fairnsss in graph-structured data. We theoretically analyzed how the con- nections in graph links affect dyadic fairness of demographic parity when employing graph neural networks for representation learning. On the basis of the foregoing analysis, we proposed FairAdj to learn fair adjacency matrix, and pursued the dyadic faimess and prediction utility simultaneously. Empirical validations demonstrated the achievement of fairness and a better fairness-utility tradeoff.
ACKNOWLEDGEMENT
We would like to thank Zizhang Chen and Wei Lu for the helpful discussions, and Lizi Liao for providing the Oklahoma977UNCC2 datasets. This work is partially supported by NSF OAC 1920147.

---

Published as a conference paper at ICLR 2021
REFERENCES
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3):11-2300, 2003.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. ProPublica, May, 23: 2016, 2016.
Solon Barocas and Andrew D Selbst. Big data's disparate impact. Calif. L. Rev. 104:671, 2016.
Avishek Bose and William Hamilton. Compositional fairness constraints for graph embeddings. In International Conference Machine Learning, pp- 715-724. PMLR, 2019a.
Avishek Bose and William Hamilton. Compositional fairness constraints for graph embed- dings. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th In- ternational Conference on Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pp. 715-724, Long Beach, California, USA, 09-15 Jun 2019b. PMLR. URL htttp://procediing ngs m wwwppprsssvveem ppwpsp/////o/selll111 ht.l
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference on Data Mining Workshops, pp. 13-18. IEEE, 2009.
Abhijnan Chakraborty, Gourab K Patro, Niloy Ganguly, Krishna P Gummadi, and Patrick Loiseau. Equality of voice: Towards fair representation in crowdsourced top-k recommendations. In Proceedings the Conference on Fairness, Accountabilityy and Transparency, pp. 129-138, 2019.
Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pontil. Empirical risk minimization under fairness constraints. In Advances in Neural Information Processing Systems, pp. 2791-2801, 2018.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Faimess through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226, 2012.
Harrison Edwards and Amos Storkey. Censoring representations with adversary. arXiv preprint arXiv:1511.05897, 2015.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pp. 417-426, 2019.
Benjamin Fish, Jeremy Kun, and Ádám D Lelkes. A confidence-basee approach for balancing fairness and accuracy. In Proceedings of the 2016 SIAM International Conference Data Mining, pp. 152-152. SIAM, 2016.
Paula Gordaliza, Eustasio Del Barrio, Gamboa Fabrice, and Jean-Michel Loubes. Obtaining faimness using optimal transport theory. In International Conference Machine Learning, pp. 2357-2365.
2019.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pp- 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in neural information processing systems, pp. 3313-3323, 2016.
Bas Hofstra, Rense Corten, Frank Van Tubergen, and Nicole B Ellison. Sources of segregation in social networks: A novel approach using facebook. American Sociological Review, 82(3):625-656. 2017.
Ray Jiang, Aldo Pacchiano, Tom Stepleton. Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classification. arXiv preprint arXiv: 1907. / 12059, 2019.
10

---

Published as a conference paper at ICLR 2021
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimess geirymandering: Auditing and learning for subgroup fairness. In Interaational Conference on Machine Learning. pp. 2564-2572, 2018.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. An empirical study of rich subgroup faimess for machine learning. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 100-109, 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1609 0.09,02907, 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07300 2016b.
Matt J Kusmer, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual faimeess. In Advances in Neural Information Processing Systems, pp. 4066-40766 2017.
Peizhao Li, Han Zhao, and Hongfu Liu. Deep fair clustering for visual learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattem Recognition, pp. 9070-9079, 2020.
Peiyuan Liao, Han Zhao, Keyulu Xu, Tommi Jaakkola, Geoffrey Gordon, Stefanic Jegelka, and
Ruslan Salakhutdinov. Graph adversarial networks: Protecting information against adversarial attacks. arXiv preprint arXivv2009. / 13504, 2020.
David Liben-Nowell and Jon Kleinberg. The link- mmk-prrdiction problem for social networks. Journal of the American society for information science and technology. 58(7):1019-1031, 2007.
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard S. Zemel. The variational fair autoencoder. In ICLR, 2016. URL
awtaaassbb111 00830
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. arXiv preprint arXiv: 06309, 2018.
Feiping Nie, Wei Zhu, and Xuelong Li. Unsupervised large graph embedding. In Thirty-first AAAI conference on artificial intelligence, 2017.
Eli Pariser. The filter bubble: How the new personalized web is changing what we read and how think. Penguin, 2011.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions, In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Yanjun Qi, Ziv Bar-Joseph, and Judith SeithSeetharrm.. Evaluation of different biological data and computational classification methods for in protein interaction prediction. Proteins: Structure, Function, and Bioinformatics, 63(3):490-5000 2006.
Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang, Fairwalk: towards fair graph embedding. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 1188993295.. AAAI Press, 2019.
Aida Rahmattalabi, Phebe Vayanos, Anthony Fulginiti, Eric Rice, Bryan Wilder, Amulya Yadav, and Milind Tambe. Exploring algorithmic faimess in robust graph covering problems. In Advances in Neural Information Processing Systems, pp. 15750-15761, 2019.
Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th international conference on World Wide Web, pp. 285-2992 295, 2001.
Harald Steck. Calibrated recommendations. In Proceedings of the 12th ACM conference on recom- mender systems, pp. 154-162, 2018.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: information network embedding. In Proceedings of the 24th international conference on world wide web, pp. 1067-1077, 2015.
Large-scar -calee
11

---

Published as a conference paper at ICLR 2021
Amanda L Traud, Eric D Kelsic, Peter Mucha, and Mason A Porter. Comparing community structure to characteristics in online collegiate social networks. SIAM review, 53(3):526-55) 543, 2011.
Théo Trouillon, Johannes Welbi, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. International Conference on Machine Learning (ICML), 2016.
Berk Ustun, Yang Liu, and David Parkes. Fairness without harm: Decoupled classifiers with preference guarantees. In International Conference on Machine Learning, pp. 6373-6382 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint S.Iv:1710.100000 2017.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-16, 2007.
Weiran Wang and Miguel A Carreira-Perpinán, Projection onto the probability simplex: An efficient algorithm with simple proof, and an application. arXiv preprint arXiv:1309.1541, 2013.
Xiang Wang. Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. Neural graph collaborative filtering. Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval, pp. 165-174, 2019.
Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. Community preserving network embedding. In Thirty-first AAAI conference on artificial intelligence, 2017.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. Gromov-waserssein learning for graph matching and node embedding. International Conference on Machine Learning, pp. 0932-6941, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00822 2018
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanic Jegelka. What neural networks reason about? In International Conference on Learning Representations, 2020. URL httptttts:////peeeeettt
net. www.:ooommmmmmrrrm
Sirui Yao and Bert Huang. Beyond parity: Fairness objectives for collaborative filtering. In Advances in Neural Information Processing Systems, pp. 2921-2930 2017.
Rex Ying. Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp- 974-983, 2018.
Muhammad Bilal Zafar, Isabel Valera, Manuel Rodriguez, Krishna Gummadi, and Adrian Weller. From parity to preference-based notions of fairness in classification. In Advances in Neural Information Processing Systems, pp. 229-239, 2017a
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fairness constraints: Mechanisms for fair classification. In Artificial Intelligence and Statistics, pp. 962-970. PMLR, 2017b.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International Conference on Machine Learning, pp. 325-333-333333 2013.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
Han Zhao and Geoff Gordon. Inherent tradeoffs in learning fair representations. In Advances in neural information processing systems, pp. 15649-15659, 2019.
Han Zhao, Amanda Coston, Tameem Adel, and Geoffrey J Gordon. Conditional learning of fair representations. arXiv preprint 1xX1v:1910.07112,200 2019.
12

---

Published as a conference paper at ICLR 2021
In Appendix, present proofs in Section illustrative diagrams for Theorem 4. in Section B
experimental configurations in Section C deferred results in Section D and the demonstration of fair vertex representation in Section
A
PROOF
Proposition 4.1. For link prediction function .(.,)) modeled inner product g(v, u) v Eu,
where Σ E $ is a positive-definite matrix, =Q > 0, Ve ~ V, | 2 S Q, for E [v] E M for
dyadic fairness based demographic parity, if | [v E So) E (u Silll2 8.
ADP
E (0 u) S(v) S(u)] E B(o,)) ((()) * S(w)l Q @ 8. (2)
Proof. To simplify the notations, we use p Eu-olu | Si] E Rd to denote the expectations in representations for So and Si respectively.
E So] RM and == Ey~ulu uee
Binta
Emnterl
Elu Eu
E So, E S1]
Biu
Eu v So, u So Voe u Sil
|
|S
p Eg Eq
| + 11
P
T
Ep
| 2 + |S| |
Dg
1
|
(q T)T
Ep
| + |S Eg
1 + |
To simplify the notation, we will use a = |So1 2/|5/ + +1S113
and B 3= //12/([SSo +111?
$ ||4 pll2 1|EEp 3Egl2
88. |0| (1lopl12 + (13al12)
=Q E|| -,
which completes the proof. The first inequality above due Cauchy-Schwarz and the second one is by the definition of spectral norm. The last equality holds by the linearity of expectation: if Yu E V. || S Q, then |[[[]]|2 S ||[|o|1 [2] Q.
Theorem 4.1. For arbitrary graph with nonnegative link weights, after conducting mean- aggregation over the graph, the consequent representation discrepancy between two sensitive groups | v E Sillla is bounded by
Agur = |lE-olAAg(e
So]
DP
max(amii l|p0 μa 12lloo 20,03 0} S AP I 1maxl1/4 MIlla 2V 2VMo,
Ager
where Ommin -minfamnnaa-a ) mmaxxmmxxxaff a1 a2), a1=|1
m= Dum
1ol
02
50
81
Proof. The feature representation of u after conducting one meen-aggreeattinn is
Agg(v) deg
Σ
a 24 +
Σ
ava u).
deg
(E)("))
wET(u)
wEr(unss
Here separate the summation of neighbor features into two parts in terms of the sensitive attribute.
We use the bracket notation to abbreviate the range of a vector. That is, if a vector u satisfies J u μ + a, we abbreviate this
[N + o).
Consider the unilateral case v E Sg. we have
Agg(e) E Ever(wyns
(u) aeuto + Ever(wyns (v)
avalt + a 1]
E [(10 Ever(uins avu
(MI Ho)) o 1]
deg,,(u)
where 1 is the all-one vector with proper size.
13

---

Published as a conference paper at ICLR 2021
The first derivation is due to the fact that each Sy lies in the range of [ng to- 1] and each Si lies in the range of [P1 = a. 1]. The second one by the definition weighted degree.
Using B. LveT())s avu/deg, (v) where Sopp(u) is the opposite sensitive group where belongs. The expectation of Agg(v) for Sq
E (Ag((v) E Sol E I( |Sol
Σ
(No + Be(111 (oo)) + a 1]
vESu
[HH + E
Bo(11 (o)) + 1].
|So
vESa
And for v E S1 we have
B (Agg(u) |o E S1] E [(1 +
Σ
Bo(Ho m1)) + a 1).
[S
wES1
Based on the above two terms, the gap in expectation of two groups after passing one mean- aggregation layer becomes
1
Eesu (Agg(v) E Sol BEowo/Agg(0) Si] [[1 (11-(15) (1s0 |So
Σ B
Σ
B.))
(no - p1) 20 1).
S
rESo
vES1
Next we study the range of a' == 1 ( Eves, Br + +111 Eves, 3o). First we consider the
term Exeso S.. Since deg,, (v) S D maxx Yu E V, we have
B Ever(r)ss avu deg,, (v)
Σ
ma
avu
D
Dmax ve uEL(v)nS:
Dmax
rESp
#E8o
For non non-negativv weights,
D (v)
Σ avu +
Σ
Qva
avn-
uEI(v)~8p
uEI(v)nS,
wEI(w))S;
This means for E So.
Σ Euer(w)ss, aeu
B,
< 1,
deg (1)
thus,
Σ B Σ Br S Spl.
vESo
v
The first equality holds because B. 0 when So/S,, meaning doesn't contain any inter-edges.
Since the analysis for S₁ is similar, we derive the lower and upper bounds for "'EEs, Bur 0,
B
S
i 1.
S
max
S.S
S
vES;
Based on the above results, we give the bound for a' as follows:
a' E
So
S
Ma
[Sol +
| ),
1
So
S
Dmax
Let Ocmin and Omax be lower bound and upper bower of la'l, we have
Omax max(1
S
1
maw
}}
[S0]
[
D max
[So]
S.S
S
mew
1
1
Qmin min(1
+
+
|80]
SS
D
S.00
|S|
14

---

Published as a conference paper at ICLR 2021
Thus give the upper bound of App".
A S O'max 10max1100011111 - 141l22 2/Mo
where the second part RHS is due to 2a 1 22
Next consider i-th entrance po and μl, denoted μá and μ respectively. The i-the entrance of Eu Agg(() e So] - EEsuo(Agg(" E Si] take nonzero values if and only if
[1 (
B
Σ S
B₂)) (mb +i)l z 20
S
Thus obtain the lower bound of A Ager
DP
Aggr DP
2 max (Otmin - /41 /alloc - -20, 02
which completes the proof.
B COMPLEMENTARY DIAGRAMS TO THEOREM 4.
We provide diagrams help better understand the upper bound in Theorem 4.1
Figure provides a common case that the gap in expectation between two sensitive groups shrinks after agggeggggeg Here the maximal deviation term can be neglected since it is much smaller than the expectation gap.
Figure provides
that the term sensitive groups. Here a = 100 and the gap equals to 0. After aggregation, we see the new expectation gap becomes 20, showing that the discrepancy in representations increases.
negligible against the expectation gap between two
Figure 5 provides another case that the contraction coefficient a equals to due to the resistance of 0g2 Here all vertices possess inter links, and the graph is complete bipartite graph. Then the aggregation fully exchanges the sensitive information, and thus the representation discrepancy remains unchanged.
Cases in Figure 4 and 5 are also pointed out by the analysis in Section 4
(12)
(-12)
(5.6)
(-5.6)
mean-agg
2
8
6
8
(10)
(8)
(-8)
(-10)
(11)
(4)
(-4)
(-11)
(10)
(-10)
(4)
intra link
inter link
Figure 3: An illustrative graph example with two protected groups So and S,. All vertices have self- loop. The expectation gap shrinks after mean aggregation. Here, [Ep=e [ule E Sn) Ep-u [u|u Si] 20, a 2 and all link weights are equal. After aggregation, |E [Agg(v)] E So)
Em- (gg(v))) E Si]l |6.15 (-6.15)] = 12.3 < 20.
15

---

Published as a conference paper at ICLR 2021
(100)
(20)
(0)
mean-agg
(0)
(0)
(0)
(50)
(50)
3
(0)
(-100)
(0)
(0)
Figure 4: Case 1: The maximal deviation term (a) is not negligible. Here a = 100 and all link
weights are equal. All vertices have self-loop. [ folu E So) [olu E S1]] 0. But after
mean-aggregation, |Ee- [g E So] E Agg (u E Si]l 15 25 20 > 0.
(f4
(112
(k2)
5 (R1)
(14)
(#2)
(112
6 (#1)
mean-agg
(14)
3
(122
(
(M1) )
(11)
(122
(1u2)
(11)
Figure 5: Case 2: The contraction coefficient equals 1. This happens when the graph is complete bipartite graph. Mean-aggregation fully exchanges the sensitive information and the gap of two groups remains unchanged.
C EXPERIMENTAL CONFIGURATIONS
For all experiments, we set Ti = 50 and the total epochs which contain Ti and T3 equal to 4. Graph neural networks are applied with two hidden layers with size 32 and 16 respectively. ne is set 0.01. For n for different datasets, we have: Oklahoma97: 0.1; UNC28: 0.1; Cora: 0.2; Citeseer: 0.5. Experiments are conducted on Nvidia Titan RTX graphics card.
D ADDITIONAL RESULTS
We present experimental results for Citeseer and UNC28 in this section. All the results deliver similar conclusions as we state in the main body of this paper. Additionally, we include another dataset Facebook# 1684 response to the second limitation as indicated in Section 4 In this case, App, Amee Aaase are already small as given by VGAE, and FairAdj is not able to further minimize the gap.
Table 4: Experimental results on Oklahoma97.
Method
AUC
AP
App |
Amne +
Atsio
Aper +
ATNR $
VGAE
90.13 0.32
91.24
0.37
8.73 0.88
8.56 104
0.40
36.51 + 1.11
2.26
node2vec
86.49
84.09
7.23 +
3.35
+ 0.4
1.08 +
32.55 +
2.36 +
Fairwalk
86.56 1: 0.32
84.23 1 0.44
7.31 1: 0.62
3.49 1 047
1.13 0.5
32.77 +: 1.00
2.18 = 0.69
FairAdjmz-s
84.92
85.07 0.2
3.60 + 0.35
0.40 0.3
0.33 0.28
4,00 +:88
2.02 0.76
FairAdjmz=20
81.01
80.79
2.96
0.38
0.32
5.61
2.03
16

---

Published as a conference paper at ICLR 2021
Table Experimental results on Cora.
Method
AUC f
AP
Apr +
Ague +
Afalse
DYNK
AENK
VGAE
88.48 0.88
90.81
0.78
74
1.11
9,99
1 2.3
10.26
1. 1.39
28.25
4.46
26.71
3.83
node2vec
87.93
0.75
87.82
1.06
39.99
2:15
6.63
1: 358
27.86
1: 4.94
23.66
4.73
32.96
5.24
Fairwalk
88.04
0.84
88.10
1.20
40.49
#:5
7.30
+ 3.28
29.43
4.86
23.74
4.19
33.79
5,08
Fuis
86,00
1.12
88.32
21.05
6,99
2:24
6.14
1.59
20.72
3.62
19.46
3.62
83.85
1.07
86.08
17.87
5,40 2.25
3.74 1.46
16.75 4
15.37 3.84
Table 6: Experimental results on Pubmed.
Method
AUC
AP
Aur +
Auee
Atals 4
AYNR
ATNK
VGAE
91.20 a 0.85
91.26 a: 0.00
20,88 a 1.48
4.19 a: 0.93
8.04 a 1.83
12.01 2:29
19.18 a 4.16
node2vee
74.27 = 1.23
79.24
1.29
19.14
0.93
3.38
+ 2,57
8.90 2.56
6.65 2211
10.91 1.88
fairwalk
73.43 1.11
78.96
1.24
18.42 1.65
3.11
= 1.84
7.79 + 3,49
6.61 2.28
10.93 2.54
FairAdj
88,64
88.21 =
16.06
1.96
0,82
4,40
8.93
12.75
FairAdi12=
87.53 =
87.10
14.73
1.39 +
3.17
9.09
10.46
6.9
Labbd/72
lambd=1
6.8
0.03
lambda
1m
bmbda=1
lambda-20
5mbdae5
lmmbda300
6.8
bmbda-30
ambda-10
1mbba-20
0.90
0.75
T2-2
lambde -50
T2-5
12-1
0.5
12=1
T2-10
72-2
T2-20
0.4
12:10
72=5
0.00
0.02
3.04
0:06
0.12
0.14
Age
Age
Figure 6: Compare adversarial training vertex representations. Left: Oklahoma97: Right: Cora.
diversity
utilly
diversity
utllyy
0.6
1.00
1.000
FairAs)
0.995
FairAc]
T2-10
inter V.5. 8318
0.4
method
0.96
inter knt
0.20
FaNrAci
T2-20
0.985
0.990
VGAE
Fairäd) 72
0.94
0.900
FairAd]
10
FairAd)
0.975
method
0.970
method
0.3
0.90
VGAE
0.30
0.915
VGAE
FabAdd
0.88
Fentdi
T2-20
0.950
Fainkdj
12-20
0.05
0.10
0.15
0.20
0.05
0.10
0.5
0.20
0.05
0.10
0.15
0.20
0.05
0.30
0.15
0.20
proportion
proportion
proportion
proportion
Figure 7: Diversity and utility in recommendations, Left: Oklahoma97; Right: Cora.
17

---

Published as a conference paper at ICLR 2021
Table Experimental results on F6cebook#1684.
Method
AUC
AP
APP
Ame
A talse
PNNR
TTNR
VGAE
94.66 55
93.91 68
2,03
0,59 + 49
0.90 =557
4,48 1.57
4.94 + 1.32
node2vec
90.57 .14
85.61
1.09
1.70 +: 143
0.52 49
2.47
1.52
6.51 2044
5.06 + 1.36
fairwalk
90.56 .63
85.58
1.97 +
0.62
2.14 1.37
6.92 2.19
5.03 +
FairAdinz=1
94.68 .88
93,94 .2
2,02 82
0.60 + .0
0,93 .00
4.42 = 1.57
4.82 1: 1.54
FairAd]y2=
94.63 49
93.84
1.77
0.53 41
0.92
5.00 1.52
4.86 + 1.41
E FAIR VERTEX REPRESENTATION
As intermediate result, inspect the fairness in vertex representation in Figure X To quantify that, we conduct K-means clustering on vertex representation and evaluate the ratio of samples from different sensitive groups within each clusters, and the ratio is called balance. We range the number of clusters from 4 to 8 and report the average balance across all clusters. In general, the higher the balance, the fairer in vertex representations. Overall the series of FairAdj achieves higher balance, which shows the invariant representations on vertices across different sensitive groups.
0.42%
michod
0.72
methed
VGAE
VISAE
Fainddj
Fairaoj
Fairad)
0.815
FairAdj 12-20
FarrAc] T2-20
0.70
0.850
0.800
0.68
0.715
6.750
clusters
clusters
Figure 8: Evaluations on balance of clusters. Left: Oklahoma97: Right: UNC28.
F EXTEND COROLLARY TO TWO-LAYER GNNS
For A DP on vertices after passing two layer GNN!2) (X, A) (Ā(GNN))) (1) (OCNNN"(XXXAX) (X,
p (Ap (AXW() )w( Here denote 14: EvNu (GNN, (1)
(v. (1, v E Sil. i = 0,1,
Q' = supf GNN (1) (u, A)lla | v TuE E V}. 4."" == Eowu (GNN (ONN!"(E,,AA | JuE St,,
0,1.
Q" = sup[[]GNN (v, A)ll2 | E V}. Let 0i be the maximal deviation of (ule E V}.
and 02 be the maximal deviation of (GNN)" (v. A)le V}. We have Q' L| 120. 1kQ.
Q" < L| 12/2 <
112..
Then
(2) DP Q"||2112 1 = QLd (2) 1 (2(ll/6 l12 + 2V Moz)
And
Il - rille L " ||2(a||/0 pılla 2vMar)
Finally have:
A < QL ( ( 3 3 2 | (2 ( +
18


Reviews:
[{"review_id": "xzmW6W8H10O", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper discusses fairness problems in graph embedding for link prediction to mitigate problems such as graph segregation related to sensitive attributes. The paper uses a variational graph autoencoder to learn an embedding, and predicts links based on distance in this embedded space. The notion of dyadic fairness refers to statistical constraints on link prediction between/across sensitive attribute groups, such as parity for positive predictions or false negatives. The learning algorithm updates a weighted adjacency matrix with nonzero entries preserving the observed adjacency structure of the graph, while optimizing edge weights to tradeoff between utility and dyadic fairness of edges predicted from the weights. The paper compares the proposed method to a baseline and a competing fair graph embedding method on several example datasets to show good performance on utility, fairness, and diversity of inter/intra-group link predictions.\n\nI recommend accepting this paper because it focuses on a problem where there is relatively little previous work, introduces a novel approach, and shows empirically that the approach is competitive. I have a few questions or comments which, if addressed, could improve my rating of the paper.\n\n0. Is it really necessary to constrain the nonzero entries of the adjacency matrix based on observed edges? The paper suggests \"adding fictitious links might mislead the directions of message passing,\" but is there any reason to believe the resulting errors would be any worse than errors from other sources of uncertainty in the problem? It seems possible to me, a priori, that an algorithm without this constraint might achieve both better utility and fairness under some conditions on some examples. This might be worth exploring or mentioning, even if the present paper makes the design choice of keeping this constraint.\n\n1. It is not clear to me exactly how the theoretical findings motivate the algorithm. Perhaps this would be clearer with a better explanation related to my previous point about the structural constraint.\n\n2. In the theoretical analysis, immediately after Corollary 4.1, the paper states \"Multiple layers of GNNs can be reasoned out similarly.\" This seems like quite a stretch without providing further justification. \n\n3. It is a little confusing to determine the meaning of \"proportion\" on the horizontal axis in Figure 2.\n\n4. For the experiments, it's not clear to me why the category of an article should be considered a sensitive attribute in citation networks. Perhaps there is an explanation of the fairness concern in citation networks that would make this more obvious. Instead of so many citation networks, the experiments might be improved with social networks having sensitive attributes like race, religion, or political identification, where there are social science reasons to be especially concerned about social network segregation. I believe there is less reason to believe there will be a high degree of network segregation on the basis of gender than on the basis of those other sensitive attributes, so I would suggest not limiting the sensitive attribute to only gender in the social network examples.", "extra_scores": {}, "extra_text": {}}, {"review_id": "YbDFpU4xOlm", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Quality:\nThe work overall is of \"okay\" quality, my concerns are listed at the end of this review.\n\nClarity:\nI believe the presentation can be improved. Specifically, the problem setting can be better explained in the introduction, where terms like \"dyadic fairness\" or \"homogeneous graph\" are thrown without much details. Perhaps a practical example can help understanding the problem under analysis.\n\nSignificance:\nLink prediction is an important problem in the analysis of social/citation networks, thus, the topic of the work is relevant to the community. In addition, the problem is analyzed under fairness considerations which increases the significance.\nThe results, however, are not strong in my opinion (at least from my first review of the paper).\n\nQuestions:\nMy next questions might come from misunderstandings, in which case I would like to clarify:\n\n* Why is homogeneous graph said to be the focus of the analysis in the introduction but, later on, it is not even mentioned in the technical results. Was that assumption being used? did it matter at all?\n* Authors state that the goal is to have link predictions that are independent of the sensitive attributes. Why does minimizing the norm of the difference of averages of node vectors of each group imply predictions being independent of the sensitive attribute?\nNot having a good explanation for this would undermine the work a lot.\n* The references in Section 2 seem rather arbitrary, for instance, in \"fair machine learning\" I do not see the work \"learning fair representations\" (Zemel et al. 2013). I wonder why it was not referred or rather why are the listed references there preferred over other works?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9Qhi1nk27n", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\nThis work studied how the connections in graph data affect 'dyadic fairness' when applying GNN for representation learning on homogenous graphs. Inspired by the theoretical findings, the authors proposed a method (FairAdj) on top of VGAE to adjust adjacency weight matrix as a separate step to address the fairness-utility trade-off. The effectiveness of the proposed method is demonstrated through extensive experiments on different real-world datasets.\n\n##########################################################################\n\nStrength:\n\n- Fairness of graph representation learning is a relevant and emerging research topic\n- The analysis and the proposed method are technically sound and the experiments are executed well\n- Many interesting insights are obtained from the theoretical analysis\n\n##########################################################################\n\nWeakness:\n\n- The overall presentation can be further improved.\n- Current analysis and method are conducted at homogeneous graph only\n- Efficiency / Time complexity analysis is not provided\n\n##########################################################################\n\nDetailed Comments and Questions:\n\nThis is an overall good work which contributes some interesting insights around graph representation fairness, a solid method to mitigate potential bias, and a series quantitative experiments to demonstrate its effectiveness. I also enjoyed reading this work and felt inspired. Overall I vote for *accept* but there are also a few points which could be further improved.\n\n- The overall presentation is a bit dry and tough to digest. Specifically it's a bit difficult to understand dyadic fairness from high-level and differentiate this concept with other algorithmic fairness work on graph data. Might be helpful to highlight the formal definition of this and the corresponding insights.\n\n- Current analysis and method are conducted at homogeneous graph and the analysis is concluded on 1-layer GNN scenario, would be better to open discussions for future work\n\n- One missing part of the proposed mitigation strategy is around the time efficiency analysis. For practical reason, how its efficiency (specifically the two-step iteration for adjusting the adjacency matrix) compared to a typical adversarial approach? \n\n- What I'm further curious about is how the theoretical findings can be extended to 1) multi-hop/layer GNN and 2) bipartite graph such as the typical user-item recommendation setting. For 2) seems not very obvious; for 1) I did see a great practical value as in real-world applications it is very common to go beyond 1-layer network (which is also a way to obtain superior utility), specifically what does corollary 4.1 imply? does that mean with small L, we are expecting to see tighter upper bound with the network goes deeper?\n\n##########################################################################\n\nTypos:\n\n- Remark 1: \"linke\" -> \"link\"\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4H-07Ljy7-a", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of performing link prediction in a way that satisfies demographic parity through Graph Neural Networks. The authors propose an algorithm to modify the weights on the graph adjancency matrix such that the resulting GNN-based link predictions are satisfy the fairness definition. They evaluate this algorithm on several real-world datasets. The experiments demonstrate that the proposed algorithm increases fairness as measured by demographic parity at the expense of accuracy.\n\nThis paper is quite dense and difficult to read. There is little exposition to provide the intuition for what the authors are doing, especially for the reader who is unfamiliar with the particular techniques used. The motivation is also not completely clear to me -- while there are definitely instances where people are interested in demographic parity as a constraint, I don't necessarily see how link prediction in particular is one of those instances.\n\nFrom a technical perspective, the work appears to be novel and sound. The experiments show that the proposed algorithm achieves what it sets out to do, in comparison with baselines.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is devoted to "dyadic fairness" in representation learning. All the reviewers agreed that the contribution is novel, original and technically sound. However, all the reviewers agreed that the paper should be improved in terms of presentation -- for two reviewers, presentation/clarity issues were at the core of their weak rejects. The most positive reviewers highlighted that the problem is still understudied despite the flurry of work on fair machine learning in the last years and therefore the contribution deserves to be accepted. If there is room, this paper can be accepted as a poster.
Decision: Accept (Poster)