# Residual2Vec: Debiasing graph embedding with random graphs

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 77 references that are in the map.
- First posted on arXiv 14 Oct 2021.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [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)
- [Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings](https://mlsanity.com/paper/1607.06520/) (2016)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Censoring Representations with an Adversary](https://mlsanity.com/paper/1511.05897/) (2015)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Compositional Fairness Constraints for Graph Embeddings](https://mlsanity.com/paper/1905.10674/) (2019)
- [DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification](https://mlsanity.com/paper/1906.02319/) (2019)
- [Understanding Undesirable Word Embedding Associations](https://mlsanity.com/paper/1908.06361/) (2019)
- [Towards Understanding Linear Word Analogies](https://mlsanity.com/paper/1810.04882/) (2018)
- [Random walks and diffusion on networks](https://mlsanity.com/paper/1612.03281/) (2016)
- [Notes on Noise Contrastive Estimation and Negative Sampling](https://mlsanity.com/paper/1410.8251/) (2014)
- [Frequency-based Distortions in Contextualized Word Embeddings](https://mlsanity.com/paper/2104.08465/) (2021)
- [Configuring Random Graph Models with Fixed Degree Sequences](https://mlsanity.com/paper/1608.00607/) (2016)
- [Variational Perspective on Local Graph Clustering](https://mlsanity.com/paper/1602.01886/) (2016)
- [Identification of core-periphery structure in networks](https://mlsanity.com/paper/1409.4813/) (2014)
- [Learning Edge Representations via Low-Rank Asymmetric Projections](https://mlsanity.com/paper/1705.05615/) (2017)
- [Statistical guarantees for local graph clustering](https://mlsanity.com/paper/1906.04863/) (2019)
- [LASAGNE: Locality And Structure Aware Graph Node Embedding](https://mlsanity.com/paper/1710.06520/) (2017)

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

- [On Generalized Degree Fairness in Graph Neural Networks](https://mlsanity.com/paper/2302.03881/) (2023)
- [Toward Degree Bias in Embedding-Based Knowledge Graph Completion](https://mlsanity.com/paper/2302.05044/) (2023)
- [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)
- [A Survey of Few-Shot Learning on Graphs: from Meta-Learning to Pre-Training and Prompt Learning](https://mlsanity.com/paper/2402.01440/) (2024)
- [Robustness of shallow graph embedding methods for community detection](https://mlsanity.com/paper/2405.00636/) (2024)
- [MS-IMAP -- A Multi-Scale Graph Embedding Approach for Interpretable Manifold Learning](https://mlsanity.com/paper/2406.02778/) (2024)
- [Learning Graph Node Embeddings by Smooth Pair Sampling](https://mlsanity.com/paper/2501.12884/) (2025)
- [FairACE: Achieving Degree Fairness in Graph Neural Networks via Contrastive and Adversarial Group-Balanced Training](https://mlsanity.com/paper/2504.09210/) (2025)
- [Mitigating Degree Bias in Graph Representation Learning with Learnable Structural Augmentation and Structural Self-Attention](https://mlsanity.com/paper/2504.15075/) (2025)
- [Fairness-Aware Network Embeddings: Methods, Applications, and Challenges](https://mlsanity.com/paper/2608.19381/) (2026)

## Abstract (arXiv)

Graph embedding maps a graph into a convenient vector-space representation for graph analysis and machine learning applications. Many graph embedding methods hinge on a sampling of context nodes based on random walks. However, random walks can be a biased sampler due to the structural properties of graphs. Most notably, random walks are biased by the degree of each node, where a node is sampled proportionally to its degree. The implication of such biases has not been clear, particularly in the context of graph representation learning. Here, we investigate the impact of the random walks' bias on graph embedding and propose residual2vec, a general graph embedding method that can debias various structural biases in graphs by using random graphs. We demonstrate that this debiasing not only improves link prediction and clustering performance but also allows us to explicitly model salient structural properties in graph embedding.