Information Loss and Disparate Effects in Network Embeddings

2025/09/15 by Gabriel Chuang, Chuang, Gabriel, Augustin Chaintreau +1
Physics and Astronomy · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Opinion Dynamics and Social Influence #Social and Information Networks (cs.SI)

paper · pdf · doi:10.48550/arxiv.2509.12396

openalex publication_date 2025/09/15 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/30

Abstract

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.

Citations

• Compressibility Barriers to Neighborhood-Preserving Data Visualizations
• Promoting Fairness in Link Prediction with Graph Enhancement
• Dot Product is All You Need: Bridging the Gap Between Item Recommendation and Link Prediction
• Fairness in Graph Mining: A Survey
• CrossWalk: Fairness-enhanced Node Representation Learning
• NodeSim: Node Similarity based Network Embedding for Diverse Link Prediction
• Node Embeddings and Exact Low-Rank Representations of Complex Networks
• DeBayes: a Bayesian Method for Debiasing Network Embeddings
• Generalization and Representational Limits of Graph Neural Networks
• Compositional Fairness Constraints for Graph Embeddings
• A Survey on Network Embedding
• Variational Graph Auto-Encoders
• Community Detection in Degree-Corrected Block Models
• node2vec: Scalable Feature Learning for Networks
• The Class of Random Graphs Arising from Exchangeable Random Measures
• DeepWalk
• Stochastic blockmodels: First steps
• Centrality in social networks conceptual clarification

Related

• DeepWalking Backwards: From Embeddings Back to Graphs
• Classic Graph Structural Features Outperform Factorization-Based Graph Embedding Methods on Community Labeling
• Network Embedding: An Overview
• Zoo Guide to Network Embedding
• Community Detection Guarantees Using Embeddings Learned by Node2Vec