FAROS: Fair Graph Generation via Attribute Switching Mechanisms
Authors: name: Abdennacer Badaoui; name: Oussama Kharouiche; name: Hatim Mrabet; name: Daniele Malitesta; name: Fragkiskos D. Malliaros
Published: 2025-07-04 17:31:41

Abstract: Recent advancements in graph diffusion models (GDMs) have enabled the
synthesis of realistic network structures, yet ensuring fairness in the
generated data remains a critical challenge. Existing solutions attempt to
mitigate bias by re-training the GDMs with ad-hoc fairness constraints.
Conversely, with this work, we propose FAROS, a novel FAir graph geneRatiOn
framework leveraging attribute Switching mechanisms and directly running in the
generation process of the pre-trained GDM. Technically, our approach works by
altering nodes' sensitive attributes during the generation. To this end, FAROS
calculates the optimal fraction of switching nodes, and selects the diffusion
step to perform the switch by setting tailored multi-criteria constraints to
preserve the node-topology profile from the original distribution (a proxy for
accuracy) while ensuring the edge independence on the sensitive attributes for
the generated graph (a proxy for fairness). Our experiments on benchmark
datasets for link prediction demonstrate that the proposed approach effectively
reduces fairness discrepancies while maintaining comparable (or even higher)
accuracy performance to other similar baselines. Noteworthy, FAROS is also able
to strike a better accuracy-fairness trade-off than other competitors in some
of the tested settings under the Pareto optimality concept, demonstrating the
effectiveness of the imposed multi-criteria constraints.