research-article

Open access

Learning Fair Node Representations with Graph Counterfactual Fairness

Authors:

Aidong Zhang, and

Jundong LiAuthors Info & Claims

WSDM '22: Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining

February 2022

Pages 695 - 703

https://doi.org/10.1145/3488560.3498391

Published: 15 February 2022 Publication History

Abstract

Fair machine learning aims to mitigate the biases of model predictions against certain subpopulations regarding sensitive attributes such as race and gender. Among the many existing fairness notions, counterfactual fairness measures the model fairness from a causal perspective by comparing the predictions of each individual from the original data and the counterfactuals. In counterfactuals, the sensitive attribute values of this individual had been modified. Recently, a few works extend counterfactual fairness to graph data, but most of them neglect the following facts that can lead to biases: 1) the sensitive attributes of each node's neighbors may causally affect the prediction w.r.t. this node; 2) the sensitive attributes may causally affect other features and the graph structure. To tackle these issues, in this paper, we propose a novel fairness notion - graph counterfactual fairness, which considers the biases led by the above facts. To learn node representations towards graph counterfactual fairness, we propose a novel framework based on counterfactual data augmentation. In this framework, we generate counterfactuals corresponding to perturbations on each node's and their neighbors' sensitive attributes. Then we enforce fairness by minimizing the discrepancy between the representations learned from the original graph and the counterfactuals for each node. Experiments on both synthetic and real-world graphs show that our framework outperforms the state-of-the-art baselines in graph counterfactual fairness, and also achieves comparable prediction performance.

Supplementary Material

MP4 File (WSDM22-fp161.mp4)

The presentation video for WSDM'22 paper "Learning Fair Node Representations with Graph Counterfactual Fairness"

Download
150.70 MB

References

[1]

Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. 2021 a. Towards a Unified Framework for Fair and Stable Graph Representation Learning. UAI (2021).

[2]

Chirag Agarwal, Marinka Zitnik, and Himabindu Lakkaraju. 2021 b. Towards a Rigorous Theoretical Analysis and Evaluation of GNN Explanations. arXiv preprint arXiv:2106.09078 (2021).

[3]

Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H Chi. 2017. Data decisions and theoretical implications when adversarially learning fair representations. arXiv preprint arXiv:1707.00075 (2017).

[4]

Smriti Bhagat, Graham Cormode, and S Muthukrishnan. 2011. Node classification in social networks. In Social network data analytics . 115--148.

[5]

Reuben Binns. 2020. On the apparent conflict between individual and group fairness. In FAT .

[6]

Avishek Bose and William Hamilton. 2019. Compositional fairness constraints for graph embeddings. In ICML .

[7]

Jane Bromley, James W Bentz, Léon Bottou, Isabelle Guyon, Yann LeCun, Cliff Moore, Eduard S"ackinger, and Roopak Shah. 1993. Signature verification using a "siamese" time delay neural network. IJPRAI (1993).

[8]

Maarten Buyl and Tijl De Bie. 2020. Debayes: a bayesian method for debiasing network embeddings. In ICML .

[9]

Silvia Chiappa. 2019. Path-specific counterfactual fairness. In AAAI .

[10]

Alexandra Chouldechova. 2017. Fair prediction with disparate impact: a study of bias in recidivism prediction instruments. Big data (2017).

[11]

Maxwell Crouse, Ibrahim Abdelaziz, Cristina Cornelio, Veronika Thost, Lingfei Wu, Kenneth Forbus, and Achille Fokoue. 2019. Improving graph neural network representations of logical formulae with subgraph pooling. arXiv preprint arXiv:1911.06904 (2019).

[12]

Enyan Dai and Suhang Wang. 2020. FairGNN: Eliminating the Discrimination in Graph Neural Networks with Limited Sensitive Attribute Information. arXiv preprint arXiv:2009.01454 (2020).

[13]

William Dieterich, Christina Mendoza, and Tim Brennan. 2016. COMPAS risk scales: demonstrating accuracy equity and predictive parity. Northpoint Inc (2016).

[14]

Yushun Dong, Jian Kang, Hanghang Tong, and Jundong Li. 2021. Individual Fairness for Graph Neural Networks: A Ranking based Approach. In KDD .

[15]

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012. Fairness through awareness. In ITCS .

[16]

Matthias Fey and Jan Eric Lenssen. 2019. Fast graph representation learning with PyTorch Geometric. ICLR Workshop on Representation Learning on Graphs and Manifolds (2019).

[17]

William L Hamilton. 2020. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning (2020).

[18]

William L Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NIPS .

[19]

Moritz Hardt, Eric Price, and Nati Srebro. 2016. Equality of opportunity in supervised learning. In NIPS .

[20]

Glen Jeh and Jennifer Widom. 2003. Scaling personalized web search. In IW3C2 .

[21]

