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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Discrimination-Free Condensation for Large-Scale Graphs

  • Runze Mao,
  • Xiao Chen,
  • Chun Hin Chan,
  • Xiangmeng Wang,
  • Wenqi Fan,
  • Qing Li

摘要

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.