Fairwalk: Towards Fair Graph Embedding

1 Introduction

The rapid assimilation of online social networks (OSNs) into people's daily lives has resulted in a massive wealth of user generated data. Researchers have created various tools to mine this rich and diverse data. One of the most prominent tools in this domain is graph embedding, which maps each user into a lower dimension vector that reflects the user's structural information within the network, such as her neighborhood, communities she belongs to, her popularity, etc. Embedding vectors have been used in various tasks, such as friendship recommendation and personal attribute prediction.

Most network embedding methods rely on deep neural networks and are often treated as a black box. The resulting vectors may have captured undesired sensitive information, that reinforces the bias already existing in the network. When used for more advanced tasks, e.g., friendship recommendation, they may result in unanticipated fairness issues. Indeed, different groups based on ethnicity, gender, levels of urbanization, or wealth are usually unequally represented in the social network graph. Analyzing bias issues inherent in such embedding based algorithms is therefore especially important but has not received attention from academia so far.

∗Authors contributed equally to this work.

†Corresponding author

In this paper, we take the first step towards quantifying and addressing fairness issues of graph embedding methods. In particular, we concentrate on one of the most prominent methods in this field, namely node2vec [Grover and Leskovec, 2016], and investigate its fairness with respect to friendship recommendation. As pointed in [Stoica et al., 2018], a recommendation system biased towards a majority in an OSN can prevent minorities from rising in the network (becoming influencers with high reach). This is further confirmed by studies on strongly homophilic networks and their negative implications on minorities [Karimi et al., 2018].

Anti-discrimination laws in various countries prohibit unfair treatment based on certain traits such as race, religion, gender (sensitive attributes). The Title VII of the Civil Rights Act of 1964 is one of the most noteworthy examples. However, these laws typically are too abstract for computation, hence there exist a variety of interpretation and the resulting proposals for mathematical formulations. In this paper, we focus on disparate impact also known as group fairness [Barocas and Selbst, 2016]. Disparate impact occurs when the decision of an algorithm benefits or hurts (a) certain sensitive feature group(s) more frequently than other group(s).

1.1 Contribution

First, we conduct the first-of-its-kind study of algorithmic fairness in the setting of graph embedding methods. We specifically analyze group fairness (disparate impact) of the state-of-the-art graph embedding: node2vec.

Second, we extend statistical parity, a well-known measure of disparate impact to measure fairness for groups based on sensitive attributes of pairs of users. We further propose a novel notion of Equality of Representation to measure fairness in friendship recommendation systems.

Third, we apply node2vec for friendship recommendation in real world OSN datasets as a case study. Using the fairness metrics above, we find biases in the recommendations caused by unfair graph embeddings.

Fourth, to mitigate the aforementioned biases, we propose a novel fairness-aware graph embedding algorithm Fairwalk, that extends node2vec. Evaluations on our OSN demonstrate the effectiveness of Fairwalk on both datasets w.r.t. all fairness metrics. Compared to node2vec, Fairwalk increases fairness in each case by a large margin. We also compare the utility of Fairwalk and node2vec.

2 RelatedWork

Algorithmic bias has received a lot of attention in the recent years [Barocas and Selbst, 2016; Romei and Ruggieri, 2014]. Prior work distinguishes between group unfairness and individual unfairness. Group unfairness (disparate impact) occurs when the decision outcomes disproportionately benefit or hurt people of different groups based on their sensitive attribute value. Examples of group fairness are statistical parity [Feldman et al., 2015], disparate mistreatment [Zafar et al., 2017], equality of opportunity [Hardt et al., 2016] and calibration [Kleinberg et al., 2017]. Individual unfairness occurs when the decision of an algorithm is different for two individuals having the same non-sensitive attributes but different values for the sensitive attribute [Dwork et al., 2012].