Yizhu Jiao, Yun Xiong, Jiawei Zhang, Yao Zhang, Tianqi Zhang, and Yangyong Zhu. 2020. Sub-graph contrast for scalable self-supervised graph representation learning. In IEEE ICDM .

[22]

Jian Kang, Jingrui He, Ross Maciejewski, and Hanghang Tong. 2020. Inform: Individual fairness on graph mining. In ACM SIGKDD .

[23]

Thomas N Kipf and Max Welling. 2016. Variational graph auto-encoders. NIPS Workshop on Bayesian Deep Learning (2016).

[24]

Thomas N Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. ICLR (2017).

[25]

Matt J Kusner, Joshua R Loftus, Chris Russell, and Ricardo Silva. 2017. Counterfactual fairness. NIPS (2017).

[26]

Marta Z Kwiatkowska. 1989. Survey of fairness notions. Information and Software Technology (1989).

[27]

Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. 2020. On dyadic fairness: Exploring and mitigating bias in graph connections. In ICLR .

[28]

David Liben-Nowell and Jon Kleinberg. 2007. The link-prediction problem for social networks. JASIST (2007).

[29]

Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. 2021. A survey on bias and fairness in machine learning. ACM CSUR (2021).

[30]

Dang Nguyen, Wei Luo, Tu Dinh Nguyen, Svetha Venkatesh, and Dinh Phung. 2018. Learning graph representation via frequent subgraphs. In SIAM .

[31]

Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. Pytorch: An imperative style, high-performance deep learning library. NIPS (2019).

[32]

Judea Pearl et al. 2009. Causal inference in statistics: an overview. Statistics surveys (2009).

[33]

Chris Russell, M Kusner, C Loftus, and Ricardo Silva. 2017. When worlds collide: integrating different counterfactual assumptions in fairness. In NIPS .

[34]

Harjit Singh Sekhon, Sanjit Kumar Roy, and James Devlin. 2016. Perceptions of fairness in financial services: an analysis of distribution channels. International Journal of Bank Marketing (2016).

[35]

Saeed Sharifi-Malvajerdi, Michael Kearns, and Aaron Roth. 2019. Average individual fairness: Algorithms, generalization and experiments. NIPS (2019).

[36]

Yuhang Song, Wenbo Li, Lei Zhang, Jianwei Yang, Emre Kiciman, Hamid Palangi, Jianfeng Gao, C-C Jay Kuo, and Pengchuan Zhang. 2020. Novel human-object interaction detection via adversarial domain generalization. arXiv preprint arXiv:2005.11406 (2020).

[37]

Petar Velivc ković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2018. Graph attention networks. ICLR (2018).

[38]

Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. 2019. Deep Graph Infomax. ICLR (Poster) (2019).

[39]

Sahil Verma and Julia Rubin. 2018. Fairness definitions explained. In FairWare. 1--7.

[40]

Daixin Wang, Peng Cui, and Wenwu Zhu. 2016. Structural deep network embedding. In ACM SIGKDD .

[41]

Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. 2018. Graphgan: Graph representation learning with generative adversarial nets. In AAAI .

[42]

Yongkai Wu, Lu Zhang, and Xintao Wu. 2019. Counterfactual fairness: Unidentification, bound and algorithm. In IJCAI .

[43]

Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020. A comprehensive survey on graph neural networks. IEEE TNNLS (2020).

[44]

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018a. How Powerful are Graph Neural Networks?. In ICLR .

[45]

Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018b. Representation learning on graphs with jumping knowledge networks. In ICML .

[46]

Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. 2018. Hierarchical graph representation learning with differentiable pooling. In NIPS .

[47]

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. 2017. Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In WWW .

[48]

Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. 2013. Learning fair representations. In ICML .

[49]

Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. 2018. Mitigating unwanted biases with adversarial learning. In AIES .

[50]

Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. 2020. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140 (2020).

Cited By

Medda GFabbri FMarras MBoratto LFenu G(2024)GNNUERS: Fairness Explanation in GNNs for Recommendation via Counterfactual ReasoningACM Transactions on Intelligent Systems and Technology10.1145/3655631Online publication date: 3-Apr-2024
https://dl.acm.org/doi/10.1145/3655631
Choe MYoo JLee GBaek WKang UShin K(2024)Representative and Back-In-Time Sampling from Real-world HypergraphsACM Transactions on Knowledge Discovery from Data10.1145/365330618:6(1-48)Online publication date: 26-Apr-2024
https://dl.acm.org/doi/10.1145/3653306
Lalor JAbbasi AOketch KYang YForsgren N(2024)Should Fairness be a Metric or a Model? A Model-based Framework for Assessing Bias in Machine Learning PipelinesACM Transactions on Information Systems10.1145/364127642:4(1-41)Online publication date: 22-Mar-2024
https://dl.acm.org/doi/10.1145/3641276
Show More Cited By

Index Terms

