# Toward Structure Fairness in Dynamic Graph Embedding: A Trend-aware Dual Debiasing Approach

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 50 references that are in the map.
- First posted on arXiv 19 Jun 2024.

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Hyperbolic Graph Convolutional Neural Networks](https://mlsanity.com/paper/1910.12933/) (2019)
- [Are Graph Augmentations Necessary? Simple Graph Contrastive Learning for Recommendation](https://mlsanity.com/paper/2112.08679/) (2021)
- [Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information](https://mlsanity.com/paper/2009.01454/) (2020)
- [ROLAND: Graph Learning Framework for Dynamic Graphs](https://mlsanity.com/paper/2208.07239/) (2022)
- [Measuring Fairness in Ranked Outputs](https://mlsanity.com/paper/1610.08559/) (2016)
- [Fairness-Aware Explainable Recommendation over Knowledge Graphs](https://mlsanity.com/paper/2006.02046/) (2020)
- [Few-Shot Knowledge Graph Completion](https://mlsanity.com/paper/1911.11298/) (2019)
- [Towards Robust Graph Neural Networks for Noisy Graphs with Sparse Labels](https://mlsanity.com/paper/2201.00232/) (2022)
- [Improving Fairness in Graph Neural Networks via Mitigating Sensitive Attribute Leakage](https://mlsanity.com/paper/2206.03426/) (2022)
- [Dynamic Graph Neural Networks for Sequential Recommendation](https://mlsanity.com/paper/2104.07368/) (2021)
- [Learning Fair Policies in Decentralized Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2012.09421/) (2020)
- [Uncovering the Structural Fairness in Graph Contrastive Learning](https://mlsanity.com/paper/2210.03011/) (2022)
- [Self-supervised Hypergraph Representation Learning for Sociological Analysis](https://mlsanity.com/paper/2212.11440/) (2022)
- [Temporal Meta-path Guided Explainable Recommendation](https://mlsanity.com/paper/2101.01433/) (2021)
- [Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve](https://mlsanity.com/paper/2105.05308/) (2021)
- [Explainable Fairness in Recommendation](https://mlsanity.com/paper/2204.11159/) (2022)
- [Enabling Long-term Fairness in Dynamic Resource Allocation](https://mlsanity.com/paper/2208.05898/) (2022)
- [Fairness-Aware Node Representation Learning](https://mlsanity.com/paper/2106.05391/) (2021)
- [Reinforced Path Reasoning for Counterfactual Explainable Recommendation](https://mlsanity.com/paper/2207.06674/) (2022)
- [Shuffling Recurrent Neural Networks](https://mlsanity.com/paper/2007.07324/) (2020)
- [Time-aware Dynamic Graph Embedding for Asynchronous Structural Evolution](https://mlsanity.com/paper/2207.00594/) (2022)
- [Attention Is Not the Only Choice: Counterfactual Reasoning for Path-Based Explainable Recommendation](https://mlsanity.com/paper/2401.05744/) (2024)
- [Counter-Empirical Attacking based on Adversarial Reinforcement Learning for Time-Relevant Scoring System](https://mlsanity.com/paper/2311.05144/) (2023)
- [Modelling the long-term fairness dynamics of data-driven targeted help on job seekers](https://mlsanity.com/paper/2208.08881/) (2022)

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

- [Revisiting Dynamic Graph Clustering via Matrix Factorization](https://mlsanity.com/paper/2502.06117/) (2025)
- [FairTP: A Prolonged Fairness Framework for Traffic Prediction](https://mlsanity.com/paper/2412.16214/) (2024)
- [Fairness in Augmented Graph Learning: A Survey](https://mlsanity.com/paper/2504.21296/) (2025)
- [MSCI: Addressing CLIP's Inherent Limitations for Compositional Zero-Shot Learning](https://mlsanity.com/paper/2505.10289/) (2025)
- [Node Role-Guided LLMs for Dynamic Graph Clustering](https://mlsanity.com/paper/2603.13799/) (2026)
- [Fairness-Aware Network Embeddings: Methods, Applications, and Challenges](https://mlsanity.com/paper/2608.19381/) (2026)

## Abstract (arXiv)

Recent studies successfully learned static graph embeddings that are structurally fair by preventing the effectiveness disparity of high- and low-degree vertex groups in downstream graph mining tasks. However, achieving structure fairness in dynamic graph embedding remains an open problem. Neglecting degree changes in dynamic graphs will significantly impair embedding effectiveness without notably improving structure fairness. This is because the embedding performance of high-degree and low-to-high-degree vertices will significantly drop close to the generally poorer embedding performance of most slightly changed vertices in the long-tail part of the power-law distribution. We first identify biased structural evolutions in a dynamic graph based on the evolving trend of vertex degree and then propose FairDGE, the first structurally Fair Dynamic Graph Embedding algorithm. FairDGE learns biased structural evolutions by jointly embedding the connection changes among vertices and the long-short-term evolutionary trend of vertex degrees. Furthermore, a novel dual debiasing approach is devised to encode fair embeddings contrastively, customizing debiasing strategies for different biased structural evolutions. This innovative debiasing strategy breaks the effectiveness bottleneck of embeddings without notable fairness loss. Extensive experiments demonstrate that FairDGE achieves simultaneous improvement in the effectiveness and fairness of embeddings.