Different fairness-aware algorithms have been proposed to achieve group and individual fairness, mostly for predictive tasks. [Calders and Verwer, 2010] extend naive Bayes models by modifying the learning algorithm. [Kamiran et al., 2010] modify the entropy-based splitting criterion in decision tree induction to account for sensitive attributes. [Kamishima et al., 2012] apply a regularization to probabilistic discriminative models, such as logistic regression. Other works include fairness in OSN timelines [Hargreaves et al., 2019] and extension of group fairness to fair rankings, [Zehlike et al., 2017; Yang and Stoyanovich, 2017]. Contrary to the above, we focus on obtaining fair features that can later be used for plethora of machine learning tasks. We tackle group fairness and not individual fairness since two individuals that have identical neighborhoods would have similar embeddings, independent of the sensitive attributes of their neighbors and would be treated equally.

In the area of graph embeddings, after invention of word2vec [Mikolov et al., 2013], many prominent graph data mining techniques were developed adopting the skip-gram model, namely DeepWalk [Perozzi et al., 2014], node2vec [Grover and Leskovec, 2016], LINE [Tang et al., 2015b] and PTE [Tang et al., 2015a], and walk2friends [Backes et al., 2017]. In this paper we study the fairness of node2vec - the most widely used one∗ .

3 Fairness Metrics

In this section, we present the notations used throughout the paper, followed by definitions of the fairness metrics. We focus on the notion of disparate impact. Firstly, we leverage the most well-known measure of disparate impact, namely statistical parity. Secondly, since our work is aimed at improving the representation of under-represented groups, we propose our own notion of Equality of Representation which comes in two variants - the user and the network level.

3.1 Notations

We define an OSN as an undirected, unweighted graph G = (U , E), where the set of vertices U represents the set of users and the set of edges E ⊆ {(u, v): u ∈ U, v ∈ U, u ̸= v} represents the set of friendships. Note that since G is undirected (u, v) ∈ E implies (v, u) ∈ E. We define neighbors of a node u as ω(u) = {v : (u, v) ∈ E}.

∗ according to citation count from GoogleScholar

We denote a sensitive attribute by S, and gender as S = g and race as S = r. We represent the set of all possible values of S by Z S and denote a specific value by zS ∈ Z S . The function ζ S : U → Z S maps users to their attribute values. For example, for an Asian male u, ζ g (u) = "male" and ζ r (u) = "asian". We denote neighbors of u with an attribute value z as ωz(u) = {v : v ∈ ω(u) ∧ ζ(v) = z}. Note that ⋃z∈Z ωz(u) = ω(u). We define a set of users recommended to user u as ρ: U → 2U and set of users with a specific attribute value z recommended to u as ρz(u) = {v : v ∈ ρ(u) ∧ ζ(v) = z}.

We partition user pairs (u, v) ∈ U × U into groups GSij based on the attribute values of both u and v, specifically, for i, j ∈ Z S , GSij = {(u, v) : ζ(u) = i ∧ ζ(v) = j ∧ u, v ∈ U}. We collectively refer to the set of all groups based on a sensitive attribute S as G S .

3.2 Statistical Parity

Statistical Parity also known as Demographic Parity or Independence is the statistical equivalent of the legal doctrine of disparate impact [Feldman et al., 2015]. Statistical Parity (typically defined in terms of two groups) requires the acceptance rates of the candidates from both groups to be equal. This allows us to measure recommendation fairness independent of the ground truth (existing friendships) which in our case is itself biased. Given a partitioning of user pairs based on an attribute S, into two groups GSab and GScd , let P(GSij ) denote the acceptance rate for group GSij ,

The bias, or statistical parity, w.r.t. GSab and GScd is then the difference between P (GSab ) and P (GScd ).

We extend the above definition to account for multiple groups that we have for friendship recommendation. Since our groups consider the attribute values of both users in a pair, we have at least 4 groups when we consider a binary attribute like gender and in general ∣∣Z ∣∣2 groups when we consider any n-ary attribute like race. To capture the differences between multiple groups, we calculate the variance between the acceptance (recommendation) rates of each group in G S .

3.3 Equality of Representation

Modern online recommendation systems suffer from problems of echo chambers or the information bubble effect [Flaxman et al., 2016; Quattrociocchi et al., 2016]. Usually users get recommendations based on their interests, which isolates them from other contradicting interests or viewpoints and reinforces the existing viewpoints. This also manifests in friendship recommendations in OSNs, where users who join a network into some well-established community, rarely see anything or anybody outside of it, although it might be interesting for them. As a direct consequence minority communities get isolated and are not seen by others. Our work aims to improve the representation of such under-represented groups in the OSN graph embeddings. To promote recommendations where all groups are equally represented, we define bias by Equality of Representation in two variants: bias ERg at the network level and bias ERu at the user level.

