SIGKDD 2023 Tutorial - Fairness in Graph Machine Learning: Recent Advances and Future Prospectives

Abstract

Graph data is ubiquitous across a plethora of real-world applications. Correspondingly, graph machine learning algorithms have become popular tools in helping us gain a deeper understanding of these graphs. Despite their effectiveness, most graph machine learning algorithms lack considerations for fairness, which can result in discriminatory outcomes against certain demographic subgroups or individuals. As a result, there is a growing societal concern about mitigating the bias exhibited in these algorithms. To tackle the problem of algorithmic bias in graph machine learning algorithms, this tutorial aims to provide a comprehensive overview of recent research progress in measuring and mitigating the bias in machine learning algorithms on graphs. Specifically, this tutorial first introduces several widely-used fairness notions and the corresponding metrics. Then, we present a well-organized theoretical understanding of bias in graph machine learning algorithms, followed by a summary of existing techniques to debias graph machine learning algorithms. Furthermore, we demonstrate how different real-world applications benefit from these graph machine learning algorithms after debiasing. Finally, we provide insights on current research challenges and open questions to encourage further advances.
Keywords: Graph Machine Learning Algorithms, Debiasing, Algorithmic Fairness.

Part 1: Background Introduction: Fairness in Graph ML (15 mins)

Motivation & Significance of fulfilling fairness in graph machine learning algorithms.
The unique challenges in debiasing graph machine learning algorithms.
An overview of graph machine learning tasks that have been studied on algorithmic bias mitigation.
An overview of the applications which benefit from debiased graph machine learning algorithms.

Part 2: Fairness Notions and Metrics in Graph ML (40 mins)

Why is it necessary to define fairness in different ways?
Group Fairness: graph machine learning algorithms should not render discriminatory predictions or decisions against individuals from any specific sensitive subgroup.
Individual Fairness: graph machine learning algorithms should render similar predictions for similar individuals.
Other popular fairness notions: counterfactual fairness and degree-related fairness are included.
Application-Specific Fairness: fairness notions defined in specific real-world applications.

Part 3: Theoretical Understanding of Bias in Graph ML (40 mins)

Mean-discrepancy analysis.
Correlation-based analysis.
Entropy-based analysis.
PAC-Bayesian analysis.
Gradient-based analysis.

Part 4: Techniques for Fair Node Embedding Learning (40 mins)

Optimization with regularization.
Adversarial learning.
Graph data augmentation.
Re-balancing.
Orthogonal projection.
Bayesian debiasing.

Part 5: Real-World Applications (30 mins)

Fairness in recommender systems.
Fairness in applications based on knowledge graphs.
Other real-world applications, including criminal justice, economics, social networks, healthcare, etc.

Part 6: Summary, Challenges, and Future Directions (15 mins)

Summary of presented fairness notions, metrics, theoretical understanding of bias, and debiasing techniques in graph ML.
Summary of current challenges and future directions.
Discussion with the audience on which fairness notion & metrics should be applied to their own application scenarios.

Related Materials

Fairness in graph mining: A survey

Authors: Yushun Dong, Jing Ma, Chen Chen, and Jundong Li. Accepted by TKDE.

Novel Fairness Taxonomy. We propose a novel taxonomy of fairness notions in graph mining, including five groups of fairness notions.
Comprehensive Technique Review. We provide a comprehensive and organized review of six groups of techniques that are commonly utilized to promote fair- ness in graph mining algorithms.
Rich Public-Available Resources. We collect rich resources of algorithms and benchmark datasets that can be employed for fair graph mining research.
Challenges and Future Directions. We present the limitations of current research and point out pressing challenges.

Paper

PyGDebias: A library of Fairness-Aware Graph Mining Algorithms

Authors & Acknowledgements: Yushun Dong, Song Wang, Zaiyi Zheng, Zhenyu Lei, Alex Jing Huang, Jing Ma, Chen Chen, Jundong Li.

We developed this library PyGDebias featured for built-in datasets and implementations of popular fairness-aware graph mining algorithms for the study of algorithmic fairness on graphs.
26 graph datasets (including 24 commonly used ones and two newly constructed ones) are collected, and 13 algorithms are implemented in this library.

GitHub

Key References

