Balancing Fairness and Accuracy in Graph Learning via Fairness-Constrained Rewiring

Jason Wang, Lukas Fesser, Melanie Weber
Proceedings of the 4th (2025) and 3rd (2024) NeurIPS Workshops on Symmetry and Geometry in Neural Representations, PMLR 282:716-735, 2026.

Abstract

Algorithmic fairness aims to ensure the safe and responsible use of machine learning tools in applications across domains. In graph learning, several “fair rewiring” approaches have been proposed that perturb edges in the input graph to mitigate feature and relational bias. However, these approaches can lead to a decrease in accuracy in downstream tasks. On the other hand, classical rewiring approaches improve accuracy by mitigating over-smoothing and over-squashing effects induced by the graph’s topology. In this work we show that those classical rewiring approaches reinforce existing topological biases and boost accuracy at the cost of fairness. We propose a novel fairness metric (topological bias) that allows for evaluating relational bias separately from feature bias. We then propose a fairness constraint that can be incorporated into classical rewiring techniques to mitigate topological bias. We show that the resulting fairness-constrained rewiring balances fairness and accuracy effectively in graph learning tasks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v282-wang26d, title = {Balancing Fairness and Accuracy in Graph Learning via Fairness-Constrained Rewiring}, author = {Wang, Jason and Fesser, Lukas and Weber, Melanie}, booktitle = {Proceedings of the 4th (2025) and 3rd (2024) NeurIPS Workshops on Symmetry and Geometry in Neural Representations}, pages = {716--735}, year = {2026}, editor = {Acosta, Francisco and Azeglio, Simone and Tolooshams, Bahareh and van de Geijn, Chase and Shewmake, Christian and Sanborn, Sophia and Miolane, Nina}, volume = {282}, series = {Proceedings of Machine Learning Research}, month = {14 Dec 2024--07 Dec 2025}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v282/main/assets/wang26d/wang26d.pdf}, url = {https://proceedings.mlr.press/v282/wang26d.html}, abstract = {Algorithmic fairness aims to ensure the safe and responsible use of machine learning tools in applications across domains. In graph learning, several “fair rewiring” approaches have been proposed that perturb edges in the input graph to mitigate feature and relational bias. However, these approaches can lead to a decrease in accuracy in downstream tasks. On the other hand, classical rewiring approaches improve accuracy by mitigating over-smoothing and over-squashing effects induced by the graph’s topology. In this work we show that those classical rewiring approaches reinforce existing topological biases and boost accuracy at the cost of fairness. We propose a novel fairness metric (topological bias) that allows for evaluating relational bias separately from feature bias. We then propose a fairness constraint that can be incorporated into classical rewiring techniques to mitigate topological bias. We show that the resulting fairness-constrained rewiring balances fairness and accuracy effectively in graph learning tasks.} }
Endnote
%0 Conference Paper %T Balancing Fairness and Accuracy in Graph Learning via Fairness-Constrained Rewiring %A Jason Wang %A Lukas Fesser %A Melanie Weber %B Proceedings of the 4th (2025) and 3rd (2024) NeurIPS Workshops on Symmetry and Geometry in Neural Representations %C Proceedings of Machine Learning Research %D 2026 %E Francisco Acosta %E Simone Azeglio %E Bahareh Tolooshams %E Chase van de Geijn %E Christian Shewmake %E Sophia Sanborn %E Nina Miolane %F pmlr-v282-wang26d %I PMLR %P 716--735 %U https://proceedings.mlr.press/v282/wang26d.html %V 282 %X Algorithmic fairness aims to ensure the safe and responsible use of machine learning tools in applications across domains. In graph learning, several “fair rewiring” approaches have been proposed that perturb edges in the input graph to mitigate feature and relational bias. However, these approaches can lead to a decrease in accuracy in downstream tasks. On the other hand, classical rewiring approaches improve accuracy by mitigating over-smoothing and over-squashing effects induced by the graph’s topology. In this work we show that those classical rewiring approaches reinforce existing topological biases and boost accuracy at the cost of fairness. We propose a novel fairness metric (topological bias) that allows for evaluating relational bias separately from feature bias. We then propose a fairness constraint that can be incorporated into classical rewiring techniques to mitigate topological bias. We show that the resulting fairness-constrained rewiring balances fairness and accuracy effectively in graph learning tasks.
APA
Wang, J., Fesser, L. & Weber, M.. (2026). Balancing Fairness and Accuracy in Graph Learning via Fairness-Constrained Rewiring. Proceedings of the 4th (2025) and 3rd (2024) NeurIPS Workshops on Symmetry and Geometry in Neural Representations, in Proceedings of Machine Learning Research 282:716-735 Available from https://proceedings.mlr.press/v282/wang26d.html.

Related Material