PaperlayerView exact revision on arXiv

Source-linked AI summary

Unbiased Graph Embedding with Biased Graph Observations

Nan Wang, Lu Lin, Jundong Li, Hongning Wang

arXiv:2110.13957v4cs.LGcs.AI

TL;DR

Sensitive attributes can affect observed graph connections and thereby be retained in node embeddings, while existing constraints may compromise utility. The paper learns embeddings from an inferred bias-free graph using complementary weighting and regularization methods; experiments report effective debiasing and improved utility–unbiasedness trade-offs.

  • Problem

    Sensitive attributes can influence observed graph connections and leak into node embeddings, while existing ad-hoc constraints may compromise embedding utility.

    Source: §1 · p. 1

  • Method

    UGE infers a graph without sensitive-attribute influence and learns embeddings from it using complementary edge-loss weighting and regularization methods.

    Source: §1 · pp. 1–2, §5 · p. 4

  • Results

    Across three datasets and several embedding backbones, UGE is reported to achieve effective debiasing and encouraging utility–unbiasedness trade-offs, with UGE methods showing the least bias across the tested attributes and datasets.

    Source: §1 · p. 2, §6.2 · p. 7

  • Takeaways & Limitations

    The experiments report that embeddings learned with UGE can support fair predictions in downstream applications.

    Source: §1 · p. 2, §7 · p. 8

    The generative account assumes an underlying structural graph whose edge distribution is modified by node attributes.

    Source: §4 · p. 3

Abstract

from arXiv · show

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.

1 INTRODUCTION

Graph embeddings support downstream graph tasks, but sensitive attributes can shape observed connections and leak into embeddings, raising fairness and privacy concerns. The paper proposes learning from a bias-free graph, using complementary methods to uncover it and seeking a balance between unbiasedness and utility.

1 INTRODUCTION

  • Sensitive attributes can shape observed connections, causing embeddings to retain sensitive information and raise downstream fairness and privacy concerns.The introduction gives gender-based friend recommendations as an example of how this information can affect downstream decisions.Source: §1 · p. 1
  • Prior adversarial regularization can hurt embedding utility, while Fairwalk and DeBayes [6] are tied to specific embedding methods.The introduction describes preventing attribute prediction as a necessary condition for debiasing and notes that randomized embeddings trivially satisfy it.Source: §1 · p. 1
  • UGE learns embeddings from an underlying structural graph whose edges are generated without influence from sensitive attributes.The proposed principle filters sensitive-attribute influence from the observed graph before embedding learning.Source: §1 · pp. 1–2
  • Importance-weighted reconstruction loss and an edge-probability regularizer provide complementary ways to uncover the bias-free graph and can be combined to balance utility and unbiasedness.The paper reports experiments on three datasets and several embedding backbones, with encouraging utility–unbiasedness trade-offs and fair downstream predictions.Source: §1 · p. 2

2 RELATED WORK

Prior work addresses graph-embedding fairness through changes to training data, learning objectives, or learned embeddings. The paper distinguishes its approach by modeling graph generation and learning from an underlying bias-free graph.

2 RELATED WORK

  • Fairwalk changes random-walk sampling, while post-processing methods use discriminators to correct embeddings; both approaches can compromise prediction quality.The related-work discussion says preprocessing may shift the data distribution and post-correction is detached from model training.Source: §2 · p. 2
  • Algorithmic methods include adversarial constraints [1] [5] [10] and DeBayes [6], which absorbs sensitive information in a biased prior but is difficult to generalize beyond its specific embedding method.The paper instead models graph generation and removes sensitive-attribute influence to uncover a bias-free graph.Source: §2 · p. 2
  • Attributed Graph Model separates structural edge probabilities from attribute correlations, motivating the paper's separation of sensitive attributes when estimating edge probabilities.Source: §2 · p. 2

3 PRELIMINARIES

The paper frames unbiased graph embedding as learning node representations independent of sensitive attributes, and distinguishes that property from fairness in a particular downstream task. It uses user-related graphs as an illustration while describing a broader graph setting.

3 PRELIMINARIES

  • User-related graphs illustrate the fairness criterion, but the proposed solution is stated to apply to any graph data and selected sensitive attributes.Source: §3 · pp. 2–3

3.1 Notation

  • The notation assumes an undirected attributed graph with categorical attributes, with the first m attributes designated sensitive and the remainder non-sensitive.The authors note that continuous values can be discretized.Source: §3.1 · p. 3, §3.2 · p. 3
  • In the unsupervised link-prediction setting, an encoder maps each node to a d-dimensional vector and a scoring function predicts whether node pairs have edges.The learning loss is defined per edge and generally compares observed edges with unobserved negative samples.Source: §3.1 · p. 3