[1] Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. 2021. Towards a unified framework for fair and stable graph representation learning. In UAI.
[2] MarioArduini,LorenzoNoci,FedericoPirovano,CeZhang,YashRajShrestha, and Bibek Paudel. 2020. Adversarial Learning for Debiasing Knowledge Graph Embeddings. In KDD.
[3] Yushun Dong, Jian Kang, Hanghang Tong, and Jundong Li. 2021. Individual fairness for graph neural networks: A ranking based approach. In KDD.
[4] Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. 2022. Edits: Modeling and mitigating data bias for graph neural networks. In WWW.
[5] Yushun Dong, Jing Ma, Chen Chen, and Jundong Li. 2022. Fairness in Graph Mining: A Survey. TKDE.
[6] Yushun Dong, Song Wang, Jing Ma, Ninghao Liu, and Jundong Li. 2023. Interpreting Unfairness in Graph Neural Networks via Training Node Attribution. In AAAI.
[7] Yushun Dong, Song Wang, Yu Wang, Tyler Derr, and Jundong Li. 2022. On structural explanation of bias in graph neural networks. In KDD.
[8] Yushun Dong, Binchi Zhang, Yiling Yuan, Na Zou, Qi Wang, and Jundong Li. 2023. RELIANT: Fair Knowledge Distillation for Graph Neural Networks. In SDM.
[9] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012. Fairness through awareness. In ITCS.
[10] Golnoosh Farnadi, Behrouz Babaki, and Michel Gendreau. 2020. A Unifying Framework for Fairness-Aware Influence Maximization. In Companion of WWW.
[11] Shubham Gupta and Ambedkar Dukkipati. 2021. Protecting individual interests across clusters: Spectral clustering with guarantees. arXiv preprint arXiv:2105.03714 (2021).
[12] Moritz Hardt, Eric Price, and Nati Srebro. 2016. Equality of opportunity in supervised learning. NeurIPS.
[13] ZhimengJiang,XiaotianHan,ChaoFan,ZiruiLiu,NaZou,AliMostafavi,and Xia Hu. 2022. Fmp: Toward fair graph message passing against topology bias. arXiv preprint arXiv:2202.04187 (2022).
[14] Jian Kang, Jingrui He, Ross Maciejewski, and Hanghang Tong. 2020. Inform: Individual fairness on graph mining. In KDD.
[15] Jian Kang, Yan Zhu, Yinglong Xia, Jiebo Luo, and Hanghang Tong. 2022. Rawlsgcn: Towards Rawlsian difference principle on graph convolutional network. In WWW.
[16] Oyku Deniz Kose and Yanning Shen. 2021. Fairness-aware node representation learning. arXiv preprint arXiv:2106.05391 (2021).
[17] Oyku Deniz Kose and Yanning Shen. 2022. Fair contrastive learning on graphs. TSIPN.
[18] Oyku Deniz Kose and Yanning Shen. 2022. Fairness-aware Adaptive Network Link Prediction. In EUSIPCO.
[19] Oyku Deniz Kose and Yanning Shen. 2022. Fairness-aware selective sampling on attributed graphs. In ICASSP.
[20] Oyku Deniz Kose and Yanning Shen. 2023. Fair node representation learning via adaptive data augmentation. TNNLS.
[21] Oyku Deniz Kose and Yanning Shen. 2023. FairGAT: Fairness-aware Graph Attention Networks. arXiv preprint arXiv:2303.14591 (2023).
[22] Oyku Deniz Kose and Yanning Shen. 2023. Fast&Fair: Training Acceleration and Bias Mitigation for GNNs. TMLR (2023).
[23] Yunqi Li, Hanxiong Chen, Zuohui Fu, Yingqiang Ge, and Yongfeng Zhang. 2021. User-oriented Fairness in Recommendation. In WWW.
[24] Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. 2021. Subgroup generalization and fairness of graph neural networks. NeurIPS.
[25] Weihao Song, Yushun Dong, Ninghao Liu, and Jundong Li. 2022. Guide: Group equality informed individual fairness in graph neural networks. In KDD.
[26] Yu Wang, Yuying Zhao, Yushun Dong, Huiyuan Chen, Jundong Li, and Tyler Derr. 2022. Improving fairness in graph neural networks via mitigating sensitive attribute leakage. In KDD.
[27] Enyan Dai and Suhang Wang. 2021. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In WSDM.

Presenters

We thank our presenters for delivering such an amazing tutorial @ SIGKDD'23!

Yushun Dong

Yushun Dong is a fourth-year Ph.D. student in the Department of Electrical and Computer Engineering at the University of Virginia. His research interest broadly lies in the realm of graph mining, with a particular interest in algorithmic fairness related problems in graph machine learning. He has been studying how to mitigate and interpret the exhibited bias in graph mining algorithms for more than two years, and his related papers have been accepted in top-tier conferences, including SIGKDD and WWW. He is also the first author of a recent survey paper (accepted by TKDE) on algorithmic fairness in graph mining.

Oyku Deniz Kose

Oyku Deniz Kose received her B.S. and M.S. from Bogazici University, Istanbul, Turkey, in 2017 and 2020, respectively. During her master’s studies, her research centered on speech and multimodal signal processing. Currently, she is a Ph.D. student in the Department of Electrical Engineering and Computer Science, University of California Irvine, Irvine, CA, USA. Her current research mainly focuses on trustworthy machine learning with a specific interest in graph-based learning. She was the recipient of the Samueli Endowed Fellowship at UC Irvine in 2020, and a research intern at Google Responsible AI group in the summer of 2023.

Yanning Shen

Yanning Shen is an assistant professor with the EECS department at the University of California, Irvine. Her research interests span the areas of machine learning, network science, and data science. She received her Ph.D. degree from the University of Minnesota in 2019. She was selected as a Rising Star in EECS by Stanford University in 2017. She received the Microsoft Academic Grant Award for AI Research in 2021, the Google Re- search Scholar Award in 2022, and the Hellman Fellowship in 2022. She is also an honoree of the MIT Technology Review 35 Innovators under 35 Asia Pacific in 2022.

Jundong Li

Jundong Li is an Assistant Professor in the Department of Electrical and Computer Engineering, with a joint appointment in the Department of Computer Science, and the School of Data Science. He received Ph.D. degree in Computer Science at Arizona State University in 2019. His research interests are in data mining, machine learning, and causal inference. He has published over 100 articles in high-impact venues and won prestigious awards including NSF CAREER Award, JP Morgan Chase Faculty Research Award, Cisco Faculty Research Award, and being selected for the AAAI 2021 New Faculty Highlights program.

Fairness in Graph Machine Learning: Recent Advances and Future Prospectives