Unbiased Graph Embedding with Biased Graph Observations

Nan Wang, Lu Lin, Jundong Li, Hongning Wang

Abstract

Graph embedding techniques are pivotal in real-world machine learning tasks that operate on graph-structured data, such as social recommendation and protein structure modeling. Embeddings are mostly performed on the node level for learning representations of each node. Since the formation of a graph is inevitably affected by certain sensitive node attributes, the node embeddings can inherit such sensitive information and introduce undesirable biases in downstream tasks. Most existing works impose ad-hoc constraints on the node embeddings to restrict their distributions for unbiasedness/fairness, which however compromise the utility of the resulting embeddings. In this paper, we propose a principled new way for unbiased graph embedding by learning node embeddings from an underlying bias-free graph, which is not influenced by sensitive node attributes. Motivated by this new perspective, we propose two complementary methods for uncovering such an underlying graph, with the goal of introducing minimum impact on the utility of the embeddings. Both our theoretical justification and extensive experimental comparisons against state-of-the-art solutions demonstrate the effectiveness of our proposed methods.

Introduction

Graph embedding techniques are fundamental to modern machine learning on graph-structured data. By mapping nodes into low-dimensional vector spaces, these methods enable powerful downstream applications such as social recommendation, protein modeling, and fraud detection. However, a significant challenge arises from the fact that real-world graphs are often "biased" by sensitive node attributes like gender, race, or age. This phenomenon, known as homophily, causes nodes with similar sensitive attributes to connect more frequently.

When an embedding model learns from these biased connections, it inadvertently "bakes in" that sensitive information. This leads to two major issues: downstream algorithms might discriminate against specific groups (fairness), and sensitive attributes can be "leaked" and reverse-engineered from the embeddings (privacy). Existing solutions often use adversarial training to hide this information, but this frequently destroys the utility of the embeddings or is difficult to adapt to different types of graph models.

The UGE Framework: Recovering the Bias-Free Graph

To address these challenges, we propose the Unbiased Graph Embedding (UGE) framework. Unlike existing methods that impose ad-hoc constraints, UGE takes a principled generative approach. We model the observed graph as a distorted version of an underlying, bias-free "structural graph." Our goal is to mathematically "undo" the influence of sensitive attributes to recover this latent structure.

The UGE framework models the transition from a structural graph to an observed graph, then debiases it to produce bias-free embeddings.

The framework introduces three complementary variants:

  • UGE-W (Weighting-based): This method employs importance sampling to reweight the loss function. Edges that are highly likely due to sensitive attributes are down-weighted, effectively simulating a training process on a bias-free graph. This provides a sufficient condition for unbiasedness.
  • UGE-R (Regularization-based): This approach adds a penalty term to ensure that predicted edge probabilities remain invariant whether or not sensitive attributes are considered. This acts as a necessary condition for the learned representations.
  • UGE-C (Combined): By integrating both weighting and regularization, UGE-C achieves a robust balance between debiasing effectiveness and the preservation of structural utility.

Crucially, these methods are backbone-agnostic, meaning they can be integrated into almost any existing embedding algorithm, including GCN, GAT, SGC, node2vec, or Matrix Factorization.

Experimental Evaluation

We evaluated UGE across three large-scale real-world datasets: Pokec-z and Pokec-n (subsets of a Slovakian social network) and MovieLens-1M (a movie recommendation dataset). Sensitive attributes included Gender, Region, Occupation, and Age.

Comparison of UGE variants against state-of-the-art baselines across multiple datasets and embedding models. The y-axis represents utility (NDCG@10), while the x-axis represents bias (Micro-F1 on sensitive attributes).

As shown in the results, UGE-C consistently outperforms baselines like Fairwalk and CFC. It achieves a superior trade-off: significantly reducing the predictability of sensitive attributes (lower Micro-F1) while maintaining high performance on link prediction tasks (high NDCG). For instance, on the Pokec-n dataset using node2vec, UGE-C reduced the bias of the "Region" attribute significantly while maintaining an NDCG@10 of ~0.63, whereas adversarial methods dropped utility much further to achieve similar debiasing.

Conclusion and Future Work

UGE provides a theoretically grounded method for learning unbiased embeddings by focusing on the data-generating process. Instead of treating bias as a classification error, we treat it as a distortion to be mathematically reversed. While the current implementation faces some computational bottlenecks on massive graphs due to the complexity of the regularization term, batch sampling techniques offer a viable path forward. Future research will explore extending this framework to continuous sensitive attributes and developing "Unbiased GNNs" that incorporate debiasing directly into the message-passing mechanism.

Summary updated

Abstract

Graph embedding techniques are pivotal in real-world machine learning tasks that operate on graph-structured data, such as social recommendation and protein structure modeling. Embeddings are mostly performed on the node level for learning representations of each node. Since the formation of a graph is inevitably affected by certain sensitive node attributes, the node embeddings can inherit such sensitive information and introduce undesirable biases in downstream tasks. Most existing works impose ad-hoc constraints on the node embeddings to restrict their distributions for unbiasedness/fairness, which however compromise the utility of the resulting embeddings. In this paper, we propose a principled new way for unbiased graph embedding by learning node embeddings from an underlying bias-free graph, which is not influenced by sensitive node attributes. Motivated by this new perspective, we propose two complementary methods for uncovering such an underlying graph, with the goal of introducing minimum impact on the utility of the embeddings. Both our theoretical justification and extensive experimental comparisons against state-of-the-art solutions demonstrate the effectiveness of our proposed methods.
BibTeX
@inproceedings{wang2022unbiased,
  author = {Nan Wang and Lu Lin and Jundong Li and Hongning Wang},
  title = {{Unbiased Graph Embedding with Biased Graph Observations}},
  booktitle = {The Web Conference},
  year = {2022},
  doi = {10.1145/3485447.3512189},
}
Figure