3.2 Unbiased Graph Embedding

  • An embedding is unbiased with respect to an attribute when it is independent of that attribute; downstream fairness alone cannot establish that independence.The paper evaluates embedding bias through sensitive-attribute prediction and separately uses downstream fairness measures.Source: §3.2 · p. 3

4 EFFECT OF ATTRIBUTES IN GRAPH GENERATION

The paper models observed edges as arising from a structural graph whose edge distribution is modified by node attributes. This separates structural properties from attribute-driven effects in graph generation.

4 EFFECT OF ATTRIBUTES IN GRAPH GENERATION

  • The generative account starts with an underlying structural graph governed by global properties, then lets node attributes modify its edge distribution, for example through homophily.Source: §4 · p. 3
  • The structural model assigns edge probabilities independently of node attributes, while the observed graph conditions edge probabilities on attribute-value combinations.The structural graph's edges are modeled as Bernoulli samples from probabilities set by the model parameters.Source: §4 · p. 3
  • The observed edge probability modifies the structural probability through an attribute-dependent ratio, representing the influence of attributes on graph generation.Figure 1 uses node colors for attribute values and line styles to suggest attribute influence on observed edges.Source: §4 · p. 4, Figure 1 · p. 4

5 UNBIASED GRAPH EMBEDDING FROM A BIAS-FREE GRAPH

The section learns embeddings from a graph generated without sensitive attributes, so the embeddings are unbiased with respect to those attributes. It presents weighting-based, regularization-based, and combined methods for approximating that graph or its properties.

5 UNBIASED GRAPH EMBEDDING FROM A BIAS-FREE GRAPH

  • The framework removes sensitive attributes when defining a bias-free graph and learns embeddings from its edge probabilities.It conditions those probabilities only on non-sensitive attributes; the resulting embeddings are described as unbiased with respect to sensitive attributes.Source: §5 · p. 4

5.1 Weighting-Based UGE

  • UGE-W reweights each observed edge’s loss so the resulting loss is equivalent in expectation to learning from the bias-free graph.Theorem 5.1 establishes that UGE-W’s loss is unbiased with respect to the bias-free graph.Source: §5.1 · p. 4

5.2 Regularization-Based UGE

  • The regularization-based method matches edge-score estimates for node pairs grouped by sensitive and non-sensitive attribute combinations.It uses the ℓ2 distance between the two estimates as a regularization term.Source: §5.2 · p. 5

5.3 Combined Method

  • The combined method uses UGE-W and UGE-R to seek a better trade-off between embedding unbiasedness and downstream utility.UGE-W is a sufficient condition for unbiased graph embedding, while UGE-R requires embeddings to satisfy properties of a bias-free graph.Source: §5.3 · p. 5

6 EXPERIMENTS

Across three datasets and multiple embedding models, the experiments assess UGE’s debiasing, utility, and downstream fairness. UGE methods generally offer favorable unbiasedness–utility trade-offs, with UGE-C often strongest on debiasing and trade-off performance.

6.1 Setup

  • The experiments use three user-related datasets and evaluate UGE with five representative embedding models, alongside debiasing baselines and random embeddings.Pokec-z and Pokec-n use GCN, GAT, SGC, and node2vec; MovieLens-1M uses MF.Source: §6 · p. 5, §6.1 · p. 6

6.2 Unbiasedness and Utility Trade-off

  • UGE methods have the least bias across the reported sensitive attributes and datasets; UGE-C usually debiases best by combining UGE-W and UGE-R.The comparison reports Micro-F1 on Pokec-z with GAT and Pokec-n with node2vec.Source: §6.2 · p. 7, Table 2 · p. 7
  • Across most cases, UGE methods achieve the most encouraging unbiasedness–utility trade-offs; UGE-C usually improves debiasing without sacrificing too much utility.Random embeddings have the lowest Micro-F1, while embeddings without debiasing have the highest NDCG@10.Source: §6.2 · p. 7, Figure 2 · p. 7
  • On Pokec-n, UGE-C embeddings from different regions blend together in the t-SNE visualization, unlike the clearly region-clustered embeddings without debiasing.Node color represents region.Source: §6.2 · p. 7, Figure 3 · p. 7

6.3 High-Level Fairness from Embeddings

  • On Pokec-n with node2vec, UGE methods achieve better fairness than baselines on DP and EO while maintaining competitive link-prediction utility, except for age on EO.UGE-C achieves the fairest predictions in this setting.Source: §6.3 · p. 8, Figure 4 · p. 8

6.4 Unbiasedness-Utility Tradeoff in UGE

  • On Pokec-z with GAT, UGE-C has higher utility than CFC at the same Micro-F1 and less bias at the same utility.The comparison tunes regularization weights and evaluates gender and region debiasing.Source: §6.4 · p. 8, Figure 5 · p. 8

