# CrossWalk: Fairness-enhanced Node Representation Learning

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 31 references that are in the map.
- First posted on arXiv 6 May 2021.

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

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (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)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Compositional Fairness Constraints for Graph Embeddings](https://mlsanity.com/paper/1905.10674/) (2019)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [Operationalizing Individual Fairness with Pairwise Fair Representations](https://mlsanity.com/paper/1907.01439/) (2019)
- [DeBayes: a Bayesian Method for Debiasing Network Embeddings](https://mlsanity.com/paper/2002.11442/) (2020)
- [Adversarial Graph Embeddings for Fair Influence Maximization over Social Networks](https://mlsanity.com/paper/2005.04074/) (2020)
- [On the Efficiency of the Information Networks in Social Media](https://mlsanity.com/paper/1603.04447/) (2016)

## Built on by (most cited first, 30 of 34)

- [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)
- [Subgroup Generalization and Fairness of Graph Neural Networks](https://mlsanity.com/paper/2106.15535/) (2021)
- [Representation Bias in Data: A Survey on Identification and Resolution Techniques](https://mlsanity.com/paper/2203.11852/) (2022)
- [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)
- [Fairness Amidst Non-IID Graph Data: A Literature Review](https://mlsanity.com/paper/2202.07170/) (2022)
- [A Survey on Fairness for Machine Learning on Graphs](https://mlsanity.com/paper/2205.05396/) (2022)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [FairGAT: Fairness-aware Graph Attention Networks](https://mlsanity.com/paper/2303.14591/) (2023)
- [FUGNN: Harmonizing Fairness and Utility in Graph Neural Networks](https://mlsanity.com/paper/2405.17034/) (2024)
- [Rethinking Fair Graph Neural Networks from Re-balancing](https://mlsanity.com/paper/2407.11624/) (2024)
- [Graph Learning with Localized Neighborhood Fairness](https://mlsanity.com/paper/2212.12040/) (2022)
- [One Fits All: Learning Fair Graph Neural Networks for Various Sensitive Attributes](https://mlsanity.com/paper/2406.13544/) (2024)
- [Deceptive Fairness Attacks on Graphs via Meta Learning](https://mlsanity.com/paper/2310.15653/) (2023)
- [FairMILE: Towards an Efficient Framework for Fair Graph Representation Learning](https://mlsanity.com/paper/2211.09925/) (2022)
- [Impact Of Missing Data Imputation On The Fairness And Accuracy Of Graph Node Classifiers](https://mlsanity.com/paper/2211.00783/) (2022)
- [Disparity, Inequality, and Accuracy Tradeoffs in Graph Neural Networks for Node Classification](https://mlsanity.com/paper/2308.09596/) (2023)
- [On Explaining Unfairness: An Overview](https://mlsanity.com/paper/2402.10762/) (2024)
- [Benchmarking Fairness-aware Graph Neural Networks in Knowledge Graphs](https://mlsanity.com/paper/2510.18473/) (2025)
- [Structural Bias Beyond Homophily: A Study of Fairness in Link Prediction](https://mlsanity.com/paper/2602.11802/) (2026)
- [Fair Graph Neural Network with Supervised Contrastive Regularization](https://mlsanity.com/paper/2404.06090/) (2024)
- [DQ4FairIM: Fairness-aware Influence Maximization using Deep Reinforcement Learning](https://mlsanity.com/paper/2512.00545/) (2025)
- [Fairness-aware PageRank via Edge Reweighting](https://mlsanity.com/paper/2512.08055/) (2025)
- [FairRARI: A Plug and Play Framework for Fairness-Aware PageRank](https://mlsanity.com/paper/2602.08589/) (2026)
- [Fair Graph Machine Learning under Adversarial Missingness Processes](https://mlsanity.com/paper/2311.01591/) (2023)
- [Information Loss and Disparate Effects in Network Embeddings](https://mlsanity.com/paper/2509.12396/) (2025)
- [Estimating Fair Graphs from Graph-Stationary Data](https://mlsanity.com/paper/2510.07536/) (2025)
- [Model-Agnostic Fairness Regularization for GNNs with Incomplete Sensitive Information](https://mlsanity.com/paper/2512.03074/) (2025)
- [A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Mining](https://mlsanity.com/paper/2601.12751/) (2026)

## Abstract (arXiv)

The potential for machine learning systems to amplify social inequities and unfairness is receiving increasing popular and academic attention. Much recent work has focused on developing algorithmic tools to assess and mitigate such unfairness. However, there is little work on enhancing fairness in graph algorithms. Here, we develop a simple, effective and general method, CrossWalk, that enhances fairness of various graph algorithms, including influence maximization, link prediction and node classification, applied to node embeddings. CrossWalk is applicable to any random walk based node representation learning algorithm, such as DeepWalk and Node2Vec. The key idea is to bias random walks to cross group boundaries, by upweighting edges which (1) are closer to the groups' peripheries or (2) connect different groups in the network. CrossWalk pulls nodes that are near groups' peripheries towards their neighbors from other groups in the embedding space, while preserving the necessary structural properties of the graph. Extensive experiments show the effectiveness of our algorithm to enhance fairness in various graph algorithms, including influence maximization, link prediction and node classification in synthetic and real networks, with only a very small decrease in performance.