BishtRef
Articles Journals Publishers Authors Subjects Most Cited New Papers Year Stats Open Access
journal article Open Access Mar 10, 2025

GFairHint: Improving Individual Fairness for Graph Neural Networks via Fairness Hint

Paiheng Xu ORCID Bang An ORCID Wei Ai ORCID Furong Huang ORCID
ACM Transactions on Knowledge Discovery from Data Vol. 19 No. 3 pp. 1-22 · Association for Computing Machinery (ACM)
View at Publisher Save 10.1145/3714472
Abstract
Given the growing concerns about fairness in machine learning and the impressive performance of Graph Neural Networks (GNNs) on graph data learning, algorithmic fairness in GNNs has attracted significant attention. While many existing studies improve fairness at the group level, only a few works promote individual fairness, which renders similar outcomes for similar individuals. A desirable framework that promotes individual fairness should (1) balance fairness and performance, (2) accommodate two commonly-used individual similarity measures (externally annotated and computed from input features), and, (3) generalize across various GNNs. Unfortunately, none of the prior work achieves all the desirables. In this work, we propose a novel method,
GFairHint
, which promotes individual fairness in GNNs and achieves all aforementioned desirables. GFairHint learns fairness representations through an auxiliary link prediction task, which is inspired by a theoretical analysis of the definition of individual fairness. We then concatenate the representations with the learned node embeddings in original GNNs as a
“fairness hint”
. Through extensive experimental investigations on five real-world graph datasets under three prevalent GNNs covering both individual similarity measures above, GFairHint achieves the best fairness results in almost all combinations of datasets with various backbone models, while generating comparable utility results, with much less computational cost compared to the previous state-of-the-art method.
Topics

No keywords indexed for this article. Browse by subject →

References
52
[1]
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. 2021. Towards a unified framework for fair and stable graph representation learning. In Proceedings of the Uncertainty in Artificial Intelligence. PMLR, 2114–2124. 10.1007/978-3-030-72357-6
[2]
Derrick Blakely Jack Lanchantin and Yanjun Qi. 2021. Time and Space Complexity of Graph Convolutional Networks. Accessed on: Dec 31 (2021).
[3]
Avishek Bose and William Hamilton. 2019. Compositional fairness constraints for graph embeddings. In Proceedings of the International Conference on Machine Learning. PMLR, 715–724.
[4]
Maarten Buyl and Tijl De Bie. 2020. DeBayes: A Bayesian method for debiasing network embeddings. In Proceedings of the 37th International Conference on Machine Learning, Vol. 119. Hal Daumé III and Aarti Singh (Eds.), PMLR, 1220–1229. https://proceedings.mlr.press/v119/buyl20a.html
[7]
Andac Demir, Toshiaki Koike-Akino, Ye Wang, Masaki Haruna, and Deniz Erdogmus. 2021. EEG-GNN: Graph neural networks for classification of electroencephalogram (EEG) signals. In Proceedings of the 43rd Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC ‘21). IEEE, 1061–1067.
[8]
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1: Long and Short Papers. DOI: 10.18653/v1/N19-1423
[14]
Matthias Fey and Jan E. Lenssen. 2019. Fast graph representation learning with PyTorch geometric. In Proceedings of the ICLR Workshop on Representation Learning on Graphs and Manifolds.
[16]
Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 30.
[18]
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems 33 (2020), 22118–22133.
[19]
Cumulated gain-based evaluation of IR techniques

Kalervo Järvelin, Jaana Kekäläinen

ACM Transactions on Information Systems 10.1145/582415.582418
[21]
Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv:1412.6980. Retrieved from 10.48550/arXiv.1412.6980
[22]
Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv:1609.02907. Retrieved from 10.48550/arXiv.1412.6980 10.48550/arxiv.1412.6980
[23]
O Deniz Kose and Yanning Shen. 2022. Fair node representation learning via adaptive data augmentation. arXiv:2201.08549. Retrieved from 10.48550/arXiv.2201.08549 10.48550/arxiv.2201.08549
[24]
Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. 2017. Counterfactual fairness. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 30.
[25]
Preethi Lahoti, Krishna P Gummadi, and Gerhard Weikum. 2019. Operationalizing individual fairness with pairwise fair representations. Proceedings of the VLDB Endowment 13, 4 (2019), 506–518.
[26]
Algorithmic Bias? An Empirical Study of Apparent Gender-Based Discrimination in the Display of STEM Career Ads

Anja Lambrecht, Catherine Tucker

