Discrimination-Free Condensation for Large-Scale Graphs
摘要
Graph condensation has become a prominent method for reducing the size of large-scale graphs into manageable, synthetic forms, significantly decreasing the resources needed for training graph neural networks (GNNs). While these condensed graphs allow GNNs to achieve performances comparable to those trained on original, larger graphs, the potential bias and resulting unfairness in such condensed representations have not been adequately addressed. Our research indicates that subgroup unfairness—across both binary and multi-attribute groups—intensifies significantly with existing condensation techniques, leading to ethical and societal concerns when such models are deployed in real-world settings. Considering the condensed graphs have lost original subgroup information, it is prohibitive to directly train fair GNNs on them using existing algorithms. In this paper, we introduce a novel approach, Graph Condensation through Optimal Transport (GCOT), designed to ensure subgroup fairness in the graph condensation process. GCOT utilizes multi-marginal optimal transport to equalize the hidden representation distributions among different subgroups effectively, theoretically reducing unfairness in GNNs trained on condensed graphs. This method addresses both degree and attribute biases and is versatile enough to accommodate multi-group scenarios. Our extensive experiments on four real-world datasets demonstrate that GCOT not only promotes fairness but also maintains high accuracy, paving the way for more equitable GNN applications.