Network level. At the network level, we measure bias between different groups GSij , among all recommendations given in the network. Denoting the number of recommendations from a group GSij as N(GSij ) = |{(u, v) : v ∈ ρ(u) ∧ (u, v) ∈ GSij }|,

User level. At the user level, among the recommendations ρ(u) given to each user u, we measure the fraction of users having attribute value z and denote it as z-share(u) = |ρz(u)| |ρ(u)| . Specifically, for a given attribute value z, bias is measured as the difference between a fair fraction (where each attribute value has an equal share) and the average z-share over all users.

This definition allows for measuring the bias for each sensitive attribute value independently.

4 Friendship Recommendation with node2vec

In this section, we first review the graph embedding algorithm node2vec, then describe a node2vec based recommendation system and finally analyze its fairness.

4.1 Graph Embedding - node2vec

A graph embedding is a mapping from nodes in a graph to a vector space f : U → Rd where d is a hyperparameter capturing the number of dimensions of the vector space. Resulting vectors can be used for multiple machine learning tasks, e.g., link prediction for friend recommendation. Node2vec [Grover and Leskovec, 2016] first uses a random walk over a graph to generate walk traces and then extracts features based on learned traces.

Random walk. Given a graph G, for each node u ∈ U, node2vec performs a single random walk walk num number of times. The result is a list of traces, where each trace is a list of nodes' ids resulting from single random walks. Single random walk is a standard random walk over graphs without weights, i.e., at each step the next node is chosen uniformly at random among all neighbors of the current node. Both walk num and walk len are hyperparameters of node2vec.

Feature learning. Next, node2vec uses the generated traces to train a neural network and learn embedding vectors. Let us define a network neighborhood Ns(u) as the set of nodes preceding and succeeding node u in the generated walk traces. The skip-gram architecture is adapted to the network traces with a goal to maximize the log-probability of observing a network neighborhood Ns(u) based on the feature vector of node u. The corresponding objective function is defined as:

Here, the conditional probability P(u′ |f(u)) is modeled as a softmax function.

4.2 Recommendation System

We take a supervised learning approach towards the recommendation task. For each user, we use the graph embedding as described above in 4.1 to learn embeddings. We further define a feature vector ⃗x(u,v) for a user pair (u, v) as the Hadamard distance† between embeddings of u and v. Given two vectors f(u) and f(v), the Hadamard operator ⊡ is defined as: [f(u) ⊡ f(v)]i = [f(u)]i[f(v)]i. We train a random forest classifier to learn associations between the feature vectors of user pairs ⃗x(u,v) and presence or absence of friendships between them.

The trained model is then used to predict class probabilities for unseen candidate pairs using their corresponding feature vectors ⃗x(u,v). We use the positive class probability as the recommendation score. A friend v is recommended to a user u, if the recommendation score for the pair (u, v) ̸∈ E is within the top k% of all the scores received by all candidate pairs. We denote the resulting friendship recommendations given to a user u by ρ(u).

4.3 Fairness of node2vec

We now evaluate the fairness of node2vec-based friendship recommendation using Equality of Representation at user level, bias ERu (Eq. (3)). In a fair recommendation system, we would expect the bias to be lower than the initial bias. To calculate the initial bias in the network, we modify Eq. (3) by using the neighborhood function ω instead of recommendation ρ. We do a rigorous bias evaluation using all metrics in Section 6.

We distinguish between two genders Z g = {zg 0 , zg 1 } and three races: Z r = {zr 0 , zr 1 , zr 2 } and the protected (minority) groups are: zg 1 , zr 0 , zr 2 (we describe our dataset in details in Section 6.1). Figure 1 shows the distribution of z-share values for all users. The distribution of z-share indeed follows the original distribution in the network, and so does the bias. This demonstrates that node2vec based recommendations mirrors the gap between minorities and majorities.

5 Fairwalk