Learning Fair Node Representations with Graph Counterfactual Fairness
1. Applied computing
  1. Law, social and behavioral sciences
2. Computing methodologies
  1. Machine learning

Recommendations

Counterfactual Fairness in Text Classification through Robustness
AIES '19: Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society

In this paper, we study counterfactual fairness in text classification, which asks the question: How would the prediction change if the sensitive attribute referenced in the example were different? Toxicity classifiers demonstrate a counterfactual ...
Read More
Learning for Counterfactual Fairness from Observational Data
KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Fairness-aware machine learning has attracted a surge of attention in many domains, such as online advertising, personalized recommendation, and social media analysis in web applications. Fairness-aware machine learning aims to eliminate biases of ...
Read More
Counterfactual Explanation for Fairness in Recommendation
Fairness-aware recommendation alleviates discrimination issues to build trustworthy recommendation systems. Explaining the causes of unfair recommendations is critical, as it promotes fairness diagnostics, and thus secures users’ trust in recommendation ...
Read More

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WSDM '22: Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining

February 2022

1690 pages

ISBN:9781450391320

DOI:10.1145/3488560

General Chairs:
K. Selcuk Candan
Arizona State University, USA
,
Huan Liu
Arizona State University, USA
,
Program Chairs:
Leman Akoglu
Carnegie Mellon University, USA
,
Xin Luna Dong
Meta Platforms, Inc. (former Facebook), USA
,
Jiliang Tang
Michigan State University, USA

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: 15 February 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

JP Morgan Chase Faculty Research Award
Cisco Faculty Research Award
National Science Foundation (NSF)

Conference

WSDM '22

Sponsor:

WSDM '22: The Fifteenth ACM International Conference on Web Search and Data Mining

February 21 - 25, 2022

AZ, Virtual Event, USA

Acceptance Rates

Overall Acceptance Rate 498 of 2,863 submissions, 17%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
1,608
Total Downloads

Downloads (Last 12 months)729
Downloads (Last 6 weeks)56

Other Metrics

View Author Metrics

Citations

Cited By

Medda GFabbri FMarras MBoratto LFenu G(2024)GNNUERS: Fairness Explanation in GNNs for Recommendation via Counterfactual ReasoningACM Transactions on Intelligent Systems and Technology10.1145/3655631Online publication date: 3-Apr-2024
https://dl.acm.org/doi/10.1145/3655631
Choe MYoo JLee GBaek WKang UShin K(2024)Representative and Back-In-Time Sampling from Real-world HypergraphsACM Transactions on Knowledge Discovery from Data10.1145/365330618:6(1-48)Online publication date: 26-Apr-2024
https://dl.acm.org/doi/10.1145/3653306
Lalor JAbbasi AOketch KYang YForsgren N(2024)Should Fairness be a Metric or a Model? A Model-based Framework for Assessing Bias in Machine Learning PipelinesACM Transactions on Information Systems10.1145/364127642:4(1-41)Online publication date: 22-Mar-2024
https://dl.acm.org/doi/10.1145/3641276
Chen WWu YZhang ZZhuang FHe ZXie RXia F(2024)FairGap: Fairness-Aware Recommendation via Generating Counterfactual GraphACM Transactions on Information Systems10.1145/363835242:4(1-25)Online publication date: 9-Feb-2024
https://dl.acm.org/doi/10.1145/3638352
Zhu YLi JChen LZheng ZAngélica LLattanzi SMuñoz Medina AAkoglu LGionis AVassilvitskii S(2024)The Devil is in the Data: Learning Fair Graph Neural Networks via Partial Knowledge DistillationProceedings of the 17th ACM International Conference on Web Search and Data Mining10.1145/3616855.3635768(1012-1021)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1145/3616855.3635768
Dong YLei ZZheng ZWang SMa JHuang AChen CLi JChua TNgo CKa-Wei Lee RKumar RLauw H(2024)PyGDebias: A Python Library for Debiasing in Graph LearningCompanion Proceedings of the ACM on Web Conference 202410.1145/3589335.3651239(1019-1022)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589335.3651239
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
Fragkathoulas CPapanikou VKaridi DPitoura E(2024)On Explaining Unfairness: An Overview2024 IEEE 40th International Conference on Data Engineering Workshops (ICDEW)10.1109/ICDEW61823.2024.00035(226-236)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDEW61823.2024.00035
Hu YLiao TChen JBian JZheng ZChen C(2024)Migrate demographic group for fair Graph Neural NetworksNeural Networks10.1016/j.neunet.2024.106264175(106264)Online publication date: Jul-2024
https://doi.org/10.1016/j.neunet.2024.106264
Wang YZhang RYang QZhou QZhang SFan YHuang LLi KZhou F(2024)FairCareInformation Processing and Management: an International Journal10.1016/j.ipm.2024.10368261:3Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1016/j.ipm.2024.103682
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