# Information Loss and Disparate Effects in Network Embeddings

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 36 references that are in the map.
- First posted on arXiv 15 Sep 2025.

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

- [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)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [A Survey on Network Embedding](https://mlsanity.com/paper/1711.08752/) (2017)
- [Compositional Fairness Constraints for Graph Embeddings](https://mlsanity.com/paper/1905.10674/) (2019)
- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [FairDrop: Biased Edge Dropout for Enhancing Fairness in Graph Representation Learning](https://mlsanity.com/paper/2104.14210/) (2021)
- [DeBayes: a Bayesian Method for Debiasing Network Embeddings](https://mlsanity.com/paper/2002.11442/) (2020)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [CrossWalk: Fairness-enhanced Node Representation Learning](https://mlsanity.com/paper/2105.02725/) (2021)
- [The impossibility of low rank representations for triangle-rich complex networks](https://mlsanity.com/paper/2003.12635/) (2020)
- [Node Embeddings and Exact Low-Rank Representations of Complex Networks](https://mlsanity.com/paper/2006.05592/) (2020)
- [The Class of Random Graphs Arising from Exchangeable Random Measures](https://mlsanity.com/paper/1512.03099/) (2015)
- [Asymptotics of Network Embeddings Learned via Subsampling](https://mlsanity.com/paper/2107.02363/) (2021)
- [NodeSim: Node Similarity based Network Embedding for Diverse Link Prediction](https://mlsanity.com/paper/2102.00785/) (2021)
- [Fairness Rising from the Ranks: HITS and PageRank on Homophilic Networks](https://mlsanity.com/paper/2402.13787/) (2024)
- [Promoting Fairness in Link Prediction with Graph Enhancement](https://mlsanity.com/paper/2409.08658/) (2024)
- [Compressibility Barriers to Neighborhood-Preserving Data Visualizations](https://mlsanity.com/paper/2508.07119/) (2025)
- [Dot Product is All You Need: Bridging the Gap Between Item Recommendation and Link Prediction](https://mlsanity.com/paper/2409.07433/) (2024)

## Abstract (arXiv)

An extensive line of work studies fairness interventions for network embeddings, but less is known about their baseline behavior. In this work, we ask: how do baseline embeddings (without fairness interventions) produce disparate effects at the representation level? We analyze the asymptotic behavior of low-dimensional embeddings on stochastic block model (SBM) graphs, which encode both homophily and group structure. We characterize exact conditions under which embeddings cause information loss, showing that the amount of information loss depends directly on the graph's density and assortativity. Notably, very different graphs can produce identical embeddings in the limit, and this non-invertibility disproportionately affects smaller and sparser communities. As a result, simple downstream tasks, such as link prediction, introduce higher error rates for these communities, helping explain disparities widely observed in practice.