Research map / Graph learning / Graph self-supervised learning
Information Loss and Disparate Effects in Network Embeddings
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes the asymptotic kernel of dot-product network embeddings trained with uniform vertex subsampling and cross-entropy on 2- and k-block SBMs, showing information loss depends on density and assortativity, creating equivalence classes that overpredict edges for small/sparse communities.
Problem
Baseline (non-fair) network embeddings can produce disparate error across communities, but it is unclear how the embedding process itself, via information loss, causes these representation-level disparities.
Approach
Characterizes exactly, for 2-block SBMs, when inner-product embeddings preserve full, partial, or no information, shows that graphs with very different densities share identical limiting kernels along lines in parameter space, and derives that these embeddings densify smaller and sparser communities, causing link-prediction overprediction.
Key results
- For 2-block SBMs, the information-loss regimes are exactly characterized by p,q,r (not community sizes): dense assortative region preserves all information, sparse heterophilic region loses all, middle region loses partial information.
- Equivalence classes of identically embedded SBMs are lines in (p,q,r) space spanning from very sparse to very dense graphs.
- On 100 Facebook100 networks, the empirical densification ratio correlates strongly with the theoretically predicted 1/eta^2 (based only on three block-average densities).
Surprising findings
- Very sparse and very dense SBMs can produce identical embeddings in the limit, so embedding density is not encoded in the representation.
- Smaller and sparser communities are densified, so inner-product link prediction overpredicts their edges.
Limitations
- Analysis restricted to stochastic block models and uniform vertex sampling; not general graphons or random-walk samplers like DeepWalk/node2vec.
- Exact characterization only for 2-block SBMs; k-block results are numerical.
- Analysis of word-context style embeddings is left open.
Experimental setup
Datasets: Facebook100 synthetic 2-block and 3-block SBMs
Benchmarks: Facebook100
Metrics: densification ratio link prediction overprediction rate
Baselines: FairWalk
Builds on: Davison & Austern asymptotics of network embeddings node2vec DeepWalk variational graph auto-encoders
Closest papers by meaning
- How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings (ICLR 2025 · similarity 0.87)
- Convergence Guarantees for the DeepWalk Embedding on Block Models (ICML 2024 · similarity 0.86)
- Harnessing Multiple Correlated Networks for Exact Community Recovery (NeurIPS 2024 · similarity 0.86)
- Networked Inequality: Preferential Attachment Bias in Graph Neural Network Link Prediction (ICML 2024 · similarity 0.86)
- Non-Euclidean Mixture Model for Social Network Embedding (NeurIPS 2024 · similarity 0.86)
- Community Detection Guarantees using Embeddings Learned by Node2Vec (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.