research-article

Open access

GUIDE: Group Equality Informed Individual Fairness in Graph Neural Networks

Authors:

Jundong LiAuthors Info & Claims

KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Pages 1625 - 1634

https://doi.org/10.1145/3534678.3539346

Published: 14 August 2022 Publication History

Abstract

Graph Neural Networks (GNNs) are playing increasingly important roles in critical decision-making scenarios due to their exceptional performance and end-to-end design. However, concerns have been raised that GNNs could make biased decisions against underprivileged groups or individuals. To remedy this issue, researchers have proposed various fairness notions including individual fairness that gives similar predictions to similar individuals. However, existing methods in individual fairness rely on Lipschitz condition: they only optimize overall individual fairness and disregard equality of individual fairness between groups. This leads to drastically different levels of individual fairness among groups. We tackle this problem by proposing a novel GNN framework GUIDE to achieve group equality informed individual fairness in GNNs. We aim to not only achieve individual fairness but also equalize the levels of individual fairness among groups. Specifically, our framework operates on the similarity matrix of individuals to learn personalized attention to achieve individual fairness without group level disparity. Comprehensive experiments on real-world datasets demonstrate that GUIDE obtains good balance of group equality informed individual fairness and model utility. The open-source implementation of GUIDE can be found here: https://github.com/mikesong724/GUIDE.

References

[1]

Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. 2021. Towards a Unified Framework for Fair and Stable Graph Representation Learning. CoRR, Vol. abs/2102.13186 (2021). arxiv: 2102.13186 https://arxiv.org/abs/2102.13186

[2]

Punam Bedi and Chhavi Sharma. 2016. Community detection in social networks. Wiley Interdiscip. Rev. Data Min. Knowl. Discov., Vol. 6, 3 (2016), 115--135.

Digital Library

[3]

Avishek Joey Bose and William L. Hamilton. 2019. Compositional Fairness Constraints for Graph Embeddings. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9--15 June 2019, Long Beach, California, USA (Proceedings of Machine Learning Research, Vol. 97). PMLR, 715--724.

[4]

Enyan Dai and Suhang Wang. 2021. Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining (Virtual Event, Israel) (WSDM '21). Association for Computing Machinery, New York, NY, USA, 680--688. https://doi.org/10.1145/3437963.3441752

Digital Library

[5]

Yushun Dong, Jian Kang, Hanghang Tong, and Jundong Li. 2021. Individual Fairness for Graph Neural Networks: A Ranking based Approach. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 300--310.

Digital Library

[6]

Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. 2022a. Edits: Modeling and mitigating data bias for graph neural networks. In Proceedings of the ACM Web Conference 2022. 1259--1269.

Digital Library

[7]

Yushun Dong, Jing Ma, Chen Chen, and Jundong Li. 2022b. Fairness in Graph Mining: A Survey. arXiv preprint arXiv:2204.09888 (2022).

[8]

Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. http://archive.ics.uci.edu/ml

[9]

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. 2012. Fairness through awareness. In Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8--10, 2012. ACM, 214--226.

[10]

David Garc'i a-Soriano and Francesco Bonchi. 2021. Maxmin-Fair Ranking: Individual Fairness under Group-Fairness Constraints. CoRR, Vol. abs/2106.08652 (2021). https://arxiv.org/abs/2106.08652

[11]

Lin Gong, Lu Lin, Weihao Song, and Hongning Wang. 2020. JNET: Learning User Representations via Joint Network Embedding and Topic Embedding. In WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining, Houston, TX, USA, February 3--7, 2020. ACM, 205--213.

Digital Library

[12]

William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4--9, 2017, Long Beach, CA, USA. 1024--1034.

[13]

Moritz Hardt, Eric Price, and Nati Srebro. 2016. Equality of Opportunity in Supervised Learning. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5--10, 2016, Barcelona, Spain. 3315--3323.

Digital Library

[14]

Mohammad Al Hasan and Mohammed J. Zaki. 2011. A Survey of Link Prediction in Social Networks. In Social Network Data Analytics, Charu C. Aggarwal (Ed.). Springer, 243--275.

[15]

Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and Philip S. Yu. 2020. A Survey on Knowledge Graphs: Representation, Acquisition and Applications. CoRR, Vol. abs/2002.00388 (2020). https://arxiv.org/abs/2002.00388

[16]

Jian Kang, Jingrui He, Ross Maciejewski, and Hanghang Tong. 2020. InFoRM: Individual Fairness on Graph Mining. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23--27, 2020. ACM, 379--389.

[17]

Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7--9, 2015, Conference Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). http://arxiv.org/abs/1412.6980