Since graph embeddings aim to find the best structural representation of nodes, the algorithm also unintentionally learns some information about people's sensitive attributes and relations between them. Recommendations based on this further reinforces differences between minorities and majorities. As a countermeasure to this problem, we propose Fairwalk, a modified version of random walk, which results in a more diverse network neighborhood representation thereby producing less biased graph embedding.

5.1 RandomWalk

We are modifying the random walk procedure from original node2vec. Instead of randomly selecting a node to jump to

†While other binary operators (e.g., average, L1, L2 distance) could be used, we chose Hadamard distance, as it performed the best in original node2vec paper [Grover and Leskovec, 2016]

Algorithm 1 Fair random walk trace generation

1: procedure RAND WALK(U, ω, walk num, walk len) 2: traces ←empty list 3: for all u ∈ U do 4: for i ← 0, walk num do 5: trace←empty list 6: u1 ← u 7: for j ← 0, walk len do 8: trace.append(u1) 9: Zu ← {z : z ∈ Z ∧ ∣∣ωz(u1)∣∣ > 0} 10: z1 R←- Zu 11: v R←- ωz1 (u1) 12: u1 ← v 13: end for 14: traces.append(trace) 15: end for 16: end for 17: return traces 18: end procedure

from amongst all neighbors, we now partition neighbors into groups based on their sensitive attribute values and give each group the same probability of being chosen regardless of their sizes. Then a random node from the chosen group is selected for the jump. The modified random walk procedure is shown in Algorithm 1. By R←- A we denote drawing an element of set A uniformly at random.

5.2 Resulting Traces

While detailed evaluation of the resulting modified embedding is in Section 6, we can already discuss differences in the walk traces themselves. From Figure 2 we can see that minorities appear more often in the fair random walk. Not only does it result in higher network neighborhood diversity with respect to sensitive attribute, but also minorities appear more frequently in the traces. This provides more network neighborhood data for minorities which enables the neural network give more importance to obtain their best vector representation while optimizing the overall objective function.

6 Evaluation

In this section, we first describe our dataset, followed by the set-up of the machine learning model for our experiments. We then present the evaluation results for our Fairwalk using the fairness metrics defined in Section 3 and finally show the recommendation utility in terms of precision and recall.

6.1 Dataset

We use Instagram data collected from two of the biggest cities in different English speaking countries, namely London and Los Angeles (LA). The data was collected in 2016 using the Instagram API. An edge exists between two users if they mutually follow each other (e.g., [Cho et al., 2011]). We concentrate on two sensitive attributes, gender and race, which we extract by querying Face++ with users' profile pictures. Tools such as Face++ have limitations [Buolamwini and Gebru, 2018]. To this end, we choose users for whom the attribute with highest confidence is at least 20 percentage points higher then the second best. We distinguish between female or male gender, and denote them as 0 or 1, i.e., Z g = {0, 1}, and between African, Caucasian or Asian race and denote them as 0, 1 or 2, i.e., Z r = {0, 1, 2}. Table 2 shows the sizes of datasets and the proportions of different genders and races. We thus have 4 pairwise groups for gender namely Gz0,z0 ,Gz0,z1 ,Gz1,z0 ,Gz1,z1 and 9 pairwise groups for race namely Gzi,zj , i, j ∈ {0, 1, 2}. Table 1 shows the proportions of friendships in different groups.

6.2 Experimental Setup

We iterate our experiments 5 times. To this end we divide our dataset into 5 equal slices. We train a random forest with 100 trees using 4 out of 5 slices, leaving out a different slice each time. We use Hadamard distance between the feature embeddings of each user pair as input features to the random forest. Graph embeddings are trained 5 times, each time with the same 4 slices as used for training. We use the following hyper-parameters (following [Grover and Leskovec, 2016]), i.e., length of each walk: walk len = 80, number of walks starting from each node in the graph: walk num = 20, number of dimensions of the resulting vector space: d = 128. For the recommendation candidates, of each node u we rank all non-friend nodes by the cosine similarity of their embeddings with the embedding of u and select the top 100. This approach gives us a candidate set likely to be recommended. For scalability reasons (for bigger datasets), non-friend pairs can be sampled randomly. For the quantity of top recommendations, we experiment with a variety of values for k and do not observe any significant differences. Therefore we show results below only for k = 20 i.e., when the top 20% of all candidates are selected for recommendation. We denote node2vec based recommendations by "regular" and Fairwalk based recommendation by "fair".

