A Deep Latent Factor Graph Clustering with Fairness-Utility Trade-off Perspective

A Deep Latent Factor Graph Clustering with Fairness-Utility Trade-off Perspective Siamak Ghodsi L3S Research Center Hannover, Germany ghodsi[at]l3s.de Amjad Seyedi University of Mons Mons, Belgium seyedamjad.seyedi[at]umons.ac.be Tai Le Quy University of Koblenz Koblenz, Germany tailequy[at]uni-koblenz.de Fariba Karimi TU Graz Graz, Austria karimi[at]csh.ac.at Eirini Ntoutsi Bundeswehr University Munich, Germany eirini.ntoutsi[at]unibw.de Abstract—Fair graph clustering seeks partitions that respect network structure while maintaining proportional representation across sensitive groups, with applications spanning community detection, team formation, resource allocation, and social network analysis. Many existing approaches enforce rigid constraints or rely on multi-stage pipelines (e.g., spectral embedding followed by k -means), limiting trade-off control, interpretability, and scalability. We introduce DFNMF, an end-to-end deep nonnegative tri-factorization tailored to graphs that directly optimizes cluster assignments with a soft statistical-parity regularizer. A single parameter λ tunes the fairness–utility balance, while nonnegativity yields parts-based factors and transparent soft memberships. The optimization uses sparse-friendly alternating updates and scales near-linearly with the number of edges. Across synthetic and real networks, DFNMF achieves substantially higher group balance at comparable modularity, often dominating state-ofthe-art baselines on the Pareto front. The code is available at https://github.com/SiamakGhodsi/DFNMF.git. Index Terms—Trustworthy ML, Fair Graph Clustering, Community Detection, Heterogen. Networks, Deep Factorization I. INTRODUCTION Fair and trustworthy machine learning has advanced rapidly over the last decade [1]–[4], yet it remains underexplored in graph learning—especially graph clustering [5], [6]. Graph clustering partitions a network into cohesive groups and underpins applications such as community detection, team formation, resource allocation, and social network analysis [7]. Classical approaches maximize utility (e.g., modularity) or minimize cuts to uncover natural network structures, yet many real-world applications require balancing structural cohesion with demographic fairness. Consider academic collaboration networks where funders increasingly mandate diverse team compositions. Purely structuredriven clustering may recover prolific yet homogeneous groups that fail diversity requirements. Similarly, educational institutions forming student project teams must balance social connections with equitable assignments (Figure 1). These scenarios demand fair graph clustering—modifying natural community boundaries to achieve demographic balance while preserving meaningful network structure [8]. Two lines of research relate to our work. (i) Fair clustering for i.i.d. data: develop demographic-parity constraints for k -center/median/means via fairlets and related schemes [9], [10], alongside supervised fair GNNs for labeled settings [11]– [13]. These methods assume metric i.i.d. data or require labels, Fig. 1: Fair clustering of a 16-node graph (10 Male, 6 Female) into two equal-sized clusters. Left: Utilitarian clustering yields a structure-driven partition with a 6M:2F distribution for green and 4M:4F for lavender cluster, resulting in gender imbalance. Right: Fair clustering achieves a balanced 5M:3F distribution in both clusters by swapping memberships of nodes 1 and 13. making them unsuitable for graph-structured clustering. (ii) Fair graph clustering: primarily extends spectral clustering with hard demographic constraints [14]–[16], but eigendecompositions and post-hoc rounding (e.g., k -means) limit end-to-end control and scalability. Recent matrix-factorization approaches offer more flexibility, though contrastive NMF variants can struggle at larger scales [17]. To address these limitations, we propose DFNMF, an endto-end deep NMF framework for fair graph clustering. DFNMF integrates balanced fairness constraints—enforcing proportional group representation—directly into the clustering objective, enabling explicit utility–fairness trade-offs via a single parameter λ without post-processing. Deep tri-factorization captures multilevel network structure while maintaining scalability through sparse implementations. To our knowledge, this is the first deep hierarchical NMF model with integrated fairness designed specifically for graph clustering. Our contributions are: • End-to-end fairness integration: Joint representation learning and fairness enforcement without multi-stage pipelines or post-processing. • Tunable trade-off control: Single parameter λ enables precise utility–fairness balance adjustment. • Deep hierarchical architecture: Tri-factorization robust to graph sparsity and group-size heterogeneity. • Scalable sparse implementation: CSR-based operations with efficient alternating updates. • Comprehensive evaluation: Synthetic and real networks with statistical analysis, Pareto studies, and ablations. The remainder of this paper is structured as follows: Section II reviews the current literature and highlights the existing gaps. Section III formulates the problem and provides necessary preliminaries, including theoretical foundations of NMF. Section IV details our proposed DFNMF model. Section V presents the experimental results. Finally, Section VI concludes the paper and points out future research directions. II. RELATED WORKS Fairness-aware graph clustering aims to mitigate bias propagation by enforcing demographic constraints during network partitioning. While graph fairness has been studied extensively [5], [7], [18], relatively few works specifically tackle fairness in unsupervised graph clustering. The literature can be broadly divided into (1) methods primarily targeting independent and identically distributed (iid) data, and (2) those tailored specifically for graph-structured data. A. Fair Clustering for iid Data Fairness-aware clustering methods initially emerged for independent and identically distributed (iid) tabular data. Chierichetti et al. [9] introduced “fairlets” to enforce demographic parity in k -center and k -median clustering. Subsequent works extended fairness constraints to k -means and related objectives [10]. Some approaches construct similarity graphs from iid data to enable graph-based fairness reasoning [19], [20]. However, these methods rely on strong geometric or metric assumptions and cannot natively handle the complex relational dependencies inherent in real-world networks [5], [21]. While these methods address unsupervised fairness, they are fundamentally limited for graph clustering applications. Their experimental evaluations typically use simplified datasets that inadequately reflect the structural complexities of networked data, where connections themselves carry semantic meaning beyond mere similarity. B. Fair Graph Clustering Recent studies directly extend spectral clustering to incorporate fairness constraints for graph data. Kleindessner et al. [14] introduced demographic fairness constraints into spectral decompositions. Subsequent works improved computational efficiency using relaxation techniques and augmented Lagrangian methods [15], [16], [22]. However, these spectral methods face fundamental limitations: rigid fairness constraints, non-endto-end clustering requiring post-processing (e.g., k -means), discretization approximations, and limited interpretability. Graph embedding-based alternatives such as the method by Dong et al. [11] apply individual fairness through rankbased alignment, yet their embedding-driven strategy risks propagating biases from sensitive attributes. Ghodsi et al. [17] proposed asymmetric NMF with contrastive fairness regularization, offering improved interpretability but limited scalability due to computationally intensive pairwise contrastive terms. Supervised graph methods have also been explored for fairness-aware tasks. Ranking-based fairness models [11], fair GNN architectures [12], and sensitive attribute neutralization strategies [13] show promise in supervised settings. However, these approaches require labeled data and may suffer from proxy-bias propagation through learned embeddings, limiting their applicability to unsupervised community discovery tasks. GNN-based clustering methods like DMoN [23] provide scalable alternatives but lack integrated fairness constraints. While effective for supervised tasks, adapting such methods to incorporate fairness remains an open challenge. Table I summarizes existing methods across five key criteria. Most approaches either face scalability limitations, enforce rigid fairness constraints, or provide limited interpretability. Existing approaches trade off flexibility (softness), end-to-end optimization, and scalability—gaps our DFNMF addresses. Clearly, existing methods either face scalability constraints, rigid fairness enforcement, or limited interpretability. Method Soft? End-to-End Complexity Scalability Interpret. [23] DMoN " " O(nk2+|E|)Large ↑Low ↓ [14] FSC % % O(n3)Small ↓Low ↓ [16] sFSC % % O(|E|+n(h2+k2)) Medium Low↓ [15] iFSC % % O(n3)Small ↓Low ↓ [11] GNN-FSC % % O(n3)Small ↓Low ↓ [22] FNM-SC % % O(n4.5k4.5|E|)Small ↓Low ↓ [17] iFNMTF " " O(|E|k+nk2+k3)Medium High ↑ DFNMF (ours) " " O(T pk|E|)Large ↑High ↑ TABLE I: Representative methods for fair graph clustering. Soft? indicates soft (regularized) vs. hard constraints; End-toEnd denotes no post-hoc rounding; complexity is measured in graph size n , edges |E| , clusters k , and iterations T , and Interpret. refers to parts-based transparency of assignments/factors. III. PROBLEM FORMULATION & PRELIMINARIES A. Problem Definition Consider an undirected graph G= (V, E) with adjacency matrix A∈Rn×n encoding edge connections, where aij >0 indicates a positive edge between nodes vi, vj∈V , and aij = 0 otherwise (assuming no self-loops, thus aii = 0 ). Suppose the node set V is partitioned into m disjoint demographic groups based on sensitive attributes, such that V=˙ ∪s∈[m]Vs . Our goal is to find a clustering C=C1˙ ∪. . . ˙ ∪Ck into k clusters that maximizes structural cohesion while satisfying demographic balance (Definition 1), ensuring fair representation. B. Demographic Balance The balance criterion, originally introduced by Chierichetti et al. [9], ensures that each cluster maintains demographic proportions similar to the global distribution. This concept, first applied to k -median, was later adapted to spectral clustering in [14], [16]. While initially formulated for iid data, we extend this principle to our context, where demographic balance must be preserved over node partitions, formalized as follows: Definition 1 (Generalized Demographic Balance).Given a partitioning of the vertex set V into k≥2 communities, the clustering is said to be fair with respect to a partition into demographic groups s∈[m] if, in each community Cl , the proportion of group-snodes matches its global share: |Vs∩Cl| |Cl|=|Vs| |V|,∀s∈ {1, . . . , m}, l ∈ {1, . . . , k}.(1) Here, V={v1, v2, . . . , vn} is the set of graph nodes, |Vs| is the number of nodes belonging to demographic group s , and |V|=n is the total number of nodes. This constraint operationalizes statistical parity for clustering and forms the foundation of the fairness regularizer introduced in Section IV. C. Nonnegative Matrix Factorization (NMF) NMF is widely used due to its interpretability, versatility, and adaptability to constraints, performing a low-rank approximation of data [24]. Its nonnegativity constraints yield parts-based, sparse representations that are inherently interpretable, making NMF particularly suitable for domains like text mining, image analysis, and bioinformatics [25], [26]. Formally, given data matrix X∈Rm×n , NMF seeks basis matrix W∈Rm×k and representation matrix H∈Rk×nby solving: min W,H≥0∥X−W H∥2 F,(2) where ∥A∥F=qPij A2 ij denotes the Frobenius norm. 1) NMF Tri-Factorization for Graph Clustering:The general NMF formulation (2) is not directly tailored for graph clustering. Hence, Symmetric-NMF [27] was developed specifically for this purpose. Symmetric-NMF factorizes a graph adjacency matrix A∈Rn×n into latent node representations H∈Rn×u , encouraging attraction between connected nodes and repulsion otherwise. Formally: min H≥0∥A−HH⊤∥2 F.(3) Extending Symmetric NMF, the NMF Tri-Factorization (NMTF) [28] introduces cluster-cluster interactions via matrix W, leading to: min H,W≥0∥A−HW H⊤∥2 F,(4) where W represents interactions between clusters, improving interpretability and flexibility. An epistemic comparison of theoretical foundations and differences of NMF-based clustering vs neural network architectures is provided in the Appendix VIII. IV. DEEP FAIR NMF MODEL This section presents DFNMF, a deep fair tri-factor model for community detection on attributed graphs. A proportional group-balance regularizer is built into the objective, producing soft memberships and direct cluster assignments—no post-hoc k -means. The design (i) performs end-to-end clustering with interpretable nonnegative factors; (ii) couples graph topology with demographic indicators to promote balanced communities; (iii) traverses the utility–fairness trade-off via a single parameter λ ; and (iv) scales through sparse-friendly alternating updates with shallow pretraining and deep fine-tuning. A. Soft Balanced Fairness (BF) We encode node–cluster memberships by H∈Rn×k . For partitioning V into k clusters, projecting H by node memberships yields: nl X i=1 Hil = 1,∀l∈ {1, . . . , k}.(5) This encoding enforces nonnegativity, improving interpretability via parts-based memberships. With column-stochastic normalization (Eq. (5) ), each entry Hil ∈[0,1] serves as a soft membership weight for node viin cluster Cl. Definition 2 (Demographic Group Encoding).Let the vertex set V be partitioned into m sensitive groups V=˙ ∪m s=1Vs, and define the binary sensitive group indicator for node vi as g(s) i=(1,if vi∈Vs, 0,otherwise. We then define the group indicator for each sensitive group as f(s)=g(s)−|Vs| n1n, s ∈ {1, . . . , m −1}(6) where 1n∈Rn is the vector of ones. We obtain the matrix F=f(1) f(2) · · · f(m−1)∈Rn×(m−1) by stacking these m−1 vectors as columns. Note: We use m−1 columns to avoid linear dependency, since group proportions sum to one. The matrix F stacks mean-centered (proportionally centered) group indicators. It will encode demographic balance via the linear condition F⊤H=0 and induce the fairness regularizer ∥F⊤H∥2 F . This construction is used as Step 1 in Algorithm 1. Definition 3 (Soft Balanced Fairness).A partitioning represented by a column-stochastic membership matrix H is fair with respect to the sensitive groups if, for each cluster Cl and every group s∈ {1, . . . , m} , the proportion of mass from group Vs in Cl equals the global group proportion. It means that, a clustering H is fair if eq. (1) strictly holds for all clusters and all sensitive groups. In our soft clustering formulation, this condition is equivalent to the following: X i∈Vs Hil =|Vs| nfor all s∈ {1, . . . , m −1}, l ∈ {1, . . . , k}. Equivalently, stacking the deviations for all groups and clusters, the fairness condition can be formulated as F⊤H=0. Lemma 1 (Equivalence to Demographic Balance).Let H be a nonnegative, column-stochastic matrix. Then F⊤H=0 of Definition 3, is equivalent to the fairness condition in Eq. (1) . Proof. Since each column of H is normalized by Eq. (5) , for any cluster l we have Pn i=1 Hil = 1. Then, for each sensitive group s∈[m−1] and cluster l , the (s, l) th entry of F⊤H is (F⊤H)sl = n X i=1 f(s) iHil =X i∈Vs Hil −|Vs| n n X i=1 Hil =X i∈Vs Hil −|Vs| n. Thus, (F⊤H)sl = 0 if and only if Pi∈VsHil =|Vs| n, which is exactly equal to the fairness condition in Eq. (1). B. Shallow Fair NMF Model We begin with a shallow Fair NMF (FNMF) that serves as the foundation for our deep hierarchical extension. To encode fairness, we augment the standard tri-factorization with a penalty derived from Lemma 1, encouraging proportional representation during optimization: min H,W≥0∥A−HW H⊤∥2 F+λR(H),(7) where H∈Rn×k + are soft cluster memberships and W∈ Rk×k +captures inter-cluster interactions. a) Fairness penalty.: We enforce demographic balance via the smooth quadratic penalty (i.e. L2norm): R(H) = ∥F⊤H∥2 F= m−1 X s=1 k X l=1 f(s)⊤hl2,(8) where f(s) is column s of F and hl is column l of H . By Lemma 1, R(H)=0 iff the balance condition holds; decreasing R drives cluster compositions toward global group proportions. Substituting (8) into (7) yields our shallow FNMF objective: min H,W≥0∥A−HW H⊤∥2 F | {z } utility term +λ∥F⊤H∥2 F | {z } fairness term ,(9) with λcontrolling the utility–fairness trade-off. C. Deep Fair NMF (DFNMF) Model Shallow tri-factorization is transparent and efficient, but can miss multi-level structure on large graphs. We therefore adopt a deep tri-factorization inspired by [29] in which successive nonnegative layers capture increasingly coarse communities. Let Ψ= p Y i=1 Hi,Hi∈Rri−1×ri +(10) where r0=n≥ · · · ≥ rp=k . and Wp∈Rk×k + encode final inter-/intra-cluster interactions. The graph is reconstructed as A≈ΨWpΨ⊤(11) yielding direct soft memberships (columns of Ψ ) without any post-hoc clustering. a) Unified objective.: We integrate the balance penalty from Eq. (8) at the final layer: min {Hi}p i=1≥0,Wp≥0 L= A−ΨWpΨ⊤ 2 F | {z } utility +λ F⊤Ψ 2 F | {z } fairness , (12) The regularizer acts on Ψ , i.e., the final memberships, and λ tunes the utility–fairness trade-off. b) Pipeline illustration.: Figure 2 depicts the hierarchy ( H1,H2,H3 ) and a 45-node example with two sensitive groups (triangles/circles). Small λ preserves intrinsic structure but yields imbalanced clusters (e.g., 5:9 , 5:11 , 8:7 ); large λ adjusts memberships toward parity (e.g., 7:11,5:7,6:9). This demonstrates controllable movement along the utility–fairness spectrum by tuning λ. D. Optimization We solve the DFNMF objective in Eq. (12) with alternating minimization [30], updating each factor while holding the others fixed. As the problem is non-convex, this procedure converges to a local optimum but does not guarantee global optimality. a) Pretraining (Algorithm 1, lines 2–6).: To accelerate convergence, we initialize each layer via sequential NMTF: first factorize A≈H1W1H⊤ 1 , then recursively factorize Wi−1≈ HiWiH⊤ i for i= 2, . . . , p . This provides warm starts for {Hi}and Wp, reducing wall time in practice [31]. b) Fine-tuning (Algorithm 1, lines 7–16).: With Ψ defined as in Eq. (10) , we alternate updates for the membership blocks {Hi}and the interaction matrix Wp. 1) Update rule for membership blocks Hi :Fix all variables except Hi. Using the block products Ψi=H1· · · Hi−1,Φi=Hi+1 · · · Hp, (with Ψ1=Iand Φp=I), the subproblem is min Hi≥0L(Hi) =  A−ΨiHiΦiWpΦ⊤ iH⊤ iΨ⊤ i 2 F(13) +λ F⊤ΨiHiΦi 2 F. Following a standard Lee–Seung style multiplicative update derived [24] via KKT conditions (derivation omitted for brevity), we obtain Hi←Hi⊙ Ni Di!1/4 ,(14) where we introduce compact shorthands Ni=Ψ⊤ iA⊤ΨWp+AΨW⊤ p+λF F ⊤Ψ−Φ⊤ i, Di=Ψ⊤ iΨW⊤ pΨ⊤ΨWp+ΨWpΨ⊤ΨW⊤ p +λF F ⊤Ψ+Φ⊤ i, and B+= max(B,0) , B−=−min(B,0) so that B= B+−B−. Update (14) is used in Algorithm 1, line 13. The detailed derivation is discussed in the Appendix VIII-B. 7:11 5:7 6:9 5:9 5:11 8:7 balance coherence λ trade-off parameter Structure-oriented clustering Fairness-oriented clustering Input graph Adjacency Matrix Fig. 2: DFNMF schematic and example. A 45-node graph with imbalanced gender distribution of 40%/60%(27 , 18 ) is factorized through H1,H2,H3 . Two solutions illustrate the effect of λ : small λ preserves structure but yields imbalance (5:9, 5:11, 8:7); large λimproves parity (7:11, 5:7, 6:9), highlighting the utility–fairness trade-off. Algorithm 1 [Balanced] Deep Fair NMF (DFNMF) Input: The adjacency matrix of graph G,A; layer size of each layer, ri; fairness regularization parameter λ; Output:Wi(1 ≤i<p),Hi(1 ≤i<p), and the membership matrix Ψ; 1: Constructing the balance fairness matrix F according to Definition 2; 2: ▷Pre-training process: 3: W1,H1←NMTF(A, r1); 4: for i= 2 to pdo 5: Wi,Hi←NMTF(Wi−1, ri); 6: end for 7: ▷Fine-tuning process: following Section IV-C 8: Wi,Hi←DFNMF(Ψi, p); deep hierarchical learning 9: while convergence not reached do 10: for i= 1 to pdo 11: Ψi−1←Qi−1 τ=1 Hτ(Ψ0←I); 12: Φi+1 ←Qp τ=i+1 Hτ(Φp+1 ←I); 13: Update clustering matrix Hiusing (14); 14: Ψi←Ψi−1Hi; 15: Update interaction matrix Wpusing (16); 16: end for 17: end while 2) Update rule for interaction matrix Wp :By fixing {Hi}p i=1, we can update Wpby solving min Wp L(Wp) =∥A−ΨWpΨ⊤∥2 F,s.t. Wp≥0,(15) Let ¯ A=Ψ⊤AΨ and S=Ψ⊤Ψ . The multiplicative update becomes Wp←Wp⊙¯ A S WpS,(16) which corresponds to Algorithm 1, line 15. a) Remarks.: (i) Eqs. (14) – (16) preserve nonnegativity and monotonically decrease the objective under the usual assumptions for multiplicative updates. (ii) The shorthands Ni,Di compactly collect terms as auxiliary variables improving readability. E. Computational Complexity Our method involves iterative updates of the factor matrices Wp(16) and Hi(14) until convergence. The update of Wp has a complexity of O(n2k+nk2+k3) , while the update of each Hi , which incorporates the fairness regularization, has a complexity of O(n2k+nk2+n(m−1)k+nrik+ri(m−1)k) . In practice, k , m , and ri are typically small, making the overall cost dominated by operations involving n . To further improve efficiency, our implementation uses sparse CSR representations of A , reducing the dominant matrix operations to O(|E|k) , where |E| is the number of non-zero entries in A (i.e. number of edges). This yields an overall per-iteration complexity of O(p|E|k) . Optional block coordinate descent (not used in our experiments) can further reduce memory from O(n2) to O(bk) . V. EXPERIMENTS This section presents experimental evaluations of our proposed model compared to baselines on both real-world and synthetic datasets. Results are assessed based on the utility and fairness of partitioning under various conditions. A. Experimental Setup All experiments were conducted on a NVIDIA A3090 GPU with 24 GB of memory. Sparse graph operations were implemented using the scipy.sparse classes of csr_matrix and coo_matrix , and their counterparts in torch.sparse . Optimized sparse implementations are detailed in code repository. We use a 500 epochs max, and p= 4 layers with 64 components (unless otherwise stated). The final layer is always projected to k , the number of communities (i.e., clusters) for DFNMF. The depth ( p= 4 ) offers sufficient expressiveness while avoiding over-smoothing in deeper architectures [31]; deeper variants showed no empirical improvement. All results and ablations (Appendix 2 IX) average over 10 seeds; the λ⋆ selection rule was cross-checked via a linear scalarization to confirm robustness (see Section V-E). 1) Unsupervised Setting:As we address the unsupervised task of clustering, there is no train-validation-test split. Instead, the entire dataset is used as input during each model run. Importantly, no ground-truth labels are accessed during training or inference. Label-based metrics (e.g., ARI or accuracy) are used only post hoc for evaluation assessment. 2) Parameter Selection:We sweep λ on a logarithmic grid {10−3,...,103} and form the utility–fairness curve (˜ Q(λ),˜ B(λ)) after min–max scaling of Q and ¯ B to [0,1] (per dataset and k ). We first retain the Pareto front ΛP (undominated points), then select λ⋆= arg min λ∈Λ P (˜ Q(λ),˜ B(λ)) −(1,1)  2, with a tie–breaker favoring smaller |˜ Q(λ)−˜ B(λ)| (closer to the identity guide as shown in Section V-E 4). This setting obtains a robust and reproducible λ⋆ scheme, which are reported together with their bracket {λ⋆/10,10λ⋆} in the appendix B. All the experimental results throughout the paper are reported according to our optimal λ⋆for each dataset. 3) Baselines:We compare DFNMF with seven baselines introduced previously in Section II. They comprise vanilla models of spectral clustering (SC) [32], tri-factor NMF (NMTF) [27], GNN-based model (DMoN) [23], and fairness-aware models: fair, scalable, individual spectral models (FairSC, sFSC, iFSC) [14]–[16], and individually fair NMTF (iFNMTF) [17]. All hyperparameters are tuned according to the original papers. 4) Evaluation Measures:We assess clustering utility on labeled datasets using accuracy (ACC) and adjusted Rand index (ARI), and on unlabeled datasets using Newman’s modularity (Q) [33]. Accuracy calculates the proportion of nodes correctly assigned to their respective clusters. ARI is a pairwise agreement measure between predicted and groundtruth clusterings, adjusted for chance, and ranges from −1 (random clustering), through 0 (chance-level agreement), to 1 (perfect clustering). Modularity quantifies the strength of division of a graph into clusters by comparing the observed intra-cluster connectivity to that expected under a random null model, also ranging from −1 to 1 . For fairness, we report average balance ( ¯ B )[14], [16] and statistical parity deviation ( ∆SP )[34]. ¯ B computes the mean minimum group proportion across clusters, where higher values in [0,1] indicate fairer clusters. ∆SP measures deviation from global group proportions within each cluster: ∆SP =1 k k X l=1 m X s=1  |Vs∩Cl| |Cl|−|Vs| |V|,(17) where lower values (approaching 0 ) imply better demographic parity. All metrics are averaged over 10 runs. ACC and ¯ B lie in [0,1], while ARI, Q, and ∆SP range in [−1,1]. B. Datasets We evaluate DFNMF on 11 networks (8 real-world, 3 synthetic) with diverse structural setups, group imbalances, and homophily levels. Dataset characteristics, including number of nodes ( |V| ), edges ( |E| ), sensitive groups, number of clusters ( k ), edge density, and homophily, are summarized in Table II. Homophily quantifies the tendency of nodes to connect within the same sensitive group, indicating inherent network bias. Thus, datasets with higher homophily tend to exacerbate the impact of demographic imbalances on fairness. TABLE II: Summary statistics for datasets used in experiments. Network |V| |E|Attribute (# groups) Edge Density Homophily k SBM 2,000 267,430 attr (2) 0.133 0.82 5 5,000 978,959 attr (2) 0.078 0.82 5 10,000 2,603,190 attr (2) 0.052 0.82 5 Pokec-n 67,797 882,765 age (4) 0.0384 0.399 2 Pokec-z 66,570 729,129 age (4) 0.0329 0.360 2 NBA 403 8,285 ethnicity (2) 0.102 0.72 2 Diaries 120 348 gender (2) 0.048 0.61 – Friendship 134 406 gender (2) 0.049 0.60 – Facebook 156 1,437 gender (2) 0.120 0.57 – DrugNet 293 284 ethnicity (3) 0.014 0.88 – LastFM 7,624 27,806 country (6) 0.001 0.92 – 1) Synthetic Networks:are generated using an extended Stochastic Block Model (SBM) following [14]–[16], with explicitly controlled group memberships and cluster assignments. Each node set V =[ n ] is partitioned into m groups V=V1˙ ∪. . . ˙ ∪Vm and k clusters V=C1˙ ∪. . . ˙ ∪Ck , ensuring proportional representation of each sensitive group within clusters (fair clustering by construction). 2) Real-World Networks:Our collection of real datasets represents diverse social and interaction graphs with varying demographics and biases [35]–[38]: small-scale datasets (Facebook,Friendship,Diaries) exhibit moderate gender imbalance (around 60% majority groups), and medium-sized datasets like DrugNet and NBA show stronger imbalances (majority ethnic groups above 70%). Larger datasets such as Pokec-n and Pokeczpresent considerable imbalance (majority age group over 70%) with moderate homophily (0.36–0.40), while highly sparse and homophilous graphs like LastFM (country, homophily = 0.92) and DrugNet (ethnicity, homophily = 0.88) pose greater fairness challenges. These variations allow comprehensive exploration of fairness-utility trade-offs. Fig. 3: SBM networks with varying node sizes: comparison of clustering and fairness metrics. Arrows ( ↑ / ↓ ) indicate whether higher/lower is better. C. Results on Synthetic Datasets To benchmark the baselines under controlled conditions, we conducted experiments on three variants of the SBM networks with 2,000, 5,000, and 10,000 nodes. Results are depicted in Figure 3. SFSC and FSC baselines report identical results; thus, only SFSC is visualized to conserve space. The results indicate that DFNMF, SFSC, and iFSC consistently outperform other baselines, including vanilla models (SC, NMTF, DMoN) and the iFNMTF by reporting the highest Q , B , ARI , ACC , and lowest ∆SP . These findings strongly support that the three models have an advantage in trading-off clustering utility and fairness under varying degrees of structural complexity and group imbalance on SBM networks. D. Results on Real-world Datasets We further evaluate DFNMF and baseline models on a variety of real-world networks, with diverse structural and fairness challenges. These include datasets with strong group imbalance (e.g., Pokec, NBA), as well as sparse, highly homophilous graphs such as LastFM and DrugNet, as characterized in Section V-B and Table II. Given the comparable performance of spectral methods on synthetic data, we focus here on their limitations in more complex, real-world scenarios. 1) UnLabeled Datasets:Table III presents results on datasets without ground-truth labels, evaluated using average balance ( B ) and modularity ( Q ) under two cluster settings ( C =5 and C =10). On DrugNet and LastFM, DFNMF shows a clear advantage, achieving both high modularity and fairness. In contrast, spectral baselines (SFSC, FSC, iFSC) perform poorly due to their rigid fairness constraints, which often fail to adapt to highly sparse and biased network structures. On smaller networks such as Facebook,Friendship, and Diaries, DFNMF maintains top fairness performance and ranks second in modularity—slightly behind SFSC or iFSC—demonstrating strong overall adaptability even in simpler settings. 2) Labeled Datasets:We evaluate DFNMF against SFSC—a fair spectral clustering baseline—and DMoN, a state-of-theart GNN-based model. This comparison is designed to assess DFNMF’s scalability and fairness performance across varying data complexities. Specifically, we test whether spectral methods like SFSC degrade under high-dimensional settings, and whether DMoN’s prior limitations are due to dataset scale or inherent model bias. Table IV reports results on three Labeled TABLE III: Performance on unLabeled datasets for k=5 and k=10 number of clusters. Model DrugNet Diaries Facebook Friendship LastFM k=5 k=10 k=5 k=10 k=5 k=10 k=5 k=10 k=5 k=10 DMoN B0.00 0.00 0.263 0.034 0.267 0.194 0.182 0.040 0.00 0.00 Q0.326 0.324 0.145 0.165 0.047 0.034 0.129 0.121 0.526 0.360 SC B0.030 0.020 0.681 0.467 0.295 0.181 0.362 0.282 0.005 0.002 Q0.607 0.633 0.631 0.669 0.454 0.450 0.575 0.602 0.418 0.419 SFSC B0.052 0.026 0.684 0.494 0.601 0.436 0.485 0.399 0.067 0.033 Q27.00 52.56 0.808 0.698 0.500 0.512 0.626 0.665 0.034 0.040 FSC B0.052 0.026 0.684 0.494 0.601 0.436 0.485 0.399 0.067 0.033 Q0.270 0.525 0.808 0.698 0.500 0.512 0.626 0.665 0.034 0.040 iFSC B0.055 0.037 0.800 0.495 0.564 0.452 0.581 0.520 0.065 0.032 Q0.279 0.457 0.657 0.697 0.515 0.496 0.624 0.683 0.007 0.013 iFNMF B0.098 0.114 0.706 0.578 0.527 0.001 0.613 0.551 0.071 0.029 Q0.116 0.058 0.238 0.129 0.239 0.004 0.216 0.621 0.254 0.225 DFNMF B0.162 0.141 0.787 0.707 0.767 0.614 0.614 0.623 0.091 0.084 Q0.591 0.524 0.716 0.594 0.503 0.432 0.666 0.604 0.420 0.455 TABLE IV: Performance (mean ± std) on Labeled datasets. Arrows (↑/↓) show if higher/lower is better. Metric Model Pokec-n Pokec-z NBA ARI ↑ DFNMF 0.0051 ±0.001 0.0158 ±0.002 0.1203 ±0.012 SFSC 0.0009 ±0.000 0.0009 ±0.000 0.0825 ±0.007 DMoN 0.0024 ±0.000 0.0022 ±0.000 0.0741 ±0.006 Q↑ DFNMF 0.2067 ±0.005 0.1910 ±0.026 0.1344 ±0.012 SFSC 0.0001 ±0.000 0.0001 ±0.000 0.1089 ±0.013 DMoN 0.1801 ±0.003 0.1625 ±0.004 0.1162 ±0.008 ACC ↑ DFNMF 0.6879 ±0.052 0.7767 ±0.096 0.6765 ±0.010 SFSC 0.8476 ±0.012 0.8165 ±0.042 0.6500 ±0.004 DMoN 0.5252 ±0.035 0.5062 ±0.039 0.5232 ±0.026 B↑ DFNMF 0.1844 ±0.017 0.2905 ±0.025 0.4373 ±0.028 SFSC 0.0974 ±0.010 0.2249 ±0.021 0.3590 ±0.052 DMoN 0.1135 ±0.002 0.0589 ±0.004 0.0012 ±0.040 ∆SP ↓ DFNMF 0.0194 ±0.002 0.0189 ±0.000 0.0018 ±0.000 SFSC 0.5664 ±0.042 0.0573 ±0.016 0.0030 ±0.000 DMoN 0.3856 ±0.020 0.4143 ±0.053 0.0087 ±0.001 datasets—Pokec-n,Pokec-z, and NBA—using both utility (ACC, ARI, Q ) and fairness metrics ( B , ∆SP ). DFNMF consistently achieves the best overall performance, offering a strong balance between clustering quality and fairness. On Pokec datasets, it improves Q and ARI while also ensuring B and lower ∆SP . SFSC, while competitive in raw accuracy, fails on fairness and modularity due to its rigid constraints that tend to favor trial solutions with dominant groups. DMoN shows moderate utility but poor fairness, likely due to bias propagation through GNN embeddings and lack of clear debiasing policies. On the NBA dataset, which presents moderate homophily and high group imbalance, DFNMF again outperforms both baselines across all metrics, demonstrating its adaptability and robustness in handling complex group structures while maintaining fairness. E. Convergence, Interpretability, scalability, and FairnessUtility Trade-offs analysis 1) Convergence Analysis.:DFNMF employs a two-phase optimization strategy: a multi-layer pretraining phase with shallow NMTF (with known convergence guarantees [39]) and a deep fine-tuning phase minimizing the fairness-aware objective (12) . Figure 4 shows convergence curves on synthetic graphs (5K and 10K nodes) for both the fairness-aware variant ( λ =10) and a fairness-agnostic version ( λ =0). Both converge within 150 iterations; the fairness-regularized version stabilizes at a slightly higher loss, reflecting the additive influence of fairness penalties. Fig. 4: Convergence curves on SBM graphs (5K and 10K nodes), comparing DFNMF with/without fairness regularization ( λ= 10 vs. λ= 0 ). Both variants converge rapidly; the fair version yields a higher loss due to the added fairness penalty. 2) Interpretability Analysis:DFNMF is interpretable by construction: its nonnegative factors encode parts-based soft memberships across the hierarchy of nonnegative affinities. On the 60-node graph in Fig. 5, the first layer assigns nodes to 12 micro-clusters ( H1 ), the second maps micro-clusters to three communities ( H2 ), and Ψ=H1H2 yields final node–community affinities. A compact slice of H1 (nodes 1–5 and 56–60) is shown in Table V; the full H1 appears in Appendix IX-C . Figure 6 illustrates the relationship of micro-cluster→community mapping H2 with the corresponding (trimmed) node → community matrix Ψ; complete matrices are deferred to Appendix IX-C. Two patterns underpin interpretability. (i) Sparse micromemberships: rows of H1 are typically few-peaked, indicating that most nodes participate in a small number of micro-clusters; rows with multiple peaks (e.g., node 5 in Table V) flag potential TABLE V: Node → micro-cluster memberships ( H1 ). We show nodes 1–5 and 56–60; full table in Appendix IX-C. Node Micro-clusters A B C D E F G H I J K L 1 0.26 0.00 0.00 0.00 0.00 0.04 0.00 0.00 0.01 0.00 0.00 0.00 2 0.25 0.00 0.01 0.00 0.01 0.09 0.02 0.00 0.01 0.00 0.04 0.00 3 0.21 0.00 0.01 0.00 0.09 0.03 0.00 0.00 0.00 0.00 0.11 0.00 4 0.23 0.00 0.00 0.00 0.00 0.03 0.00 0.00 0.00 0.00 0.00 0.00 5 0.31 0.00 0.02 0.00 0.01 0.15 0.05 0.10 0.05 0.02 0.09 0.00 . . . 56 0.01 0.00 0.24 0.00 0.00 0.04 0.13 0.00 0.01 0.00 0.25 0.00 57 0.06 0.00 0.26 0.00 0.00 0.05 0.01 0.09 0.06 0.01 0.26 0.00 58 0.00 0.00 0.22 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.24 0.00 59 0.00 0.00 0.31 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.10 0.00 60 0.00 0.00 0.19 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.04 0.00 bridge nodes. (ii) Structured aggregation: H2 is nearly onehot for core micro-clusters (e.g., A → I, B → II, C → III), while boundary micro-clusters (e.g., D/E/H) spread mass across communities—capturing inter-community conduits. Multiplying H1 by H2 consolidates these signals: nodes with concentrated micro-membership become near one-hot in Ψ , whereas mixed rows remain soft. This traceability—from node → micro ( H1 ) to micro → community ( H2 ) to node → community ( Ψ )—supports transparent auditing of how local structure (under fairness regularization) aggregates into global communities. 3) Scalability Analysis:Table VI reports wall-clock runtime (seconds) and memory footprint of DFNMF against baselines on synthetic Erd˝ os-Rényi graphs with varying sizes, averaged over 10 runs on a single NVIDIA A3090 GPU. TABLE VI: Scalability on Erd˝ os-Rényi Graphs ( p= 2 , k= 128) Scale Methods Nodes Edges sFSC iFSC NMTF DMoN DFNMF Runtime (seconds) 104≃10542.3 48.7 2.8 8.3 1.5 105≃1061842 2103 31.6 78.4 9.8 106≃107OOM OOM 413 8932 92.4 Memory (GB) 104≃1052.1 2.4 0.8 1.2 0.4 105≃10645.2 52.3 5.4 8.1 2.1 106≃107OOM OOM 21.3 OOM 12.1 DFNMF demonstrates higher scalability with near-linear runtime growth O(|E|kp) versus spectral methods’ O(n3) . Beyond 100K nodes, spectral approaches exhaust memory while DFNMF processes million-node graphs efficiently. The advantage over NMTF is due to CSR-based sparse operations and pre-training process that remarkably reduces iterations. 4) Fairness–Utility Trade-offs:We assess trade-offs similar to [40], [41] at k=5 on DrugNet and LastFM (Fig. 7) by sweeping λ∈[10−3,103] and plotting (Q, ¯ B) . Blue points are DFNMF solutions; other markers are baselines. We first retain the Pareto front (undominated DFNMF points) and then select the ideal-point configuration (closest to (1,1) after min–max 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 33 34 35 31 32 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 A B C D E FG H I J K L A B C D E FG H I J K L I II III Fig. 5: DFNMF hierarchy on a 60-node graph. (a) Input graph; node shapes denote sensitive groups. (b) Micro-clusters (A–L) discovered by the first layer (H1). (c) Three coarse communities obtained by aggregating micro-clusters via H1; final node–community affinities are Ψ=H1H2. Fig. 6: Micro → community ( H2 ) and node → community ( Ψ= H1H2) soft memberships. scaling), shown as the green star at λ⋆= 100 —the same setting reported in Table III. Dashed identity lines provide a balanced trade-off guide (top-right is best), and shaded curvature indicates empirical fronts. Consistent patterns emerge: DMoN and SC attain higher Q but poorer balance; fairness-oriented spectral baselines (FSC/SFSC/iFSC) improve ¯ B at the expense of Q . In contrast, the DFNMF sweep spans the spectrum: increasing λ moves solutions rightward (higher ¯ B ) with some loss in Q , while decreasing λ moves them upward (higher Q ) with lower ¯ B . At the extremes, DFNMF reaches fronts that surpass baselines on either objective individually, while λ⋆ lies near the identity guide, offering a balanced, high-quality operating point. VI. CONCLUSION AND OUTLOOK We introduce DFNMF, an end-to-end deep matrix factorization framework that directly integrates fairness constraints into graph clustering. Unlike existing approaches that rely on rigid NTMF SFSC FSC SC iFSC iFNMF (a) DrugNet (k = 5) NTMF SFSC FSC SC iFSC iFNMF (b) LastFM (k = 5) Fig. 7: Pareto plots for k=5 . Blue: DFNMF across λ∈ [10−3,103] ; green star: λ⋆=100 selected on the Pareto front via the ideal-point rule. Dashed identity lines mark balanced trade-offs; shaded curves indicate empirical fronts.