[18]

Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24--26, 2017, Conference Track Proceedings. OpenReview.net.

[19]

Matth"a us Kleindessner, Samira Samadi, Pranjal Awasthi, and Jamie Morgenstern. 2019. Guarantees for Spectral Clustering with Fairness Constraints. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9--15 June 2019, Long Beach, California, USA (Proceedings of Machine Learning Research, Vol. 97). PMLR, 3458--3467.

[20]

Preethi Lahoti, Krishna P. Gummadi, and Gerhard Weikum. 2019. Operationalizing Individual Fairness with Pairwise Fair Representations. Proc. VLDB Endow., Vol. 13, 4 (2019), 506--518.

Digital Library

[21]

Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. 2021. A Survey on Bias and Fairness in Machine Learning. ACM Comput. Surv., Vol. 54, 6, Article 115 (July 2021), 35 pages. https://doi.org/10.1145/3457607

Digital Library

[22]

Tahleen A. Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. 2019. Fairwalk: Towards Fair Graph Embedding. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10--16, 2019. ijcai.org, 3289--3295.

[23]

L. Takac and Michal Zábovský. 2012. Data analysis in public social networks. International Scientific Conference and International Workshop Present Day Trends of Innovations (01 2012), 1--6.

[24]

Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018a. Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net.

[25]

Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018b. Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net. https://openreview.net/forum?id=rJXMpikCZ

[26]

Daixin Wang, Yuan Qi, Jianbin Lin, Peng Cui, Quanhui Jia, Zhen Wang, Yanming Fang, Quan Yu, Jun Zhou, and Shuang Yang. 2019. A Semi-Supervised Graph Attentive Network for Financial Fraud Detection. In 2019 IEEE International Conference on Data Mining, ICDM 2019, Beijing, China, November 8--11, 2019. IEEE, 598--607.

[27]

Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. 2021. CurGraph: Curriculum Learning for Graph Classification. In WWW '21: The Web Conference 2021, Virtual Event / Ljubljana, Slovenia, April 19--23, 2021. ACM / IW3C2, 1238--1248. https://doi.org/10.1145/3442381.3450025

Digital Library

[28]

Qitian Wu, Hengrui Zhang, Xiaofeng Gao, Peng He, Paul Weng, Han Gao, and Guihai Chen. 2019. Dual Graph Attention Networks for Deep Latent Representation of Multifaceted Social Effects in Recommender Systems. In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13--17, 2019. ACM, 2091--2102. https://doi.org/10.1145/3308558.3313442

Digital Library

[29]

Shiwen Wu, Wentao Zhang, Fei Sun, and Bin Cui. 2020. Graph Neural Networks in Recommender Systems: A Survey. CoRR, Vol. abs/2011.02260 (2020). https://arxiv.org/abs/2011.02260

[30]

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6--9, 2019. OpenReview.net.

[31]

Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018. Representation Learning on Graphs with Jumping Knowledge Networks. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm"a ssan, Stockholm, Sweden, July 10--15, 2018 (Proceedings of Machine Learning Research, Vol. 80). PMLR, 5449--5458.

[32]

I-Cheng Yeh and Che-hui Lien. 2009. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Syst. Appl., Vol. 36, 2 (2009), 2473--2480.

Digital Library

[33]

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi. 2017. Fairness Constraints: Mechanisms for Fair Classification. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20--22 April 2017, Fort Lauderdale, FL, USA (Proceedings of Machine Learning Research, Vol. 54). PMLR, 962--970.

Cited By

Chen ARossi RPark NTrivedi PWang YYu TKim SDernoncourt FAhmed N(2024)Fairness-Aware Graph Neural Networks: A SurveyACM Transactions on Knowledge Discovery from Data10.1145/364914218:6(1-23)Online publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1145/3649142
Li YYang YCao JLiu STang HXu GBaeza-Yates RBonchi F(2024)Toward Structure Fairness in Dynamic Graph Embedding: A Trend-aware Dual Debiasing ApproachProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671848(1701-1712)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671848
Li ZDong YLiu QYu JBaeza-Yates RBonchi F(2024)Rethinking Fair Graph Neural Networks from Re-balancingProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671826(1736-1745)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671826
Show More Cited By

