Fair graph distillation
AUTHORs: 
Qizhang Feng, Zhimeng Jiang, Ruiquan Li, Yicheng Wang, Na Zou, Jiang Bian, Xia HuAuthors Info & Claims
Article No.: 3535, Pages 80644 - 80660
Abstract
As graph neural networks (GNNs) struggle with large-scale graphs due to high computational demands, graph data distillation promises to alleviate this issue by distilling a large real graph into a smaller distilled graph while maintaining comparable prediction performance for GNNs trained on both graphs. However, we observe that GNNs trained on distilled graphs may exhibit more severe group fairness issues than GNNs trained on real graphs for vanilla and fair GNNs training. Motivated by these observations, we propose fair graph distillation (FGD), an advanced graph distillation approach to generate fair distilled graphs. The challenge lies in the deficiency of sensitive attributes for nodes in the distilled graph, making most debiasing methods (e.g., regularization and adversarial debiasing) intractable for distilled graphs. We develop a simple yet effective bias metric, named coherence, for distilled graphs. Based on the proposed coherence metric, we introduce a framework for fair graph distillation using a bi-level optimization algorithm. Extensive experiments demonstrate that the proposed algorithm can achieve better prediction performance-fairness trade-offs across various datasets and GNN architectures.
References
[1]
C. Agarwal, H. Lakkaraju, and M. Zitnik. Towards a unified framework for fair and stable graph representation learning. In Uncertainty in Artificial Intelligence, pages 2114-2124. PMLR, 2021.
[2]
A. Beutel, J. Chen, Z. Zhao, and E. H. Chi. Data decisions and theoretical implications when adversarially learning fair representations. arXiv preprint arXiv:1707.00075, 2017.
[3]
A. Bose and W. Hamilton. Compositional fairness constraints for graph embeddings. In International Conference on Machine Learning, pages 715-724. PMLR, 2019.
[4]
C.-Y. Chuang and Y. Mroueh. Fair mixup: Fairness via interpolation. In International Conference on Learning Representations, 2020.
[5]
E. Dai and S. Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 680-688, 2021.
[6]
Y. Dong, J. Kang, H. Tong, and J. Li. Individual fairness for graph neural networks: A ranking based approach. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 300-310, 2021.
[7]
Y. Dong, N. Liu, B. Jalaian, and J. Li. Edits: Modeling and mitigating data bias for graph neural networks. In Proceedings of the ACM Web Conference 2022, pages 1259-1269, 2022.
[8]
Y. Dong, B. Zhang, Y. Yuan, N. Zou, Q. Wang, and J. Li. Reliant: Fair knowledge distillation for graph neural networks. In Proceedings of the 2023 SIAM International Conference on Data Mining (SDM), pages 154-162. SIAM, 2023.
[9]
M. Du, S. Mukherjee, G. Wang, R. Tang, A. H. Awadallah, and X. Hu. Fairness via representation neutralization. arXiv preprint arXiv:2106.12674, 2021.
[10]
J. Fisher, A. Mittal, D. Palfrey, and C. Christodoulopoulos. Debiasing knowledge graph embeddings. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7332-7345, 2020.
[11]
J. Gou, B. Yu, S. J. Maybank, and D. Tao. Knowledge distillation: A survey. International Journal of Computer Vision, 129:1789-1819, 2021.
[12]
W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[13]
X. Han, Z. Jiang, N. Liu, and X. Hu. G-mixup: Graph data augmentation for graph classification. arXiv preprint arXiv:2202.07179, 2022a.
[14]
X. Han, Z. Jiang, N. Liu, Q. Song, J. Li, and X. Hu. Geometric graph representation learning via maximizing rate reduction. In Proceedings of the ACM Web Conference 2022, pages 1226-1237, 2022b.
[15]
X. Han, Z. Jiang, H. Jin, Z. Liu, N. Zou, Q. Wang, and X. Hu. Retiring $\delta \text{DP}$: New distribution-level metrics for demographic parity. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL https://openreview.net/forum?id=LjDFIWWVVa.
[16]
A. Ishizaka and P. Nemery. Multi-criteria decision analysis: methods and software. John Wiley & Sons, 2013.
[17]
Z. Jiang, X. Han, C. Fan, Z. Liu, N. Zou, A. Mostafavi, and X. Hu. Fmp: Toward fair graph message passing against topology bias. arXiv preprint arXiv:2202.04187, 2022a.
[18]
Z. Jiang, X. Han, C. Fan, F. Yang, A. Mostafavi, and X. Hu. Generalized demographic parity for group fairness. In International Conference on Learning Representations, 2022b.
[19]
Z. Jiang, X. Han, H. Jin, G. Wang, R. Chen, N. Zou, and X. Hu. Chasing fairness under distribution shift: a model weight perturbation approach. 2023.
[20]
W. Jin, L. Zhao, S. Zhang, Y. Liu, J. Tang, and N. Shah. Graph condensation for graph neural networks. arXiv preprint arXiv:2110.07580, 2021.
[21]
W. Jin, X. Tang, H. Jiang, Z. Li, D. Zhang, J. Tang, and B. Yin. Condensing graphs via one-step gradient matching. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 720-730, 2022.
[22]
J. Kang, J. He, R. Maciejewski, and H. Tong. Inform: Individual fairness on graph mining. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 379-389, 2020.
[23]
J.-H. Kim, J. Kim, S. J. Oh, S. Yun, H. Song, J. Jeong, J.-W. Ha, and H. O. Song. Dataset condensation via efficient synthetic-data parameterization. In International Conference on Machine Learning, pages 11102-11118. PMLR, 2022.
[24]
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.
[25]
Ö. D. Köse and Y. Shen. Fairness-aware node representation learning. arXiv preprint arXiv:2106.05391, 2021.
[26]
S. Lee, S. Chun, S. Jung, S. Yun, and S. Yoon. Dataset condensation with contrastive signals. In International Conference on Machine Learning, pages 12352-12364. PMLR, 2022.
[27]
P. Li, Y. Wang, H. Zhao, P. Hong, and H. Liu. On dyadic fairness: Exploring and mitigating bias in graph connections. In International Conference on Learning Representations, 2021.
[28]
Z. Li and D. Hoiem. Learning without forgetting. IEEE transactions on pattern analysis and machine intelligence, 40(12):2935-2947, 2017.
[29]
H. Ling, Z. Jiang, M. Liu, S. Ji, and N. Zou. Graph mixup with soft alignments. In International Conference on Machine Learning. PMLR, 2023a.
[30]
H. Ling, Z. Jiang, Y. Luo, S. Ji, and N. Zou. Learning fair graph representations via automated data augmentations. In International Conference on Learning Representations, 2023b.
[31]
H. Liu, K. Simonyan, and Y. Yang. Darts: Differentiable architecture search. arXiv preprint arXiv:1806.09055, 2018.
[32]
J. Liu, T. Zheng, G. Zhang, and Q. Hao. Graph-based knowledge distillation: A survey and experimental evaluation. arXiv preprint arXiv:2302.14643, 2023a.
[33]
Z. Liu, Z. Jiang, S. Zhong, K. Zhou, L. Li, R. Chen, S.-H. Choi, and X. Hu. Editable graph neural network for node classifications. arXiv preprint arXiv:2305.15529, 2023b.
[34]
Z. Liu, K. Zhou, Z. Jiang, L. Li, R. Chen, S.-H. Choi, and X. Hu. DSpar: An embarrassingly simple strategy for efficient GNN training and inference via degree-based sparsification. Transactions on Machine Learning Research, 2023c. ISSN 2835-8856. URL https://openreview.net/forum?id=SaVEXFuozg.
[35]
C. Louizos, K. Swersky, Y. Li, M. Welling, and R. Zemel. The variational fair autoencoder. arXiv preprint arXiv:1511.00830, 2015.
[36]
N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan. A survey on bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1-35, 2021.
[37]
T. Nguyen, R. Novak, L. Xiao, and J. Lee. Dataset distillation with infinitely wide convolutional networks. Advances in Neural Information Processing Systems, 34:5186-5198, 2021.
[38]
W. Song, Y. Dong, N. Liu, and J. Li. Guide: Group equality informed individual fairness in graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1625-1634, 2022.
[39]
H. Suresh and J. V. Guttag. A framework for understanding unintended consequences of machine learning. arXiv preprint arXiv:1901.10002, 2, 2019.
[40]
L. Takac and M. Zabovsky. Data analysis in public social networks. In International scientific conference and international workshop present day trends of innovations, volume 1. Present Day Trends of Innovations Lamza Poland, 2012.
[41]
A. Tong, J. Huang, G. Wolf, D. Van Dijk, and S. Krishnaswamy. Trajectorynet: A dynamic optimal transport network for modeling cellular dynamics. In International conference on machine learning, pages 9526-9536. PMLR, 2020.
[42]
T. Wang, J.-Y. Zhu, A. Torralba, and A. A. Efros. Dataset distillation. arXiv preprint arXiv:1811.10959, 2018.
[43]
Y. Wang, B. Hooi, Y. Liu, and N. Shah. Graph explicit neural networks: Explicitly encoding graphs for efficient and accurate inference. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 348-356, 2023.
[44]
F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6871. PMLR, 2019.
[45]
S. Yang, Z. Xie, H. Peng, M. Xu, M. Sun, and P. Li. Dataset pruning: Reducing training data by examining generalization influence. arXiv preprint arXiv:2205.09329, 2022.
[46]
R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974-983, 2018.
[47]
Z. Zeng, R. Islam, K. N. Keya, J. Foulds, Y. Song, and S. Pan. Fair representation learning for heterogeneous information networks. In Proceedings of the International AAAI Conference on Web and Social Media, volume 15, pages 877-887, 2021.
[48]
B. H. Zhang, B. Lemoine, and M. Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pages 335-340, 2018.
[49]
B. Zhao, K. R. Mopuri, and H. Bilen. Dataset condensation with gradient matching. ICLR, 1(2):3, 2021a.
[50]
B. Zhao, K. R. Mopuri, and H. Bilen. Dataset condensation with gradient matching. ICLR, 1(2):3, 2021b.
[51]
K. Zhou, Q. Song, X. Huang, and X. Hu. Auto-gnn: Neural architecture search of graph neural networks. arXiv preprint arXiv:1909.03184, 2019.
Recommendations
Fair reception and Vizing's conjecture
In this paper we introduce the concept of fair reception of a graph which is related to its domination number. We prove that all graphs G with a fair reception of size γ(G) satisfy Vizing's conjecture on the domination number of Cartesian product graphs,...
Collapsible subgraphs of a 4-edge-connected graph
AbstractJaeger in 1979 showed that every 4-edge-connected graph is supereulerian, graphs that have spanning eulerian subgraphs. Catlin in 1988 sharpened Jaeger’s result by showing that every 4-edge-connected graph is collapsible, graphs that ...
Trivially noncontractible edges in a contraction critically 5-connected graph
An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is said to be contraction critically k-connected. An edge of a k-connected graph ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2023 Neural Information Processing Systems Foundation, Inc.
Publisher
Curran Associates Inc.
Red Hook, NY, United States
Publication History
Published: 30 May 2024
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Sep 2024