Management Science 10.1287/mnsc.2018.3093
[27]
Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. 2021. On dyadic fairness: Exploring and mitigating bias in graph connections. In Proceedings of the International Conference on Learning Representations.
[28]
Zhao Li, Xin Shen, Yuhang Jiao, Xuming Pan, Pengcheng Zou, Xianling Meng, Chengwei Yao, and Jiajun Bu. 2020. Hierarchical bipartite graph neural networks: Towards large-scale e-commerce applications. In Proceedings of the IEEE 36th International Conference on Data Engineering (ICDE ‘20). IEEE, 1677–1688.
[31]
A Survey on Bias and Fairness in Machine Learning

Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena et al.

ACM Computing Surveys 10.1145/3457607
[32]
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 26.
[33]
Debarghya Mukherjee, Mikhail Yurochkin, Moulinath Banerjee, and Yuekai Sun. 2020. Two simple ways to learn individual fairness metrics from data. In Proceedings of the 37th International Conference on Machine Learning (ICML’20). JMLR.org, Article 658, 11 pages.
[34]
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017. Automatic differentiation in pytorch. In Proceedings of the NIPS 2017 Workshop on Autodiff, Long Beach, California, USA. Retrieved from https://openreview.net/forum?id=BJJsrmfCZ
[35]
Felix Petersen, Debarghya Mukherjee, Yuekai Sun, and Mikhail Yurochkin. 2021. Post-processing for individual fairness. In Proceedings of the Advances in Neural Information Processing Systems. M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 25944–25955. Retrieved from https://proceedings.neurips.cc/paper/2021/file/d9fea4ca7e4a74c318ec27c1deb0796c-Paper.pdf
[36]
Evaggelia Pitoura, Kostas Stefanidis, and Georgia Koutrika. 2022. Fairness in rankings and recommendations: An overview. The VLDB Journal 31, 3 (2022), 431–458. 10.1007/s00778-021-00697-y
[38]
Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. 2019. Fairwalk: Towards fair graph embedding. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI’19). AAAI Press, 3289–3295.
[39]
Michael Redmond. 2009. Communities and Crime. UCI Machine Learning Repository.
[40]
Oleksandr Shchur Maximilian Mumme Aleksandar Bojchevski and Stephan Günnemann. 2018. Pitfalls of graph neural network evaluation. arXiv:1811.05868. Retrieved from 10.48550/arXiv.1811.05868
[41]
Karen Simonyan Andrea Vedaldi and Andrew Zisserman. 2013. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv:1312.6034. Retrieved from 10.48550/arXiv.1312.6034 10.48550/arxiv.1312.6034
[44]
Petar Veličković Guillem Cucurull Arantxa Casanova Adriana Romero Pietro Lio and Yoshua Bengio. 2017. Graph attention networks. arXiv:1710.10903. Retrieved from 10.48550/arXiv.1710.10903 10.48550/arxiv.1710.10903
[49]
Graph Neural Networks in Recommender Systems: A Survey

Shiwen Wu, Fei Sun, Wentao Zhang et al.

ACM Computing Surveys 10.1145/3535101
[50]
A Comprehensive Survey on Graph Neural Networks

Zonghan Wu, Shirui Pan, Fengwen Chen et al.

IEEE Transactions on Neural Networks and Learning... 10.1109/tnnls.2020.2978386

Showing 50 of 52 references

Metrics
4
Citations
52
References
Details
Published
Mar 10, 2025
Vol/Issue
19(3)
Pages
1-22
License
View
Authors
P
Paiheng Xu

University of Maryland at College Park, College Park, Maryland, USA

B
Bang An

University of Maryland at College Park, College Park, Maryland, USA

W
Wei Ai

University of Maryland at College Park, College Park, Maryland, USA

F
Furong Huang

University of Maryland at College Park, College Park, Maryland, USA

Cite This Article
Paiheng Xu, Bang An, Wei Ai, et al. (2025). GFairHint: Improving Individual Fairness for Graph Neural Networks via Fairness Hint. ACM Transactions on Knowledge Discovery from Data, 19(3), 1-22. https://doi.org/10.1145/3714472
Related

You May Also Like

Graph evolution

Jure Leskovec, Jon Kleinberg · 2007

2,024 citations

Isolation-Based Anomaly Detection

Fei Tony Liu, Kai Ming Ting · 2012

1,600 citations

Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection

Ricardo J. G. B. Campello, Davoud Moulavi · 2015

673 citations

A Survey on Causal Inference

Liuyi Yao, Zhixuan Chu · 2021

376 citations

Temporal Link Prediction Using Matrix and Tensor Factorizations

Daniel M. Dunlavy, Tamara G. Kolda · 2011

351 citations