6.3 Statistical Imparity

Figure 3 shows the acceptance rates P(GSij )(fraction of recommended users pairs out of all possible pairs in each group) for both the regular and the Fairwalk. We observe that, Fairwalk increases the probability of the under represented groups being recommended to a very large extent. Additionally, it is noteworthy to see that the probabilities of same gender and same race friendship recommendations are always reduced by Fairwalk and the probabilities of diverse friendships are always increased.

Table 3 shows bias SI compared to node2vec for both cities. Fairwalk reduces bias SI (G g ) by 61% and bias SI (G r ) by 68% for LA. For London, Fairwalk reduces bias SI (G g ) by 91% and bias SI (G r ) by 61% compared to node2vec.

6.4 Equality of Representation

Group Level. Figure 4 highlights the differences between the representations of different groups among the top recommendations. We see that as compared to node2vec, Fairwalk decreases the share for the over-represented groups, e.g., G r 11 and G g 00 and increases the share for most underrepresented groups which can be clearly seen for G r 01 , G r 10 , G r 02 , G r 12 and G g 10 , G g 01 . For G g 11 and G r 00 , Fairwalk could not increase the representation anymore since they are already very strongly connected as seen in Fig 3. Table 3 shows bias ERg for both cities. Compared to node2vec, Fairwalk reduces bias ERg (G g ) by 36% and bias ERg (G r ) by 23% for LA and bias ERg (G g ) by 26% and bias ERg (G r ) by 21% for London.

User Level. On the distribution plots on Figures 5 we can see that Fairwalk reduces the gap between different groups, by leaning towards the fair fraction (where each attribute value has an equal share). We skipped the distribution for gender 1 since it's symmetrical to gender 0. The exact values of bias ERu for different groups for the original network (initial bias) for node2vec and Fairwalk can be found in Table 4. We see that Fairwalk decreased the bias in all cases, for LA the average improvement is 32% and for London 14%. The best result is for race 0 in LA, with an improvement of 53%.

6.5 Precision and Recall

We also evaluate whether our recommendations capture any friendship edges that would otherwise have been formed naturally without users following any recommendations at all. To this end, we use the 20% of friendship edges unused during training for each iteration as described in Sec. 6.2 as ground truth. We calculate precision and recall for Fairwalk, and compare with the regular node2vec recommendations.

Figure 6 shows precision and recall for different number of recommendations for LA. Unsurprisingly, we see that precision and recall are always lower for Fairwalk as compared number of recommendations to node2vec. This indicates that we deviate more from the original biased growth of the network compared to regular recommendations thereby not amplifying the initial bias in the network. We also see that for race, Fairwalk deviates the most since it tries to balance more groups compared to gender, and given that race 1 alone makes up a huge proportion of our OSN dataset. Nevertheless, we capture a large number of true positives. Results for London follow the same trend.

Figure 6: Precision and recall for different number of recommendations.

7 Conclusion and FutureWork

We study fairness issues in a state-of-the-art graph embedding method node2vec. Using the metrics of Statistical Parity and Equality of Representations we find bias in node2vec. We propose a fairness-aware Fairwalk and demonstrate its effectiveness in mitigating the aforementioned biases by a large scale evaluation on real world OSN datasets for friendship recommendation.

While Fairwalk already improves Statistical Parity and Equality of Representations to a large extent, there exist multiple other notions of fairness in the community dependent on the task at hand. Our Fairwalk can be tuned with parameters to fulfill any such fairness notion, for example maintaining the real-world ratio between groups. One could also iteratively perform further recommendation to achieve a higher balance or parity. Using a weighted ensemble-like approach that allow optimizing for a combination of sensitive attributes (e.g Asian females) can account for cross-attribute biases in the network. This can also be done following recent work on rich subgroup fairness [Kearns et al., 2019].

Acknowledgements

The authors would like to thank Inken Hagestedt, David Pfaff as well as the anonymous reviewers for their valuable comments on the submitted manuscript.