Deep Nonnegative Matrix Factorization for Fair and Explainable Graph Clustering

Abstract. This paper introduces DFEGC (Deep Fair Explainable Graph Clustering), a novel framework that si-multaneously addresses three critical challenges in graph analysis: clustering accuracy, fairness, and interpretability. While existing graph clustering methods excel in performance, they often neglect fairness considerations and provide limited explainability. Our approach integrates deep nonnegative matrix factorization with fairness constraints and interpretability mechanisms through three key innovations: (1) a multi-layer NMF architecture that captures hierar-chical graph structures while preserving nonnegativity, (2) a fairness regularization term based on Hilbert-Schmidt Independence Criterion (HSIC) to reduce dependence between cluster assignments and sensitive attributes, and (3) explainability mechanisms that promote sparsity and semantic coherence in the learned representations. Through extensive experiments on six real-world datasets, we demonstrate that DFEGC achieves superior clustering performance while maintaining strong fairness properties. The model also generates more interpretable results, with higher sparsity scores and better semantic coherence than competing approaches. Ablation studies validate the importance of our fairness and explainability components, showing optimal performance. DFEGC’s balanced approach makes it particularly suitable for sensitive applications in social networks, healthcare, and education systems where accuracy, equity, and transparency are all essential requirements