7 CONCLUSION

UGE infers a graph with sensitive-attribute influence removed and learns embeddings from it, with experiments reporting debiasing and improved unbiasedness–utility trade-offs. The conclusion also identifies possible directions for refining the framework and extending it to GNNs.

7 CONCLUSION

  • UGE infers a graph with sensitive-attribute influence removed, then learns unbiased node embeddings from that graph.The proposed instances are UGE-W, UGE-R, and their combination UGE-C.Source: §7 · p. 8
  • Experiments report strong debiasing and better unbiasedness–utility trade-offs for UGE in downstream applications.Source: §7 · p. 8
  • Future directions include improving UGE-R’s moment matching and learning UGE-W’s weights for stronger debiasing.The conclusion also suggests generating bias-free graphs from a generative model and designing GNNs to aggregate edges from an inferred bias-free graph.Source: §7 · p. 8

A EXPERIMENTAL SETTINGS

The experiments specify model configurations, training settings, regularization choices, and an approximation for computing the UGE regularizer. They evaluate embedding unbiasedness using classifier Micro-F1.

A EXPERIMENTAL SETTINGS

  • GCN, GAT, and SGC use two convolutional layers with dimensions 64 and 16; node2vec uses walk length 1 for link prediction.Source: A EXPERIMENTAL SETTINGS · p. 10
  • Deep learning models use Adam with step size 0.01 for 800 epochs and normalized weight decay 0.0005.Source: A EXPERIMENTAL SETTINGS · p. 10
  • The reported regularization weights are λ=55.0 for CFC and λ=0.5 for UGE, selected from tested candidate sets.Source: A EXPERIMENTAL SETTINGS · p. 10
  • Sampling about 10% of node groups’ pairs per update is reported to yield promising results for the costly UGE regularizer.Unbiasedness is evaluated with scikit-learn classifiers using Micro-F1.Source: A EXPERIMENTAL SETTINGS · p. 10

B RESULTS

The appendix points readers to additional trade-off results, comparisons among UGE variants, and regularization-weight analyses. Figure 7 encodes attribute prediction and link prediction across embedding models.

B RESULTS

  • Appendix B.1 reports additional unbiasedness–utility trade-off results across embedding models on Pokec-z.Source: B RESULTS · p. 10
  • Figure 7’s left columns show unbiasedness measured by attribute prediction, while its right columns show utility measured by link prediction.Source: Figure 7 · p. 10
  • Appendix B.2 compares UGE-W, UGE-R, and UGE-C, while B.3 studies regularization-weight influence across embedding models.Source: B RESULTS · p. 10

B.1 Additional Analysis on Undebiasedness

On Pokec-z with four graph neural networks, UGE-W has the strongest link prediction performance, UGE-R better debiasing, and UGE-C a better trade-off.

B.1 Additional Analysis on Undebiasedness

  • UGE-C combines UGE-W’s best link prediction performance with UGE-R’s better debiasing effect to produce a better trade-off on Pokec-z with four GNNs.Source: §B.1 · p. 10
  • UGE-W achieves the best link prediction performance among the compared methods on Pokec-z with four GNNs.Source: §B.1 · p. 10
  • UGE-R has better debiasing effect than the compared methods in the reported Pokec-z, four-GNN comparison.Source: §B.1 · p. 10

B.2 Ablation Study

Across four embedding backbones, UGE-R generally debiases better, UGE-W better preserves link-prediction utility, and UGE-C combines these strengths.

B.2 Ablation Study

  • The comparison evaluates UGE-W, UGE-R, and UGE-C with GAT, SGC, GCN, and node2vec embedding models.Source: §B.2 · p. 10
  • UGE-C combines UGE-R’s stronger debiasing with UGE-W’s better link-prediction utility across the evaluated models.Source: §B.2 · p. 10
  • UGE-R generally achieves better debiasing than UGE-W, while UGE-W better maintains downstream link-prediction utility.Source: §B.2 · p. 10

B.3 Unbiasedness-Utility Tradeoff in UGE

The analysis examines UGE’s unbiasedness–utility trade-off across embedding models. Increasing the regularization weight strengthens debiasing but reduces link-prediction utility.

B.3 Unbiasedness-Utility Tradeoff in UGE

  • The trade-off analysis extends beyond Pokec-z with GAT to examine different embedding models.Source: §B.3 · pp. 10–11
  • Table 3 reports Pokec-z prediction performance for four graph neural network embedding models and marks the best debiasedness or utility in each row.Source: Table 3 · p. 11
  • As the regularization weight increases, debiasing strengthens at the cost of link-prediction utility.Source: §B.3 · p. 11

Related papers

Loading 2110.13957v4…