# Unbiased Graph Embedding with Biased Graph Observations

arXiv: https://arxiv.org/abs/2110.13957 · HTML: https://mlsanity.com/paper/2110.13957/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 50 references that are in the map.
- First posted on arXiv 26 Oct 2021.

## Builds on (most cited first, 20 of 20)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Learning Adversarially Fair and Transferable Representations](https://mlsanity.com/paper/1802.06309/) (2018)
- [Fairness in Criminal Justice Risk Assessments: The State of the Art](https://mlsanity.com/paper/1703.09207/) (2017)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information](https://mlsanity.com/paper/2009.01454/) (2020)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [Towards a Unified Framework for Fair and Stable Graph Representation Learning](https://mlsanity.com/paper/2102.13186/) (2021)
- [Compositional Fairness Constraints for Graph Embeddings](https://mlsanity.com/paper/1905.10674/) (2019)
- [DeBayes: a Bayesian Method for Debiasing Network Embeddings](https://mlsanity.com/paper/2002.11442/) (2020)
- [Conditional Network Embeddings](https://mlsanity.com/paper/1805.07544/) (2018)
- [MONET: Debiasing Graph Embeddings via the Metadata-Orthogonal Training Unit](https://mlsanity.com/paper/1909.11793/) (2019)

## Built on by (most cited first, 28 of 28)

- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [DeAR: Debiasing Vision-Language Models with Additive Residuals](https://mlsanity.com/paper/2303.10431/) (2023)
- [Fair Attribute Completion on Graph with Missing Attributes](https://mlsanity.com/paper/2302.12977/) (2023)
- [Counterfactual Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.01391/) (2023)
- [Fairness-Aware Graph Neural Networks: A Survey](https://mlsanity.com/paper/2307.03929/) (2023)
- [A Survey on Fairness for Machine Learning on Graphs](https://mlsanity.com/paper/2205.05396/) (2022)
- [FairSIN: Achieving Fairness in Graph Neural Networks through Sensitive Information Neutralization](https://mlsanity.com/paper/2403.12474/) (2024)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [Implications of Topological Imbalance for Representation Learning on Biomedical Knowledge Graphs](https://mlsanity.com/paper/2112.06567/) (2021)
- [Graph Learning with Localized Neighborhood Fairness](https://mlsanity.com/paper/2212.12040/) (2022)
- [COFFEE: Counterfactual Fairness for Personalized Text Generation in Explainable Recommendation](https://mlsanity.com/paper/2210.15500/) (2022)
- [GFairHint: Improving Individual Fairness for Graph Neural Networks via Fairness Hint](https://mlsanity.com/paper/2305.15622/) (2023)
- [Deceptive Fairness Attacks on Graphs via Meta Learning](https://mlsanity.com/paper/2310.15653/) (2023)
- [Adversarial Attacks on Fairness of Graph Neural Networks](https://mlsanity.com/paper/2310.13822/) (2023)
- [Globally Interpretable Graph Learning via Distribution Matching](https://mlsanity.com/paper/2306.10447/) (2023)
- [Are Your Models Still Fair? Fairness Attacks on Graph Neural Networks via Node Injections](https://mlsanity.com/paper/2406.03052/) (2024)
- [Adapting to Heterophilic Graph Data with Structure-Guided Neighbor Discovery](https://mlsanity.com/paper/2506.08871/) (2025)
- [Breaking the Dyadic Barrier: Rethinking Fairness in Link Prediction Beyond Demographic Parity](https://mlsanity.com/paper/2511.06568/) (2025)
- [Structural Bias Beyond Homophily: A Study of Fairness in Link Prediction](https://mlsanity.com/paper/2602.11802/) (2026)
- [ComFairGNN: Community Fair Graph Neural Network](https://mlsanity.com/paper/2411.04371/) (2024)
- [Towards Fair Graph Representation Learning in Social Networks](https://mlsanity.com/paper/2410.11493/) (2024)
- [Let's Grow an Unbiased Community: Guiding the Fairness of Graphs via New Links](https://mlsanity.com/paper/2508.15499/) (2025)
- [FairAD: Computationally Efficient Fair Graph Clustering via Algebraic Distance](https://mlsanity.com/paper/2510.27136/) (2025)
- [A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Mining](https://mlsanity.com/paper/2601.12751/) (2026)
- [Mitigating topology biases in Graph Diffusion via Counterfactual Intervention](https://mlsanity.com/paper/2603.02005/) (2026)
- [k-hop Fairness: Addressing Disparities in Graph Link Prediction Beyond First-Order Neighborhoods](https://mlsanity.com/paper/2603.03867/) (2026)
- [How Predicted Links Influence Network Evolution: Disentangling Choice and Algorithmic Feedback in Dynamic Graphs](https://mlsanity.com/paper/2603.03945/) (2026)

## Abstract (arXiv)

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.