Unbiased Graph Embedding with Biased Graph Observations

Nan Wang, Lu Lin, Jundong Li, Hongning Wang

TL;DR

This paper introduces a principled framework for learning unbiased graph embeddings by uncovering an "underlying bias-free graph." Instead of simply penalizing the model when it learns sensitive info, the authors propose two complementary methods—importance weighting and distribution regularization—to ensure embeddings are learned as if the sensitive attributes (like gender or age) never influenced the graph's structure in the first place.

What Problem Does This Paper Address?

Graph embeddings map nodes into low-dimensional vectors used for tasks like friend recommendation or credit scoring. However, real-world graphs are often "biased" by homophily: people with similar sensitive attributes (gender, race, age) tend 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:

  1. Fairness: Downstream algorithms might discriminate against specific groups.
  2. Privacy: Sensitive attributes can be "leaked" and reverse-engineered from the embeddings.

Existing solutions often use adversarial training (trying to make a "discriminator" fail to guess the attribute), but this frequently destroys the utility of the embeddings or is difficult to adapt to different types of graph models (like GCNs vs. node2vec).

Methods

The authors model graph generation as a two-phase process: first, a "structural graph" forms based on global properties (like degree distribution); second, attributes "re-route" these connections. Their goal is to recover the influence of that first, bias-free phase.

They propose UGE (Unbiased Graph Embedding) with three variants:

  • UGE-W (Weighting-based): Uses importance sampling. It reweights the loss function for each edge. If an edge was highly likely due to a sensitive attribute (e.g., two people of the same gender connecting), its weight is reduced. This provides a sufficient condition for unbiasedness by simulating a bias-free training set.
  • UGE-R (Regularization-based): Adds a penalty term that forces the predicted edge probabilities to be the same regardless of whether sensitive attributes are considered. This acts as a necessary condition, ensuring the learned representations don't differentiate based on protected traits.
  • UGE-C (Combined): The "best of both worlds" approach that uses both weighting and regularization to balance utility and fairness.

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

Datasets

The researchers evaluated their methods on three large-scale real-world datasets:

  • Pokec-z & Pokec-n: Subsets of a Slovakian social network. Sensitive attributes: Gender, Region, and Age.
  • MovieLens-1M: A movie recommendation dataset. Sensitive attributes: Gender, Occupation, and Age.

Key Insights and Ideas

  • Generative Perspective: Instead of treating bias as a classification error to be fixed, the authors treat it as a distortion in the data-generating process. By mathematically "undoing" the distortion (via Bayes' Theorem), they can recover the structural signal.
  • Sufficient vs. Necessary: UGE-W is theoretically "sufficient" because it changes the objective to match a bias-free world. UGE-R is "necessary" because it ensures the model's internal logic remains consistent. Combining them (UGE-C) provides the most robust debiasing.
  • Utility Preservation: Unlike adversarial methods that often "trash" the embedding space to hide information, UGE focuses on re-weighting the existing structural signal, which helps maintain high performance on downstream tasks like link prediction.

Key Results

  • Superior Debiasing: In attribute prediction tests (where a classifier tries to guess the sensitive trait from the embedding), UGE-C consistently achieved the lowest Micro-F1 scores, meaning it hid sensitive info better than baselines like Fairwalk or CFC.
  • Better Trade-offs: On the Pokec-n dataset using node2vec, UGE-C reduced the bias of the "Region" attribute significantly while maintaining an NDCG@10 (utility metric) of ~0.63, whereas adversarial methods (CFC) dropped utility much further to achieve similar debiasing.
  • Visual Evidence: t-SNE visualizations showed that while standard GCN embeddings clearly cluster nodes by region (showing high bias), UGE-C embeddings "blend" the regions together, effectively removing the geographical signature from the data.

Limitations and Future Work

  • Computational Complexity: The regularization term in UGE-R theoretically requires $O(N^3)$ operations (summing over all node pairs). While the authors mitigate this using batch sampling, it remains a bottleneck for extremely massive graphs.
  • Categorical Assumption: The current framework assumes sensitive attributes are categorical. While the authors suggest discretization for continuous data, a native approach for continuous variables isn't explored.
  • Future Directions: The authors suggest moving toward "Unbiased GNNs" that directly aggregate neighbor information through a bias-free lens, rather than just debiasing the final embeddings.

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},
}

Loading related content...

Figure