Index Terms

GUIDE: Group Equality Informed Individual Fairness in Graph Neural Networks
1. Applied computing
  1. Law, social and behavioral sciences
2. Computing methodologies
  1. Machine learning

Recommendations

Individual Fairness for Graph Neural Networks: A Ranking based Approach
KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining

Recent years have witnessed the pivotal role of Graph Neural Networks (GNNs) in various high-stake decision-making scenarios due to their superior learning capability. Close on the heels of the successful adoption of GNNs in different application ...
Gerrymandering individual fairness
Abstract
Individual fairness requires that similar individuals are treated similarly. It is supposed to prevent the unfair treatment of individuals on the subgroup level and to overcome the problem that group fairness measures are susceptible to ...
On the apparent conflict between individual and group fairness
FAT* '20: Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency

A distinction has been drawn in fair machine learning research between 'group' and 'individual' fairness measures. Many technical research papers assume that both are important, but conflicting, and propose ways to minimise the trade-offs between these ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 2022

5033 pages

ISBN:9781450393850

DOI:10.1145/3534678

General Chairs:
Aidong Zhang
University of Virginia
,
Huzefa Rangwala
Amazon/George Mason University

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 August 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Cisco Faculty Research Award

Conference

KDD '22

Sponsor:

KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 14 - 18, 2022

Washington DC, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
1,503
Total Downloads

Downloads (Last 12 months)594
Downloads (Last 6 weeks)82

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen ARossi RPark NTrivedi PWang YYu TKim SDernoncourt FAhmed N(2024)Fairness-Aware Graph Neural Networks: A SurveyACM Transactions on Knowledge Discovery from Data10.1145/364914218:6(1-23)Online publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1145/3649142
Li YYang YCao JLiu STang HXu GBaeza-Yates RBonchi F(2024)Toward Structure Fairness in Dynamic Graph Embedding: A Trend-aware Dual Debiasing ApproachProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671848(1701-1712)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671848
Li ZDong YLiu QYu JBaeza-Yates RBonchi F(2024)Rethinking Fair Graph Neural Networks from Re-balancingProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671826(1736-1745)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671826
He XKang JQiu RWang FSepulveda JTong HSerra ESpezzano F(2024)On the Sensitivity of Individual Fairness: Measures and Robust AlgorithmsProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679721(829-838)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679721
Dong YLei ZZheng ZWang SMa JHuang AChen CLi JChua TNgo CKumar RLauw HKa-Wei Lee R(2024)PyGDebias: A Python Library for Debiasing in Graph LearningCompanion Proceedings of the ACM Web Conference 202410.1145/3589335.3651239(1019-1022)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589335.3651239
He HZhang QWang SYi KNiu ZCao L(2024)Learning Informative Representation for Fairness-Aware Multivariate Time-Series Forecasting: A Group-Based PerspectiveIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.332395636:6(2504-2516)Online publication date: Jun-2024
https://doi.org/10.1109/TKDE.2023.3323956
Zhang HWu BYuan XPan STong HPei J(2024)Trustworthy Graph Neural Networks: Aspects, Methods, and TrendsProceedings of the IEEE10.1109/JPROC.2024.3369017112:2(97-139)Online publication date: Feb-2024
https://doi.org/10.1109/JPROC.2024.3369017
Wang ZDzuong JYuan XChen ZWu YYao XZhang W(2024)Individual Fairness with Group Awareness Under UncertaintyMachine Learning and Knowledge Discovery in Databases. Research Track10.1007/978-3-031-70362-1_6(89-106)Online publication date: 22-Aug-2024
https://doi.org/10.1007/978-3-031-70362-1_6
Feng QJiang ZLi RWang YZou NBian JHu XOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Fair graph distillationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669657(80644-80660)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669657
Merchant ACastillo CFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)Disparity, Inequality, and Accuracy Tradeoffs in Graph Neural Networks for Node ClassificationProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3614847(1818-1827)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1145/3583780.3614847
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents