Abstract
Graph embeddings have gained huge popularity in recent years as a powerful tool to analyze social networks. However, no prior works have studied potential bias issues inherent within graph embedding. In this paper, we make a first attempt in this direction. In particular, we concentrate on the fairness of node2vec, a popular graph embedding method. Our analyses on two real-world datasets demonstrate the existence of bias in node2vec when used for friendship recommendation. We, therefore, propose a fairness-aware embedding method, namely Fairwalk, which extends node2vec. Experimental results demonstrate that Fairwalk reduces bias under multiple fairness metrics while still preserving the utility.
Introduction: The Algorithmic Glass Ceiling
Graph embeddings, such as node2vec, serve as the foundational "engine" for many modern recommendation systems by mapping social network users into low-dimensional vectors. However, social networks are rarely neutral; they are often characterized by homophily—the tendency of individuals to associate with others similar to themselves—and structural inequalities.
Standard embedding methods often act as a "black box" that inadvertently captures and amplifies these social biases. If a minority group is underrepresented or structurally isolated in a graph, node2vec learns and reinforces this isolation. This leads to recommendation "echo chambers," where users are primarily suggested friends from their own demographic groups. Such biases can create an algorithmic glass ceiling, preventing minority groups from gaining visibility or influence within the network.
Methodology: Fair Random Walks
To address these issues, we propose Fairwalk, a fairness-aware extension of the node2vec algorithm. The core innovation lies in modifying the random walk process used to generate node sequences for embedding.
In standard node2vec, a "walker" moves to a neighbor chosen uniformly at random. This means that if a user has a disproportionate number of friends from a majority group, the walker is far more likely to remain within that group's cluster. Fairwalk intervenes by first grouping a node's neighbors based on a sensitive attribute (e.g., gender or race). It then assigns an equal probability to each group being visited. Once a group is selected, a specific node within that group is selected uniformly. This mechanism forces the embedding process to "see" a more diverse neighborhood for every node, regardless of the local network density of different demographic groups.
To evaluate the effectiveness of Fairwalk, we introduce two primary fairness metrics:
- Statistical Parity (SI): This measures whether different demographic pairs (e.g., male-male vs. male-female) have equal "acceptance rates" in the resulting recommendations.
- Equality of Representation (ER): This assesses whether recommendations are distributed proportionally to the actual population, both at the aggregate network level and for individual users.
Key Results and Discussion
Our experimental results demonstrate that Fairwalk significantly outperforms standard node2vec across all fairness metrics while maintaining high utility.
Bias Reduction and Parity
Fairwalk achieved substantial reductions in bias. For instance, in the London dataset, it reduced Statistical Parity bias for gender by 91% and for race by 61%. By balancing the "acceptance rates" across different groups, Fairwalk ensures that recommendations are not unfairly skewed toward majority groups.
Improved Representation
In the Los Angeles dataset, Fairwalk improved the "Equality of Representation" at the user level by an average of 32% for gender and up to 53% for certain racial groups. This indicates that the embeddings generated by Fairwalk are less clustered by sensitive attributes, providing a more diverse set of potential connections for all users.
The Utility-Fairness Trade-off
While Fairwalk introduces a slight "fairness tax"—a minor decrease in precision and recall when predicting existing edges—this is an expected outcome. Because Fairwalk intentionally deviates from the "natural" (and often biased) structure of the graph to promote diversity, it may not perfectly replicate existing biased connections. However, this trade-off is essential for breaking the cycle of biased network growth and fostering a more equitable social landscape.
Conclusion
Fairwalk represents a significant step toward making graph embeddings more equitable. By diversifying the neighborhoods explored during random walks, it prevents the amplification of social biases in recommendation systems. Future work will explore "rich subgroup fairness," addressing intersections of multiple sensitive attributes and adapting the method for scenarios where attribute data may be incomplete.
Summary updated