WorksComputer Science
FairPGT: Partitioned Graph Transformers for Dual-Level Fair Graph Clustering
Abstract
Clustering on attributed graphs can produce demographically biased clusters, particularly when communities align with protected groups. Graph transformers can amplify this bias through same-group attention, while global attention limits scalability. We propose FairPGT, a partitioned graph transformer for fair graph clustering. FairPGT restricts attention to METIS partitions and connects them through routing tokens, which divides the quadratic cost of attention by the number of partitions. A graph-aware self-training target guides clustering, with a provably bounded deviation from the standard DEC target. Fairness is imposed at two levels: a mutual-information term promotes demographic parity in cluster assignments, while a normalized cross-group attention ratio (nCGAR) guides attention toward group neutrality through self-distillation. We prove that the nCGAR correction moves attention toward neutrality and establish a condition preventing overshooting. Across seven benchmarks, FairPGT achieves the best clustering performance and statistical parity on the three largest graphs (Credit, Pokec-n, Pokec-z), with a statistical-parity gap approximately ten times lower than DMoN, and is Pareto-dominated on only one dataset. On controlled stochastic block models, FairPGT attains 97% of the derived upper bound on NMI for exactly fair clustering when communities and protected groups coincide. These graphs further show that, under strong alignment, assignment-level fairness alone makes the attention group-heterophilous, whereas attention-level fairness alone improves neutrality without ensuring fair clusters. Code for reproducibility is available at https://github.com/SiamakGhodsi/FairPGT.
Email addresses: [email protected] (Siamak Ghodsi), [email protected] (Amjad Seyedi), [email protected] (Sahar Tahmasebi), [email protected] (Eirini Ntoutsi), [email protected] (Sören Auer)
Introduction
When a bank segments its customers or a platform groups its users, the resulting clusters decide who is offered what. Graph clustering, closely related to community detection, groups the nodes of a graph into structurally coherent communities and is a fundamental unsupervised task in network analysis, with applications in fraud analysis, bioinformatics, and recommendation [1, 2, 3, 4, 5]. When nodes carry protected attributes such as gender, age, or nationality, the communities a clustering finds can line up with demographic groups, and because clusters are used downstream, to target services or to segment users, such alignment can turn into biased decisions [6, 7]. The problem is hardest in unsupervised graph learning, where no label tells useful structure apart from structure that merely reflects the protected attribute.
Bias can enter a clustering pipeline at two points. First, at the representation level: node representations may encode group membership even when the protected attribute is removed from the input, because node features and graph structure act as proxies for it [8, 9]. In message-passing graph neural networks, aggregation over neighborhoods dominated by one group has been shown to amplify this signal [10, 11]. Similarly, graph transformers aggregate information through attention [12, 13, 14], and they are exposed to the same effect in a more flexible form: if attention concentrates on nodes of the same group, each representation becomes a summary of its own group. Moreover, at the assignment level, clusters can be demographically imbalanced even when the representations are reasonable; this is the level addressed by most classical fair clustering methods [15, 6, 16].
Figure 1 illustrates both these levels concretely on a small graph with 45 nodes and depicts why balancing cluster assignments alone may be insufficient. In this toy graph, the protected groups are mixed within the communities, but group-correlated features draw attention toward same-group nodes and pull clusters away from the communities. Enforcing group proportions on the assignments balances the clusters while disrupting their community structure. Rebalancing attention alongside assignment-level fairness yields clusters that are both balanced and structurally cohesive.
Figure 1. Why fairness is needed in both attention and assignments. Toy graph with 45 nodes, three communities, and two protected groups mixed within each community. Colours denote clusters, shapes denote groups, and numbers give the group counts (triangles:circles) of each cluster. Spectral coordinates and a noisy group-proxy feature feed one attention layer, whose representations are clustered by -means (). (a) Same-group attention (nCGAR = 0.14) splits the clusters by group. (b) Enforcing the population group shares on the same representations balances the clusters but fragments the communities. (c) Replacing the attention by the fixed point of the CGAR target (Eq. (5); nCGAR = 0.97), the attention toward which FairPGT’s self-distillation drives its encoder, and applying the same group shares yields clusters that are both balanced and cohesive. Panels (b) and (c) isolate the two levels by direct intervention, so that their effects can be seen without training; the outcome is the same for attention temperatures 0.3, 0.5, and 1.0.
Two observations guide our design. First, attention and assignments are separate entry points for group information, and fixing one does not explicitly fix the other: with a fixed encoder, fair assignments have to work against biased representations, as in panel (b), and we show in § 4.3 that an encoder trained with assignment-level fairness alone learns attention biased toward the other group, while neutral attention alone leaves the clusters unfair. Second, same-group attention has to be judged relative to the group composition of the attended nodes, because even group-agnostic attention gives more total mass to the larger group.
Existing methods cover parts of this picture. On the clustering side, fair clustering methods impose proportionality or individual-fairness constraints in spectral formulations [16, 17, 18, 19], or they add parity, adversarial, and contrastive regularizations to deep clustering models to remove protected information from learned representations [20, 21, 22]. In addition, our previous factorization-based models made the fairness–utility trade-off explicit at the assignment level [7, 23]. However, all of these methods act on the assignments or on the learned representations, and none of their encoders uses attention, so the group dependence of attention is neither measured nor controlled. In parallel, fair graph learning has developed adversarial, counterfactual, and graph-editing methods to debias graph neural network representations [24, 25, 26, 27, 28, 29], but mostly for supervised node classification. Closer to our setting, graph transformers have been used for attributed graph clustering, though without fairness considerations [30], while the two recent fair graph transformers of Luo et al., FairGT [31] and FairGP [32], still target supervised node classification: FairGT builds fairness-aware structural and multi-hop encodings, and FairGP restricts attention to graph partitions and removes attention across them. Consequently, no existing method measures and controls the group dependence of attention in unsupervised graph clustering. Finally, scalability is a further obstacle: full attention costs per layer, which is prohibitive on the larger graphs of fair graph learning benchmarks.
To address these gaps, we propose FairPGT (Fair Partitioned Graph Transformer), a graph transformer for fair unsupervised graph clustering that acts on both levels. Its central idea is that fair clusters and and balanced attention are two separate goals, and that a fair clustering method should reach both: clusters with the group shares of the population, produced by an encoder whose attention is balanced across groups. For scalability, attention is computed within METIS partitions, and routing tokens exchange information across partitions, which reduces the cost of attention by a factor of , the number of partitions. At the encoder level, we measure the group dependence of attention with a Cross-Group Attention Ratio (CGAR), normalized by the group composition of each partition so that a value of 1 corresponds to group-agnostic attention. The encoder is trained to keep this ratio close to 1 through self-distillation: at every training step, its current attention is rebalanced across groups and used as a target for the attention itself. The protected attribute therefore acts only as a training-time regularizer, and the transformer never takes it as input. At the assignment level, a DEC-style clustering head [33] is trained toward a graph-aware target with modularity-based structural guidance, together with a group-fairness term and an information term that keeps the assignments informative. Our main contributions can be listed as follows:
We propose FairPGT, a partitioned graph transformer for unsupervised clustering that restricts attention to METIS partitions, connects them with routing tokens, and clusters with a graph-aware self-training target. Partitioning divides the quadratic cost of attention by the number of partitions and, in practice, reduces peak memory by an order of magnitude (§ 3).
We introduce two complementary fairness terms: an assignment-level term that makes the clusters independent of the protected attribute, and an attention-level self-distillation term built on nCGAR, a normalized cross-group attention ratio that also serves as a diagnostic of the trained encoder. We prove that the nCGAR correction moves the ratio toward neutrality and give the condition under which it does not overshoot, and we bound how far the graph-aware target can depart from the DEC target (§ 3.3).
We conduct a controlled study on stochastic block models in which the alignment between communities and groups is varied, with an information-theoretic bound on the NMI of any exactly fair clustering at full alignment. FairPGT stays fair at every alignment and reaches 97% of the bound (§ 4.3).
We benchmark 14 methods on seven graphs of up to 67k nodes, with binary and four-group protected attributes, under one label-free protocol (fixed hyperparameters, last-epoch selection, collapse detection). FairPGT achieves the best NMI and the best statistical parity on the three largest graphs.
The remainder of the paper is organized as follows. § 2 reviews related work. § 3 presents the proposed FairPGT model and its theoretical properties. § 4 reports the experimental results and discussions, and § 5 concludes the paper.
Related Work
To position our work within the existing literature, we review three main research directions, as summarized in Table 1: deep graph clustering and graph transformers, fair clustering, and fairness in deep graph learning.
| Method | Venue | Task | Unsup. | Assign. | Repr. | Attn. | Groups | Encoder | Key idea |
| Deep graph clustering (fairness-agnostic) | |||||||||
| DMoN [34] | JMLR’23 | Clust. | ✓ | – | GNN | Differentiable modularity | |||
| SDCN [35] | WWW’20 | Clust. | ✓ | – | AE+GCN | AE–GCN fusion, DEC self-training | |||
| CCGC [36] | AAAI’23 | Clust. | ✓ | – | Contr. MLP | Cluster-guided positives and negatives | |||
| SCGC [5] | TNNLS’24 | Clust. | ✓ | – | Contr. MLP | Low-pass filter, cross-view consistency | |||
| DinkNet [37] | ICML’23 | Clust. | ✓ | – | GNN | Cluster dilation and shrink | |||
| DiffPool [38] | NeurIPS’18 | Pooling | ✗ | – | GNN | Hierarchical differentiable pooling | |||
| MinCutPool [39] | ICML’20 | Pooling | ✓ | – | GNN | Relaxed normalized min-cut | |||
| Fair clustering: classical, spectral, and factorization | |||||||||
| Fairlets [15] | NeurIPS’17 | Clust.* | ✓ | ✓ | 2 | – | Fair micro-clusters, -center/median | ||
| Fair SC [16] | ICML’19 | Clust. | ✓ | ✓ | Spectral | Proportionality constraint | |||
| sFairSC [18] | AISTATS’23 | Clust. | ✓ | ✓ | Spectral | Scalable fair spectral clustering | |||
| iFairSC [17] | NeurIPS’22 | Clust. | ✓ | indiv. | – | Spectral | Representation-graph constraint | ||
| iFairNMTF [7] | PAKDD’24 | Clust. | ✓ | indiv. | NMF | Contrastive individual-fair NMTF | |||
| DFNMF [23] | BigData’25 | Clust. | ✓ | ✓ | Deep NMF | Statistical-parity regularized deep NMF | |||
| Fair deep graph clustering and fair graph transformers | |||||||||
| Mod.-fair DMoN [40] | ICDM’25 | Clust. | ✓ | ✓ | 2 | GNN | Group-modularity terms in DMoN | ||
| FairGC [21] | AAAI’26 | Clust. | ✓ | indiv. | ✓ | 2 | Contr. MLP | Adversarial and covariance debiasing | |
| FairGT [31] | IJCAI’24 | Class. | ✗ | ✓ | 2 | Hop-token attn | -aware hop aggregation, eigenvector encodings | ||
| FairGP [32] | AAAI’25 | Class. | ✗ | ✓ | – | Part. attn | No attention across partitions | ||
| FairPGT (ours) | – | Clust. | ✓ | ✓ | ✓ | Part. attn | Routing tokens, nCGAR attention self-distillation |
Table 1. Related methods. Task: Clust. = node clustering (*: clustering of points without a graph), Class. = node classification. Unsup.: trained without class labels. Fairness acts on the cluster assignments (Assign.), on learned representations (Repr.), or on attention (Attn.); indiv. = individual fairness. Groups: number of protected groups the method is defined for (–: groups not used by the method). Encoder: AE = autoencoder, Contr. = contrastive, Part. attn = attention within graph partitions, Hop-token attn = attention over a node’s multi-hop tokens. FairPGT uses the protected attribute only in its training objective, never as a model input.
Deep graph clustering and graph transformers
Classical community detection optimizes structural criteria such as modularity [2, 1]. Building on this, deep graph clustering models combine representation learning with clustering, through graph autoencoders [41, 35], differentiable modularity [34], differentiable pooling [38, 39], contrastive objectives [36, 5], or cluster dilation and shrinkage on large graphs [37]. These methods, however, do not consider protected attributes, and their encoders are GNNs or MLPs. Graph transformers, in turn, replace fixed neighborhood aggregation by attention over sets of nodes, using structural or positional encodings to inject graph information [12, 13, 14], and tokenized designs scale them to large graphs [42]. For attributed graph clustering in particular, the work of [30] fuses a graph-transformer autoencoder with a feature autoencoder whose embeddings are adversarially matched to a prior distribution, and train the fused embeddings with a DEC-style self-supervised objective; its adversarial component regularizes the embedding distribution and does not involve protected attributes. In short, these architectures are designed for clustering or prediction quality alone, and how attention carries group information into clusters has not yet been studied.
Fair clustering
Early fair clustering enforces demographic balance in each cluster through fairlets [15] or constrained -clustering [6], while related formulations constrain the group membership of the selected centers instead [43]. Fair spectral clustering carries the same idea to graphs by adding group-proportionality constraints to the spectral relaxation [16, 18, 19]. Beyond groups, individual fairness requires similar individuals to be treated similarly [8, 44], and has been formulated for spectral clustering through an individual-level constraint encoded by a representation graph [17]. Along the same lines, our previous factorization-based models regularize the cluster memberships for statistical parity [23] and for contrastive individual fairness [7]. In community detection, finally, fairness has been defined through the modularity of each group [45] and through the balance of group proportions combined with modularity [46]. What all of these methods share is that fairness is imposed on the clustering itself, through constraints, pre- or post-processing, or regularization of the assignments, while the representation is either the input data or a spectral or factorization embedding of it. Consequently, none of them learns an unbiased message-passing or attention encoder, and bias introduced by such an encoder lies outside their scope.
Fairness in deep graph learning
Fair graph learning has mainly targeted node classification. Among the first approaches, FairGNN debiases representations adversarially [24], NIFTY uses counterfactual augmentation [25], and EDITS edits the graph and node features before training [26]. Analyses of message passing have since shown that aggregation over neighborhoods dominated by one protected group can amplify group information in node representations [10, 11]. Accordingly, several methods intervene inside the model rather than on its outputs: FairGAT designs fairness-aware attention for graph attention networks [47], FMP adds a demographic-parity term to an optimization view of message passing [10], FS-GNN jointly sparsifies edges and weights under a fairness penalty [29], and FairNCI fuses estimated counterfactual-neighbor representations into each message-passing layer [27]. Fairness has also been treated jointly with privacy, by combining ranking-based individual fairness with adversarial protection against protected-attribute inference [28]. More recently, two graph transformers have addressed fairness, again for node classification: FairGT builds fairness-aware structural and multi-hop feature encodings [31], and FairGP partitions the graph and removes attention between partitions [32]. Notably, all of these methods are trained for node classification, and some, such as FS-GNN and FairNCI, even use class labels in the fairness mechanism itself.
Deep fair clustering, in contrast, debiases representations or assignments without labels. In the vision domain, DFC filters protected attributes out of learned representations [20], and for multi-view data, AFMVC removes them from fused representations with a gradient-reversal discriminator while aligning view-specific soft assignments to a consensus -means target [22]. On graphs, FairGC combines cross-view contrastive learning with adversarial and covariance-based debiasing for group and individual fairness [21], and modularity-fair deep community detection adds group-modularity terms to the DMoN objective [40]. Yet none of their encoders uses attention. Taken together, attention-level fairness has so far been studied only in supervised graph attention networks and graph transformers, whereas fair clustering corrects the representations and assignments of attention-free encoders; the two lines have not met.
Positioning our work. FairPGT brings fairness into the attention of a graph transformer for unsupervised clustering, a combination that, to our knowledge, no previous method addresses (Table 1). At its core is a new measure of attention bias, the normalized cross-group attention ratio (nCGAR). Unlike a raw count of attention mass, nCGAR compares cross-group and same-group attention against what the group composition of each partition alone would produce. It therefore separates a genuine preference for one’s own group from the mere fact that a larger group receives more attention, and it reads directly: 1 means group-neutral attention, values below 1 mean same-group preference, and values above 1 mean over-correction toward the other group. Because it needs no labels, nCGAR serves both as a training signal, through attention self-distillation, and as an audit of any trained encoder. As in FairGP, attention is computed within METIS partitions; unlike FairGP, however, information still flows across partitions through routing tokens instead of being cut. Above all, FairPGT is the first method to treat fairness at both levels at once: nCGAR self-distillation keeps the encoder group-neutral, while a mutual-information term makes the clusters independent of the protected attribute, and a graph-aware self-training target keeps them aligned with the community structure. As our experiments show, the two fairness levels are complementary, since each alone leaves the other unsolved. Throughout, the protected attribute enters only the training objective and is never an input to the transformer.
FairPGT: Partitioned Graph Transformers for Dual-Level Fair Clustering
Problem formulation. Let be an undirected attributed graph with nodes, adjacency matrix , node degrees , and normalized Laplacian , where . Each node carries a feature vector , collected as , and a protected attribute , collected as . Given , our goal is to learn a model that maps to soft cluster assignments , with and , where is the number of clusters, such that the clusters are both structurally coherent and demographically fair. Beyond fair clusters, we also ask that the encoder’s attention be balanced across groups, a requirement we make precise through the attention of the model in § 3.1. We work with soft assignments because they allow clustering and fairness objectives to be optimized jointly by gradient descent, which has proven effective in deep clustering [33, 34]; the final hard labels used for evaluation are then . Importantly, the protected attributes are not part of the feature matrix : they are provided separately as and enter only the training objective, through the attention self-distillation term and the group-fairness term (§ 3.1 and § 3.2). The trained model therefore computes cluster assignments from alone.
Framework overview. Figure 2 illustrates the FairPGT pipeline, with algorithmic details in Algorithm 1 and Algorithm 2. The framework first augments the node features with structural encodings, then processes them through partitioned transformer layers whose routing tokens carry context across partitions (§ 3.1), and finally produces soft cluster assignments (§ 3.2). These assignments are trained toward a graph-aware self-training target, together with an information term that keeps them confident and non-degenerate. On top of this, fairness enters at two levels. At the encoder level, an nCGAR target (Definition 1) rebalances the attention within each partition, and the encoder learns to reproduce it through self-distillation; at the assignment level, a mutual-information term promotes statistical parity across clusters. Notably, both fairness terms belong to the training objective, so the protected attribute is never an input of the model, and inference uses alone.
Figure 2. FairPGT Pipeline: (a) Structural encodings augment the node features, partitioned transformer layers produce embeddings, and a DEC-style head outputs soft assignments . The objective combines two quality terms, the graph-aware target and the information term, with two fairness terms: on the assignments and , built from the nCGAR target on the local attention. The protected attribute (red column) is not an input to the encoder; it enters only the fairness terms during training. (b) Fair attention module: local attention within METIS partitions, routing tokens that carry context across partitions, and a learned scalar gate that fuses the two.
FairPGT Encoder
The encoder maps the augmented input to node representations through transformer layers. Each layer combines three components: (i) partition-local attention, which keeps the cost of attention manageable; (ii) routing tokens, which carry context across partitions; and (iii) a learned gate that fuses local and global information. In addition, during training, the local attention is guided toward group-neutrality by a target built from our normalized cross-group attention ratio (nCGAR). Throughout, MHA denotes standard multi-head attention, FFN a position-wise feed-forward network, and LN layer normalization. We now describe each component in turn.
Structural encodings. Since attention by itself is blind to graph structure, we first augment the node features with lightweight descriptors derived from the graph. Let denote the eigenpairs of the Laplacian . We compute the normalized degree and the first nontrivial Laplacian eigenvectors . The initial token matrix
thus combines node attributes with spectral position information and degree-based centrality. Before training, each column of is standardized to zero mean and unit variance, so that attributes, spectral encodings, and degrees enter on a comparable scale. Since eigenvectors are defined only up to sign, we fix the sign of each so that its largest-magnitude entry is positive, and we let the learned input projection absorb the remaining ambiguity for repeated eigenvalues.
Partitioned attention with routing. Full attention over all nodes costs per layer, which quickly becomes prohibitive on large graphs. To scale beyond it, we partition the graph into disjoint blocks using METIS [48], a widely used multilevel partitioning algorithm that scales to large graphs and keeps densely connected nodes together. We set , so that partitions hold at most about 2,500 nodes; the resulting complexity reduction is analyzed in § 3.4, and § 4.5 studies other values of . Within each partition and for every layer , local multi-head attention is then computed from the projected representations as
Attention is computed per head; we omit the head index for readability, and all attention-level quantities below are likewise computed per head. Moreover, the diagonal of is masked before the softmax, so that a node attends only to the other nodes of its partition, while its own state enters through the residual connection in Eq. (3).
Partitioning alone, however, limits the receptive field to within-partition nodes and severs the long-range communication that motivates graph transformers in the first place. To restore global context, we introduce one routing token per partition, following the inducing-point intuition of Set Transformer [49]. Specifically, at layer each partition is summarized by the mean of its normalized states, . The resulting set of tokens exchanges information through global self-attention with a residual connection, , and each node then absorbs global context through cross-attention to the tokens, . Since there are only tokens, this global exchange adds little cost. Finally, local and global outputs are combined through a learned gate, followed by a feed-forward block, each with a residual connection:
where , is the output projection, and is a learned scalar that controls the local–global trade-off, so that each layer decides for itself how much global context it needs. Algorithm 2 summarizes one encoder layer. Importantly, the layer does not take the protected attributes as input; it only returns the partition attention matrices, from which the CGAR targets are built during training (Algorithm 1).
Algorithm 1 FairPGT: training and inference. Steps marked ▶ are the only ones that use the protected attribute ; inference uses alone.
Input: Graph , features , protected attribute (training only), number of clusters ; weights ; CGAR step and tolerance ; target interval ; epochs
Output: Trained model ; soft assignments and cluster labels
Preprocessing (once)
1: Build the input tokens from features, Laplacian eigenvectors, and degrees, standardized per column // Eq. (1)
2: Partition the graph with METIS into blocks
3: ▶ Record the group composition of every partition with at least two groups // Eq. (4)
4: Initialize , and place the centers by -means on the initial embeddings
Training
5: for do
6: Encode: and attention from // Algorithm 2
7: Assign: project and compute the soft assignments // Eq. (7)
8: if then
9: Refresh: recompute the graph-aware target and hold it fixed // Eqs. (8)–(10)
10: end if
11: ▶ Rebalance: build the CGAR target for every layer, head, and mixed partition, held fixed // Eq. (5)
12: ▶ Score: // Eq. (13)
13: Update: one Adam step on the encoder, the gates, , and the centers
14: end for
Inference
15: Encode and assign as in training:
16: for every node
17: return , ,
nCGAR-guided fair attention. While partitioning limits how far bias can propagate, attention within a partition can still concentrate on same-group nodes. This matters because, when a node’s representation is aggregated mostly from nodes of its own protected group, group membership becomes easier to recover from the representation, and clusters formed on such representations tend to follow group boundaries. The same effect has been shown for message passing on graphs with protected-attribute homophily [10, 11], and fairness-aware graph transformers have likewise shown that attention can carry protected information [31, 32]. To measure this effect, we introduce the Cross-Group Attention Ratio (CGAR), which compares the attention mass on cross-group and within-group node pairs inside a partition, and its normalized form, nCGAR, which relates this ratio to what the group composition of the partition alone would produce. With this measure in hand, FairPGT addresses group dependence directly in the encoder, complementing the assignment-level fairness term of § 3.2.
Definition 1 (Cross-Group Attention Ratio). For partition at layer with attention
matrix , the CGAR and its normalized form nCGAR are
where is the number of nodes of group in , , and and are the numbers of ordered cross-group and within-group pairs of distinct nodes in . CGAR is defined for partitions that contain at least two groups and at least one within-group pair.
To see why the normalization is needed, consider group-agnostic attention, for example uniform attention within the partition. Each cross-group pair then receives on average as much attention as each within-group pair, so nCGAR, whereas the raw ratio equals , which is close to for equally sized groups and depends on the composition of the partition otherwise. Accordingly, nCGAR indicates group-homophilous attention, concentrated on same-group pairs beyond what the composition explains, and nCGAR indicates group-heterophilous attention, an over-correction toward the other group. Because it is normalized, nCGAR can be compared across partitions, layers, heads, and datasets, and because it needs no labels, it serves both as a training signal and as an audit of a trained encoder (§ 4.3). Naturally, nCGAR is defined only for partitions that contain at least two groups. Moreover, nCGAR pools the attention of all nodes in the partition: it measures whether cross-group and within-group pairs receive balanced attention overall. A value of 1 can therefore also arise when one group attends across groups more than the composition explains and another group less, a case we examine in § 4.3. Throughout, we call attention with nCGAR group-neutral in this aggregate sense.
We turn nCGAR into a training signal through a simple correction. Whenever nCGAR, we multiplicatively boost the cross-group attention entries; conversely, whenever nCGAR, we boost the within-group entries. The result serves as a target for the encoder’s attention:
after which row renormalization restores stochasticity. As with the DEC target in § 3.2, the target is recomputed from the current attention at every training step and treated as a constant, i.e., no gradient flows through it. The encoder’s attention is then aligned with this target through
where is row of the attention matrix of partition at layer , and collects all rows over layers, partitions with at least two groups, and heads. In the spirit of self-distillation [50], the encoder thus learns to produce group-neutral attention by itself, by distilling a rebalanced version of its own attention. The tolerance leaves small deviations from the composition baseline unpenalized. On the theoretical side, we prove in Theorem 1 that the target always moves nCGAR toward the tolerance band , and in Proposition 1 that minimizing moves the encoder’s own attention in the same direction, with once every partition lies inside the band. Finally, since the corrected attention appears only in the loss, the forward pass in Eq. (3) uses during both training and inference, and the protected attributes are never required at inference.
Fairness-aware clustering
Soft assignments. On top of the encoder, a clustering head turns node representations into soft cluster assignments. Let denote the final encoder output and its low-dimensional projection. We adopt the DEC clustering head [33], which has become a standard component of deep graph clustering thanks to its differentiability and its compatibility with self-training objectives [35, 34]. Given learnable centers , initialized by -means on the initial embeddings, the row-stochastic soft assignment matrix is computed with a Student’s kernel as
Graph-aware target. Standard DEC sharpens the assignments using only and thus ignores the graph. To bring the community structure into the target, we first score each node–cluster pair by its modularity gain,
where is the number of edges and the neighborhood of node . The first term measures how strongly the neighbors of belong to cluster , and the second subtracts what a degree-preserving random graph would produce, so that means that the neighbors of node favor cluster beyond random connectivity. To keep these scores on a bounded scale, we center them and apply a parameter-free nonlinearity,
Under exact row-stochasticity of the gains already satisfy , so the centering merely guards against finite-precision drift during training. The graph-aware target then combines DEC confidence with this structural guidance,
and the clustering loss is . Following DEC, is held fixed during back-propagation and recomputed every training steps. Intuitively, when the graph structure is informative, sharpens cluster preferences along local modularity gains; when it is weak or homogeneous, the target reduces to standard DEC. Moreover, because is bounded, the structural guidance can tip close calls but cannot overturn confident DEC preferences: Theorem 2 shows that always stays within a factor of the DEC target.
Group fairness. Next, we turn to the fairness of the assignments. Let be the global proportion of group , and let be its soft proportion in cluster . We penalize deviations from statistical parity by the mutual information between cluster and group under the soft assignments,
which is zero exactly when every cluster has the global group proportions. Weighting each cluster by its expected size keeps small clusters from dominating the penalty. A small constant is added to all proportions for numerical stability.
Informative assignments. Statistical parity alone, however, admits degenerate solutions. For example, if all nodes share the same assignment vector, every cluster inherits exactly the global group proportions, so , although the clustering carries no structure at all. To exclude such solutions, we additionally require the assignments to be informative about the nodes. Inspired by the information-maximization view of discriminative clustering [51], we minimize the negative mutual information between a node and its cluster under the soft assignments,
where is the Shannon entropy (natural logarithm) of a distribution over the clusters, is the assignment vector of node , and collects the expected cluster proportions of Eq. (11). The two terms pull in complementary directions: the first is small when each node is assigned confidently to one cluster, and the second, which enters with a negative sign, is large when the clusters have similar sizes. Since the entropy is concave, always lies between and . It reaches its minimum only when every node is assigned with certainty and all clusters have equal size, and its maximum exactly when all nodes share the same assignment vector, that is, precisely for the degenerate solutions that satisfy trivially. In short, and together serve clustering quality: the former aligns the clusters with the community structure, and the latter keeps the assignments confident and the clusters non-degenerate. Neither involves the protected attribute; fairness is the role of , the mutual information between clusters and groups, and of .
Final objective. Putting the pieces together, FairPGT minimizes
in which two terms serve clustering quality and two serve fairness: aligns the clusters with the community structure and keeps them informative, while makes the clusters independent of the protected attribute and keeps the encoder’s attention balanced across groups. Accordingly, and control the fairness–utility trade-off at the assignment and attention levels, and sets the strength of the information term; in addition, and set the step size and tolerance of the CGAR target, and the gates are learned end-to-end.
Training and inference. Algorithm 1 brings all components together. Structural encodings, partitions, and group compositions are computed once, before training. At each training step, the encoder computes its attention and the soft assignments from alone; the CGAR target and the graph-aware target are then built from these outputs and held fixed, and all parameters are updated on Eq. (13). Notably, the protected attributes enter at only two places, the CGAR target and , both of which belong to the training objective. At inference, the trained model therefore computes from alone. One encoder layer is detailed in Algorithm 2.
Algorithm 2 FairPGT encoder layer . The layer never receives the protected attribute; it returns its attention matrices so that the CGAR targets can be built during training.
Input: States , partitions
Output: States and partition attention matrices
Normalize the states: // shared by both branches Local branch: attention within partitions
for each partition (in parallel) do
Compute the self-masked attention from // Eq. (2), per head
Aggregate the values:
end for Global branch: routing tokens
Summarize each partition by a token , the mean of its normalized states
Let the tokens exchange information by self-attention, giving
Broadcast: every node attends to the tokens, giving its global context Fusion
Mix local and global outputs with the learned gate , then apply the feed-forward block // Eq. (3)
return ,
Theoretical Guarantees
We now show that the two targets that drive training behave as intended: the CGAR target moves attention toward neutrality without overshooting, its loss pulls the encoder’s own attention in the same direction, and the graph-aware target refines the DEC target without overriding it. All proofs are given in § 3.5.
Theorem 1 (CGAR target). Consider one head and one partition with at least two groups, attention , and target from Eq. (5). Let and be the cross-group mass of row before and after the correction.
(i) If , then for every row, with strict inequality whenever , and .
(ii) If , then for every row, with strict inequality whenever , and .
(iii) If , the target does not overshoot: whenever the correction is active, is strictly closer to the band than .
Parts (i) and (ii) show that one correction step always moves nCGAR in the right direction, by at most a factor . Part (iii) is needed because a large could push nCGAR from just below the band to far above it; the condition holds for any , including our setting .
The theorem concerns the target, whereas training changes the encoder. The next result connects the two.
Proposition 1 (Attention alignment). (i) if and only if nCGAR for every layer, head, and partition with at least two groups.
(ii) Let be a row with logits , and with the target held fixed. Then , and if the target boosts cross-group entries, the gradient step changes at rate
with strict inequality whenever ; if the target boosts within-group entries, the rate is the same bracket times .
In words, part (i) shows that the loss vanishes exactly when the encoder’s attention is already within the band, and part (ii) shows that descending moves the cross-group mass of each row in the same direction as the target. Part (ii) holds for the logits of each row; since all rows share the projections and , a parameter update need not move every row at once. We therefore measure the nCGAR of the trained encoder directly in § 4.
Finally, we turn to the clustering side and characterize how the graph-aware target relates to the standard DEC target.
Theorem 2 (Graph-aware target). Let be the standard DEC target. For every node and clusters , the target of Eq. (10) satisfies:
(i) Bounded modulation: .
(ii) Agreement: . Hence, if and , then ; and can reverse a DEC preference for over only if and .
(iii) Reduction to DEC: if is the same for all , then .
The graph structure therefore reweights the DEC target but cannot override it: it reinforces the DEC preference when the two agree, it can overturn a weak preference in favor of the cluster preferred by the node’s neighbors, and it cannot reverse a confident one, with odds of at least . When the modularity gains of a node do not distinguish between clusters, the target is exactly the DEC target.
Computational Complexity
Having established what the training targets do, we turn to what the model costs. Throughout, denotes the width of the encoder with heads, and the input dimension of Eq. (1) and the dimension of the clustering projection.
Proposition 2 (Complexity of FairPGT). Let the encoder have layers of width , and let the partitions be balanced.
(i) One encoder layer costs time.
(ii) One full-batch training step costs time and memory for activations.
(iii) Inference has the time cost of (ii) without the term and needs memory, since attention matrices can be released layer by layer.
For , one layer costs time, compared to for global attention.
In (i), the four terms are local attention within partitions of size , the broadcast from the routing tokens to all nodes, self-attention among the routing tokens, and the linear projections and feed-forward network, which any transformer shares. In (ii), the remaining terms are the input embedding, the clustering projection, the DEC assignments (Eq. (7)), and the graph-aware target (Eq. (10)), which needs for sparse neighbor aggregation and never forms dense matrices. In contrast, the CGAR target (Eq. (5)) and (Eq. (6)) reuse the partition attention matrices that the forward pass has already computed, while and cost ; none of them changes the order of the cost, and none is computed at inference. METIS partitioning and the spectral encodings are computed once, before training.
In practice, our default keeps partitions at about nodes, so the local-attention term becomes , linear in . The broadcast term still grows quadratically, but with the small factor : on Pokec-n () it is about 90 times smaller than the local-attention term. Figure 8 confirms that memory follows the local-attention term: peak memory falls close to , until the per-node terms dominate, from 11.9 GB to 0.75 GB on LastFM as grows from 1 to 64, while the time per epoch falls until fixed per-layer costs dominate.
Figure 8. Effect of the number of METIS partitions (one seed, 50 epochs). Dashed lines in (a) show the ideal scaling from each dataset’s first feasible point; crosses mark runs that exceed the GPU memory (Facebook and Credit at , Pokec at ).
Proofs of Theoretical Claims
Proof of Theorem 1 (CGAR Target)
Setup. Fix a layer, a head, and a partition with nodes and at least two groups; may take any number of values. Let be the row-stochastic attention of this partition, whose diagonal is masked, and write if and if and . The cross-group mass of row is , and its within-group mass is . Softmax entries outside the diagonal are positive and , so , with exactly when node has no other node of its group in the partition. Such rows are left unchanged by the correction, since all their nonzero entries are scaled by the same factor. Because CGAR is defined only when the partition contains within-group pairs, at least one row has . Summing over rows,
Since depends only on the group composition of , it suffices to prove all statements for CGAR.
Proof. (i) Correction from below. The target multiplies the cross-group entries of each row by and renormalizes by . Hence
with equality only for rows with . Since at least one row has , ; and because and is strictly increasing on , this gives .
For the upper bound, let . Then and , so
It remains to show . The difference of the two sides is
where the equality follows by adding the expression to itself with and exchanged, and the inequality holds because is decreasing in . Therefore , with equality when all are equal.
(ii) Correction from above. The within-group entries are multiplied by , so and . Exchanging the roles of and in (i) gives , which is the claim.
(iii) No overshoot. Let and . The condition is equivalent to both and . If , then by (i) : moves toward the band and does not leave it on the other side, so its distance to the band, , is strictly smaller than . The case is symmetric by (ii). If , the target equals .
Remark 1 (Repeated correction). Applying the correction times multiplies the cross-group entries by before a single renormalization, so each and as (and in the symmetric case). Starting outside the band, therefore reaches the band after finitely many steps, and by (iii) it does not jump over it. This is the fixed point used in the toy example (Figure 1). FairPGT applies the correction once per training step.
Proof of Proposition 1 (Attention Alignment)
Proof. (i) Each term of is a KL divergence and is therefore nonnegative, and it is zero if and only if . Consider a layer, head, and partition with at least two groups. If its nCGAR lies in the band, the target equals the attention and all its rows contribute zero. Otherwise, by Theorem 1(i)–(ii), for every row with , and at least one such row exists; hence for that row, and it contributes a positive term. Partitions with a single group are not in .
(ii) Write and . Since is constant and sums to one,
The gradient step changes the logits by . The cross-group mass has partial derivatives , so
When cross-group entries are boosted, the target of Theorem 1(i) gives for and for . Substituting gives the stated rate, which is positive since and both sums contain positive terms. When within-group entries are boosted, for and for , which gives the same bracket with factor .
Proof of Theorem 2 (Graph-Aware Target)
Proof. Let , so that and . Student-t assignments are positive, so . Dividing the numerator and denominator of Eq. (10) by gives
(i) The denominator of Eq. (15) is a convex combination of values in and therefore lies in . Hence .
(ii) The ratio follows from Eq. (15), since the denominator does not depend on . Centering subtracts the same from and , and is strictly increasing, so has the sign of and lies in . If and , both factors of the ratio are at least 1 and the second is larger than 1, so . If but , then , and the exponent is positive, so .
(iii) If is the same for all , then and for all , and Eq. (15) reduces to .
Remark 2 (Centering). For row-stochastic , , using . Hence and ; the explicit centering only guards against numerical drift. In the case of (iii), all gains of node are therefore zero.
Proof of Proposition 2 (Complexity of FairPGT)
We count multiply–add operations of the forward pass; the backward pass has the same order. Partitions are balanced, , and .
Proof. (i) One encoder layer. Projections and feed-forward network: the query, key, value, and output projections and the two-layer feed-forward network with hidden width cost . Local attention: in each partition and head, and the product with cost ; over heads and partitions, this gives . Routing tokens: mean pooling into tokens costs ; self-attention among the tokens costs , plus for their projections, which is dominated by ; and the broadcast, in which each node attends to all tokens, costs . Gate, residuals, and normalization: these cost . Summing all terms gives (i).
(ii) Training step. The input embedding costs , and the layers cost times (i). The projection costs , and the DEC assignments cost . In Eq. (8), the neighbor term for all is a sparse–dense product costing , and the null-model term needs the sums only once, so it costs ; centering, tanh, and the normalization in Eq. (10) also cost . The losses , , and each cost ; for , each node adds its row of to the column of its group. The CGAR target and need two passes over each partition attention matrix, per layer, which is dominated by local attention since . For memory, back-propagation stores the partition attention matrices, per layer, the broadcast attention, per layer, and the node activations, per layer, while the graph and the matrices and need .
(iii) Inference. The encoder, projection, and assignments are computed as in (ii), but the targets and the losses are not. Without back-propagation, the attention matrices of a layer can be released before the next layer is computed, so memory is .
Choice of . Balancing the local-attention term against the broadcast term gives , for which both are and the token self-attention is . One layer then costs , compared to for global attention.
Example. On Pokec-n (), our default gives partitions of about 2,470 nodes, so the partition attention matrices of one head in one layer hold about entries, compared to for global attention, a 27× reduction.
Experiments
Our experiments are designed to test the two main claims of this paper: that a graph transformer can cluster fairly without giving up the structure that is unrelated to the protected groups, and that its attention can be kept group-neutral at the same time. To this end, we organize them around four questions. Q1: How does FairPGT trade clustering quality against group fairness, compared with fairness-agnostic and fairness-aware baselines? Q2: How does the price of fairness depend on the alignment between communities and protected groups, and does the encoder stay group-neutral? Q3: Which components are responsible for the fairness, and which for the clustering quality (ablation)? Q4: What do partitioning and the fairness weight cost, and what do they buy (sensitivity and cost)?
Setup
Datasets. We use seven attributed graphs that span social, financial, and music-listening networks and range from 391 to 67,796 nodes (Table 2). Throughout, class labels are used only for evaluation, and the protected attribute is removed from the node features of every dataset, so that all methods are exposed to the same input; the only exception is FairGT, whose design requires it (see Baselines). NBA [24] connects basketball players who are linked on Twitter; the protected attribute is nationality (US or not), and the label is the salary class used by Dai and Wang [24], binarized as majority class versus the rest. Pokec-n and Pokec-z [52, 24] are two regional subgraphs of the Slovak social network Pokec. Here, the protected attribute is age in four groups (, 19–25, 26–35, ), so these two graphs test fairness beyond two groups; the label is the working field, binarized as majority field versus the rest. Profile attributes are one-hot encoded and reduced to 128 dimensions by truncated SVD, and isolated nodes are removed. German and Credit [53] are credit-scoring datasets, with gender and marital status as protected attributes and creditworthiness and default as labels. For Credit, we use the customer similarity graph of Agarwal et al. [25]; for German, we build a symmetric 10-nearest-neighbour graph with cosine similarity on the non-protected features (gender and age excluded). In both cases, edges therefore reflect feature similarity rather than observed interactions.
| Dataset | Maj. | CC | Protected attribute | Label | |||||||
| NBA | 391 | 10,416 | 95 | 2 | 2 | 73.7% | 0.73 | 0.51 | 1 | Nationality (US / non-US) | Salary class (majority vs. rest) |
| German | 1,000 | 7,156 | 39 | 2 | 2 | 69.0% | 0.78 | 0.64 | 1 | Gender | Good / bad credit |
| LastFM | 5,465 | 19,024 | 128 | 6 | 2 | 53.1% | 0.73 | 0.92 | 16 | Synthetic (feature -means) | Country (6) |
| 22,470 | 170,823 | 4,714 | 4 | 2 | 60.1% | 0.64 | 0.89 | 1 | Synthetic (feature -means) | Page type (4) | |
| Credit | 30,000 | 137,377 | 12 | 2 | 2 | 54.5% | 0.65 | 0.64 | 120 | Marital status | Default next month |
| Pokec-n | 66,569 | 517,047 | 128 | 2 | 4 | 46.2% | 0.58 | 0.75 | 226 | Age (4 bins) | Working field (majority vs. rest) |
| Pokec-z | 67,796 | 617,958 | 128 | 2 | 4 | 47.1% | 0.61 | 0.73 | 170 | Age (4 bins) | Working field (majority vs. rest) |
| SBM () | 2,000 | 11,925 | 32 | 4 | 2 | 50.0–69.7% | 0.56–0.82 | 0.73 | 1 | Planted, aligned by | Planted community |
Table 2. Dataset statistics. : nodes; : undirected edges; : feature dimension; : label classes (number of clusters); : protected groups; Maj.: share of the largest group; , : fraction of edges joining nodes of the same group and of the same class; CC: connected components.
LastFM [54] links music-platform users who follow each other; its features are the artists a user likes, reduced to 128 dimensions by truncated SVD, and its labels are the users’ countries, restricted to the six largest. Similarly, Facebook [55] links verified Facebook pages that like each other, with the page category (four classes) as label and keyword features from the page descriptions. Since neither graph has a demographic attribute, we construct a binary group by -means () on the node features. This makes the group a function of the features, which is the strongest proxy setting an encoder can face; moreover, edges also follow these groups ( and 0.64 in Table 2, against about 0.5 for groups unrelated to the edges).
Finally, for the controlled study of § 4.3, we generate attributed stochastic block models (SBMs) [56] with node features in the style of contextual SBMs [57], and with planted protected groups as in the block models used to analyse fair spectral clustering [16, 17]. Each graph has nodes, equal communities, and two groups. A node in community belongs to group with probability and otherwise follows the population share (minority 0.3), so the alignment runs from 0, where groups are independent of the communities, to 1, where every community is one group. Edges are eight times more likely within than across communities (mean degree 12), and the 32-dimensional features combine a community signal, a group proxy of equal strength, and Gaussian noise.
Baselines. The baselines cover the method families reviewed in § 2 (Table 1). As fairness-agnostic deep graph clustering methods, we use DMoN [34], SDCN [35], CCGC [36], SCGC [5], DinkNet [37], DiffPool [38], and MinCutPool [39]. As fair deep models, we use DMoN-SP, which adds a statistical-parity penalty to DMoN in the spirit of modularity-fair community detection [40]; FairGC [21]; and the fair graph transformers FairGT [31] and FairGP [32]. Finally, as fair spectral clustering, we use sFairSC, group-fair spectral clustering [16] in its scalable form [18], and iFairSC, individual-fair spectral clustering [17].
Some of these baselines needed adaptation, most of all FairGT and FairGP. Both were proposed for node classification and obtain fairness through their architectures rather than through a loss: FairGT feeds the protected attribute into its encodings, and FairGP removes attention across METIS partitions. We re-implement these mechanisms (for FairGT, with neighbourhood attention layers instead of hop-token sequences), attach a clustering head trained by DEC-style self-training [33], and add the statistical-parity penalty of DMoN-SP, so that both act as fairness-aware clustering methods; FairGT receives the protected attribute in training and at inference, as in the original. For CCGC, we use GCN encoders in place of its filtered-feature MLPs. For the spectral methods, sFairSC is computed on the regularized graph [58], the mean degree, because the leading eigenvectors of graphs with many connected components (LastFM, Credit, Pokec) are otherwise component indicators, and -means then returns a single cluster. iFairSC uses a symmetric 10-nearest-neighbour representation graph on the features, with the low-rank approximation of the original paper when the constraint is infeasible. Lastly, DMoN-SP uses a penalty weight of 0.1; at this weight it behaves almost like DMoN (Table 3), and we report it unchanged rather than tune it on labels. We do not compare with fairlets [15], which address -center and -median clustering of points without a graph, or with fair graph neural networks for node classification [24, 25, 26], which need labels for training.
| Deep graph clustering | Fair deep | Fair spectral | Ours | ||||||||||||
| DMoN | SDCN | CCGC | SCGC | DinkNet | DiffPool | MinCutPool | DMoN-SP | FairGC | FairGT | FairGP | sFairSC | iFairSC | FairPGT | ||
| NBA | NMI↑ | .086±.04 | .000±.00† | .036±.05† | .021±.03† | .000±.00† | .014±.03† | .109±.02 | .047±.05† | .004±.01 | .086±.02 | .016±.01† | .133±.00 | .000±.00 | .107±.04 |
| Δ↓ | .037±.04 | .000±.00† | .116±.10† | .255±.29† | .000±.00† | .058±.12† | .025±.03 | .079±.12† | .024±.02 | .036±.03 | .125±.05† | .011±.00 | .028±.00 | .016±.02 | |
| German | NMI↑ | .005±.00 | .004±.00 | .007±.01 | .012±.01 | .000±.00† | .001±.00 | .010±.01 | .005±.00 | .001±.00 | .005±.00 | .013±.02 | .000±.00 | .000±.00 | .002±.00 |
| Δ↓ | .090±.04 | .057±.04 | .061±.04 | .060±.06 | .000±.00† | .016±.02 | .108±.05 | .088±.04 | .023±.02 | .083±.05 | .055±.05 | .006±.00 | .038±.00 | .039±.02 | |
| LastFM | NMI↑ | .550±.03 | .405±.09† | .194±.04 | .216±.04 | .081±.12† | .207±.08† | .423±.02 | .547±.02 | .032±.01 | .321±.03 | .338±.03 | .296±.00 | .001±.00 | .289±.05 |
| Δ↓ | .399±.03 | .218±.10† | .309±.08 | .433±.09 | .515±.03† | .281±.04† | .436±.02 | .392±.03 | .088±.03 | .448±.04 | .387±.05 | .368±.00 | .029±.01 | .040±.03 | |
| NMI↑ | .196±.08 | .080±.18† | .054±.01 | .113±.05 | .053±.04 | .068±.04† | .195±.06 | .192±.08 | .010±.01 | .095±.04 | .085±.02 | .118±.00 | n/s | .057±.01 | |
| Δ↓ | .124±.06 | .025±.06† | .133±.04 | .204±.08 | .214±.11 | .329±.12† | .238±.06 | .110±.05 | .063±.02 | .519±.09 | .106±.03 | .468±.00 | n/s | .027±.01 | |
| Credit | NMI↑ | .010±.01 | .009±.00 | .013±.01 | .013±.01 | .012±.01 | .015±.01 | .008±.00 | .010±.01 | n/s | .022±.01 | .012±.01 | .002±.00† | n/s | .042±.05 |
| Δ↓ | .018±.00 | .014±.00 | .010±.00 | .024±.01 | .014±.01 | .012±.01 | .010±.00 | .018±.00 | n/s | .010±.00 | .013±.01 | .030±.00† | n/s | .003±.00 | |
| Pokec-n | NMI↑ | .001±.00 | .020±.00 | OOM | OOM | .011±.00† | n/s | n/s | .001±.00 | n/s | .072±.01 | .009±.01 | .003±.00 | n/s | .098±.01 |
| Δ↓ | .054±.00 | .118±.01 | OOM | OOM | .102±.03† | n/s | n/s | .053±.00 | n/s | .023±.01 | .093±.03 | .113±.00 | n/s | .006±.00 | |
| Pokec-z | NMI↑ | .001±.00 | .018±.00 | OOM | OOM | .015±.00† | n/s | n/s | .001±.00 | n/s | .062±.04 | .007±.01 | .001±.00 | n/s | .106±.01 |
| Δ↓ | .056±.01 | .145±.01 | OOM | OOM | .143±.02† | n/s | n/s | .057±.00 | n/s | .019±.01 | .075±.05 | .141±.00 | n/s | .005±.00 |
Table 3. Clustering quality (NMI) and group fairness () on seven benchmarks. Mean and standard deviation over five seeds. Best in bold and underlined, runner-up in underlined, among runs that did not collapse; †: collapsed (fewer than clusters used, or one cluster holding over 90% of the nodes, in at least half of the runs). n/s: not scalable, skipped (memory quadratic or cubic in ); OOM: out of GPU memory.
Protocol. Every method runs for 200 epochs with one fixed hyperparameter setting across all datasets, and no hyperparameter is tuned on labels. Likewise, we report the clustering at the last epoch, so that no label information is used for model selection. equals the number of label classes, and results are the mean and standard deviation over five seeds (three on the SBMs). Methods whose memory grows quadratically or cubically with are skipped above a size limit (DiffPool and MinCutPool above nodes, FairGC above , iFairSC above ) and marked n/s, while runs that exceed the GPU memory are marked OOM. Finally, we call a run collapsed if it uses fewer than clusters or puts more than 90% of the nodes into one cluster. Collapsed results are marked and not ranked on the real graphs, because a single cluster is trivially fair.
Metrics. For clustering quality, we report normalized mutual information (NMI) [59] and macro-F1 [60] between clusters and labels, with clusters matched to classes by the Hungarian algorithm [61] for F1, as well as modularity [2], which measures community structure without labels. For fairness, we report the statistical-parity gap [8] of the hard clustering,
that is, the largest deviation of any cluster’s group share from the population share; it is zero exactly when the clusters are independent of the protected attribute, for any number of groups. Higher is better (↑) for NMI, F1, and , and lower is better (↓) for . Beyond the clusters, two further quantities describe the trained encoder itself. The first is the nCGAR of the trained attention (Definition 1), averaged over layers, heads, and partitions with at least two groups, where 1 means group-neutral attention. The second, which we call the -probe, measures how much of the protected attribute remains in the node embeddings: a logistic-regression probe [62] is trained to predict from , as done to measure protected information in graph embeddings [63], and we report its balanced accuracy [64] under 5-fold cross-validation. We use balanced accuracy because the groups are imbalanced; a value of (0.5 for two groups) means that cannot be linearly decoded (↓).
Implementation. FairPGT uses three layers with hidden size 256 and four heads, eight spectral encodings, a 32-dimensional clustering projection, dropout 0.1, and METIS partitions. Input features are standardized, and cluster centres are initialized by -means on the initial embeddings. The CGAR target uses , the graph-aware target is refreshed every epochs, and the loss weights are , , and . We train with Adam [65] (learning rate , weight decay , gradient clipping at 1). Baselines use the default hyperparameters of their reference implementations where available, aligned only in the number of clusters, the epoch budget, and the evaluation protocol. All methods are implemented in PyTorch and PyTorch Geometric, and each run uses a single NVIDIA GPU (H100 NVL for the largest graphs).
Q1: Quality and fairness on real graphs
Table 3 reports NMI and for all methods, and Table 4 complements it with macro-F1 and modularity. To make the trade-off visible at a glance, Figure 3 places every method in the NMI– plane, together with FairPGT trained without its fairness terms.
| Deep graph clustering | Fair deep | Fair spectral | Ours | |||||||||||||
| Dataset | Metric | DMoN | SDCN | CCGC | SCGC | DinkNet | DiffPool | MinCutPool | DMoN-SP | FairGC | FairGT | FairGP | sFairSC | iFairSC | FairPGT | |
| NBA | F1↑ | .626±.04 | .376±.00† | .476±.13† | .372±.01† | .376±.00† | .371±.01† | .593±.08 | .488±.16† | .520±.03 | .659±.02 | .459±.10† | .690±.00 | .497±.00 | .677±.03 | |
| NBA | Q↑ | .105±.01 | .000±.00† | .025±.04† | .001±.00† | .000±.00† | .001±.00† | .072±.04 | .040±.05† | .023±.01 | .005±.00 | .023±.02† | .127±.00 | −.003±.00 | .070±.02 | |
| German | F1↑ | .524±.01 | .489±.05 | .524±.02 | .520±.04 | .412±.00† | .472±.03 | .541±.02 | .524±.01 | .494±.01 | .519±.03 | .527±.05 | .488±.00 | .484±.00 | .491±.02 | |
| German | Q↑ | .421±.01 | .237±.16 | .364±.01 | .330±.02 | .000±.00† | .228±.15 | .394±.01 | .422±.01 | .214±.05 | .326±.02 | .353±.01 | .391±.00 | −.010±.00 | .418±.03 | |
| LastFM | F1↑ | .589±.05 | .318±.07† | .352±.03 | .335±.06 | .133±.09† | .188±.05† | .456±.04 | .588±.04 | .241±.01 | .457±.05 | .443±.04 | .319±.00 | .171±.00 | .403±.04 | |
| LastFM | Q↑ | .666±.03 | .542±.08† | .487±.03 | .405±.06 | .113±.15† | .262±.09† | .614±.02 | .661±.02 | .139±.02 | .471±.03 | .609±.03 | .555±.00 | −.002±.00 | .460±.05 | |
| F1↑ | .493±.08 | .196±.18† | .369±.01 | .416±.06 | .276±.06 | .274±.04† | .449±.06 | .493±.08 | .288±.02 | .389±.04 | .375±.03 | .253±.00 | n/s | .373±.02 | ||
| Q↑ | .648±.01 | .107±.24† | .556±.02 | .568±.03 | .376±.13 | .350±.12† | .606±.03 | .648±.02 | .208±.06 | .396±.11 | .596±.02 | .409±.00 | n/s | .592±.02 | ||
| Credit | F1↑ | .468±.05 | .477±.02 | .507±.02 | .514±.04 | .489±.05 | .497±.05 | .494±.01 | .468±.05 | n/s | .527±.02 | .505±.03 | .452±.00† | n/s | .536±.12 | |
| Credit | Q↑ | .462±.00 | .472±.01 | .414±.03 | .374±.02 | .412±.07 | .393±.04 | .443±.01 | .462±.00 | n/s | .382±.04 | .440±.02 | .236±.00† | n/s | .368±.09 | |
| Pokec-n | F1↑ | .428±.01 | .445±.03 | OOM | OOM | .459±.00† | n/s | n/s | .431±.00 | n/s | .525±.00 | .448±.03 | .525±.00 | n/s | .453±.06 | |
| Pokec-n | Q↑ | .411±.00 | .186±.01 | OOM | OOM | .004±.00† | n/s | n/s | .411±.00 | n/s | .012±.01 | .266±.07 | .320±.00 | n/s | .059±.03 | |
| Pokec-z | F1↑ | .434±.01 | .443±.03 | OOM | OOM | .451±.00† | n/s | n/s | .432±.01 | n/s | .529±.03 | .451±.03 | .517±.00 | n/s | .491±.01 | |
| Pokec-z | Q↑ | .440±.00 | .167±.02 | OOM | OOM | .002±.00† | n/s | n/s | .441±.00 | n/s | .014±.01 | .298±.11 | .354±.00 | n/s | .053±.02 |
Table 4. Complementary quality metrics: macro-F1 against the labels and modularity of the graph. Mean and standard deviation over five seeds. Best in bold and underlined, runner-up in underlined, among runs that did not collapse; †: collapsed (fewer than clusters used, or one cluster holding over 90% of the nodes, in at least half of the runs). : not scalable, skipped (memory quadratic or cubic in ); OOM: out of GPU memory.
Figure 3. Quality–fairness plane (mean ± std over five seeds; up and left is better). Squares: fairness-agnostic baselines; circles: fair baselines; filled star: FairPGT; hollow star: FairPGT without fairness terms. The dashed line is the Pareto front of the methods, and the light red line traces FairPGT for on NBA, German and LastFM. (h) SBM at full alignment; the diamond is the best NMI any clustering with can reach (Proposition 3). Collapsed runs on the real graphs are omitted.
Large graphs. The three largest graphs are where FairPGT is strongest: on Credit, Pokec-n, and Pokec-z, it is the only method with both the highest NMI and the lowest . On Pokec-n and Pokec-z, its is 0.006 and 0.005, about ten times lower than that of DMoN (0.054 and 0.056), while its NMI is 0.098 and 0.106, against 0.072 and 0.062 for the next best method, FairGT. Since both Pokec graphs have four protected groups, this result also holds beyond binary attributes. On Credit, the NMI gain varies considerably across seeds (0.042 ± 0.053), whereas the fairness gain is stable (0.003 ± 0.002). Modularity shows what this choice means. DMoN finds a highly modular partition of Pokec-n (), but its clusters are unrelated to the labels (NMI 0.001) and differ by group (). FairPGT, in contrast, trades modularity (, Table 4) for clusters that are better aligned with the labels and almost independent of the group, which is exactly the expected outcome from a fair clustering method considering both objectives together.
Graphs with group-aligned communities. On LastFM and Facebook, the strongest communities are correlated with the protected attribute: DMoN, for example, reaches NMI 0.550 on LastFM, but with . These are therefore the graphs where fairness costs the most, and FairPGT pays this price openly. It reduces tenfold on LastFM (0.399 0.040) and more than fourfold on Facebook (0.124 0.027), while keeping NMI at 0.289 and 0.057. Among the methods that reach without collapsing, FairPGT has the highest NMI on both graphs; the only fairer method on LastFM, iFairSC (), has NMI 0.001. As § 4.3 shows, this loss is the expected price of fairness when communities and groups coincide.
Small graphs. On the two smallest graphs, however, a classical method remains hard to beat. On NBA, sFairSC is better than FairPGT in both NMI (0.133 vs. 0.107) and (0.011 vs. 0.016). On German, no method recovers the labels (NMI for all), so German measures fairness only; here too, sFairSC has the lowest (0.006).
Summary. Taken together, in mean NMI and , FairPGT is dominated by another method only on NBA, by sFairSC. Most fairness-aware deep baselines (DMoN-SP, FairGT, FairGP) keep most of the unfairness of DMoN on LastFM ( 0.39–0.45), and sFairSC, although it enforces exact parity on the relaxed problem, reaches 0.37–0.47 on LastFM and Facebook after -means rounding. The fairness of FairPGT, in turn, comes from its assignment-level group term, which acts on the soft assignments throughout training (§ 4.4).
Embeddings. Figure 4 shows what this fairness looks like in the learned representations. On the LastFM network, DMoN, sFairSC, and FairGP form clusters in which the minority group is concentrated in some clusters and nearly absent from others, and FairPGT without its fairness terms behaves the same way. With its fairness terms, by contrast, FairPGT keeps

Figure 4. t-SNE of the node embeddings (seed 0). Red: minority group; other colours: the clusters of the majority-group nodes; points are drawn in random order, so a fair clustering shows red spread evenly over all clusters. Methods: the strongest fairness-agnostic baseline (DMoN), the strongest fair baseline on small graphs (sFairSC, its fair spectral embedding), the closest architecture (FairGP), and FairPGT without and with its fairness terms. Below each panel: NMI and of the plotted run.
well-separated clusters, each of which contains both groups close to their population shares. On the SBM at full alignment, every baseline recovers the four communities, which here are the groups themselves; FairPGT instead forms two clusters that each join one community of each group, which is precisely the structure of the optimal fair clustering in Proposition 3. Finally, sFairSC illustrates that a group-neutral representation does not by itself yield fair clusters: its constraint equalizes the group means of the spectral embedding, so a linear probe cannot recover the group from it (S-probe 0.50 on LastFM), and yet -means on this embedding yields .
Q2: The price of fairness under controlled alignment
Real graphs do not let us control how strongly communities and groups overlap. The SBMs of Section 4.1, in contrast, allow these: their alignment moves from groups that are independent of the communities () to groups that coincide with them (), while the features always carry the group. Before looking at the results, it helps to know the best that any fair method can achieve in the extreme case, which the following proposition establishes.
Proposition 3 (Price of exact parity at full alignment). *Let , equal communities , and . Every clustering with satisfies NMI (arithmetic normalization), with equality for the pairing .
Proof. means is independent of , so bit. Since is a function of , , hence . Also . With , which increases in , the bound is at . The pairing is independent of and has .
Figure 5 shows the results. At , all methods recover the communities () and are fair (, the sampling noise of the generator). As grows, however, the methods without an effective fairness term (FairPGT without fairness terms, FairPGT with the attention term only, and DMoN-SP) keep NMI near 1, while their rises almost linearly to 0.50; sFairSC follows the same trend (0.48 at ). FairPGT, by contrast, keeps at every alignment and reaches 0.002 at . Its NMI falls to 0.57 at and recovers to 0.646 at , which is 97% of the bound in Proposition 3. Notably, it reaches this value with two clusters of equal size, each joining one community of each group, which is exactly the structure of the optimal fair clustering in the proof of Proposition 3; on the SBMs, we therefore do not count fewer than clusters as a collapse. In other words, at full alignment FairPGT is almost as accurate as any exactly fair clustering can be: its loss in NMI is the price of parity itself, not a weakness of the encoder.
Figure 5. SBMs with community–group alignment (mean, shaded one std over three seeds). (a) The diamond marks the NMI bound of Proposition 3 at . (c) nCGAR of the trained encoder (log scale; shaded band: ); DMoN-SP and sFairSC have no attention. (d) -probe: 0.5 means the group cannot be decoded from the embeddings.
Encoder neutrality is two-sided. Fair clusters, however, do not yet tell us whether the encoder itself is group-neutral. The two right panels of Figure 5 therefore look inside the encoder, and they reveal three distinct behaviours. Without fairness terms, attention follows the groups: at , it is strongly group-homophilous (nCGAR 0.29), and the group can be read off the embeddings perfectly (-probe 1.00). With the group term alone, the clusters become fair, but the encoder swings to the other extreme: attention becomes group-heterophilous (nCGAR 2.9 at and 3.7 at ), so the encoder still uses group membership, only in reverse. With both terms, finally, nCGAR stays between 0.84 and 1.01 at every alignment: the clusters are fair, and the attention is neutral. The converse also holds: the nCGAR term alone moves attention toward neutrality (from 0.29 to 0.82 at ) but leaves at 0.50, because the features themselves carry the group, by construction of the SBM, and reach the clustering head through the residual path. In short, neither level can stand in for the other.
Figure 6 takes a closer look, resolving the attention head by head. At without fairness terms, every first-layer head is group-homophilous (nCGAR 0.54–0.72). With the group term alone, the heads split: some become strongly heterophilous (up to 12.2), while others remain homophilous (down to 0.52). Its attention thus still depends on group membership, in both directions at once, and the geometric mean of 1.67 hides how far individual heads are from neutral. With the nCGAR term, in contrast, alone or in the full model, all heads stay near 1 (0.98–1.05 and 0.98–1.28, respectively). On LastFM, a real graph, the fairness-agnostic heads are likewise homophilous in the first layer (0.63–0.71), and the full model keeps every head within 0.94–1.08; here, however, the group term alone does not over-correct, as expected from the weaker alignment.
Figure 6. nCGAR of every attention head of the trained encoder (rows: layers; columns: heads), for the METIS partition with the most balanced group composition; 1 is group-neutral, blue cells favour the node’s own group, red cells the other group. Top: SBM with alignment (the whole partition of 250 nodes). Bottom: LastFM (a stratified sample of 400 of the 682 nodes of the partition). Seed 0.
Since nCGAR pools all nodes of a partition, we finally split it by the group of the attending node. On LastFM, the first layer of the full model is balanced for both groups: each sends 46–55% of its attention across groups, against about 50% under uniform attention. In the second layer, however, one group sends 56–62% and the other 34–49%, so part of the aggregate balance comes from the two deviations offsetting each other. On the SBM at , the majority group stays close to its uniform share in most heads (15–26% against 20%), while the 51 minority nodes of the partition deviate more strongly, in both directions: in the head with nCGAR 1.28, for example, they send only 2% across groups (against 80% under uniform attention), whereas the majority sends 48%. Similarly, we audit the routing branch, which nCGAR does not cover, by the mutual information between a node’s group and the routing token it attends to. In the full model, this is at most 0.004 nats on every real graph and 0.046 on the SBM at , against 0.62 without fairness terms (the maximum for two groups is ). Notably, the attention term alone leaves it at 0.62, so the routing branch is kept group-independent by the group term. In short, the trained encoder is balanced in aggregate and its routing carries almost no group information, but its local attention is not yet neutral for each group separately.
Q3: Ablation
To answer Q3, Figure 7 removes or replaces one component at a time, in an independent rerun with the same protocol (differences from Table 3 are within one standard deviation). The variants separate the two fairness levels from the two quality terms, and they show that each component has a distinct role.
Figure 7. Ablation of FairPGT (mean over five seeds). Each row changes one component of the full model and keeps everything else fixed: w/o and w/o remove one fairness term, w/o both fairness terms removes both; DEC target instead of replaces the graph-aware target of Eq. (10) by the standard DEC target; w/o routing tokens removes cross-partition communication, so attention stays within partitions; DMoN collapse term instead of replaces our information term by the collapse regularizer of DMoN. Each cell gives the value of the variant; its colour shows the change relative to the full model (first row), blue where the variant is better and red where it is worse.
The group term () is what makes the clusters fair. Removing it raises on every dataset except Credit, where it is already 0.007: LastFM 0.034 0.286, German 0.032 0.132, Facebook 0.028 0.082, NBA 0.020 0.075, and Pokec-n 0.007 0.034. Without it, FairPGT is a capable but unfair clustering method.
The attention term (), in contrast, shapes the encoder, not the outcome. Removing it changes NMI and by at most 0.013 on any dataset. On the real graphs, the trained attention is already close to neutral (mean nCGAR 0.90–1.06 in all variants), so the term has little to correct; its effect appears when the alignment is strong (Section 4.3) and at the level of individual heads (Figure 6).
On the quality side, the graph-aware target () is what makes FairPGT accurate on strongly modular graphs. Replacing it with the standard DEC target lowers NMI on
LastFM from 0.30 to 0.09 and on Facebook from 0.06 to 0.04, consistent with Theorem 2: the structural guidance matters where the graph is modular. On the other datasets, NMI changes by at most 0.023. The standard DEC target yields a lower on five graphs, and on NBA it is better in both metrics; on LastFM and Facebook, however, this fairness comes with the loss of NMI just described, on both Pokec graphs, the standard target gains some NMI (0.112 vs. 0.097 and 0.120 vs. 0.105) but is about three times less fair (0.020 vs. 0.007 and 0.016 vs. 0.005)
Similarly, routing tokens matter most on large, weakly modular graphs. Without them, NMI collapses on Credit (0.04 0.00) and drops on Pokec (0.10 0.05–0.07). On the smaller graphs, NMI instead rises (NBA, Facebook, and LastFM, the last to 0.45), but on LastFM only, together with a fivefold larger gap ( 0.034 0.161). In other words, letting partitions communicate with each other is what keeps FairPGT accurate on the large graphs.
Finally, our information term matters for fairness, not only for quality. A common alternative for preventing degenerate clusters is the collapse regularizer of DMoN [34], , which constrains only the cluster sizes and, unlike , is already minimal when all nodes share the uniform assignment. To test whether our choice matters, we replace with this regularizer and keep everything else fixed. The replacement lowers NMI on NBA (0.09 0.06) and Pokec (0.10 0.06–0.08), and triples on LastFM (0.034 0.106); its higher NMI on LastFM (0.35) comes only together with that larger gap.
Taken together, the ablation mirrors the design of FairPGT: two terms make it fair, at the level of the clusters and of the attention, and two components make it accurate, the graph-aware target on modular graphs and the routing tokens on large ones. None of them can be dropped without losing something the others do not recover.
Q4: Sensitivity and cost
Finally, we turn to the practical side: how sensitive FairPGT is to its weights, and what partitioning costs and buys.
Fairness weight. The weight is the main control of the trade-off (three seeds per value; red line in Figure 3). On LastFM, small weights () leave the gap almost unchanged, and from upward falls steadily, from 0.260 at 1 to 0.125 at 3 and 0.035 at 10, while NMI decreases from 0.362 at to 0.288. On NBA, by contrast, fairness costs no measurable accuracy: falls from 0.103 to 0.017 while NMI stays within seed variation (0.056–0.093 across all weights). The attention weight, in turn, is robust: changes neither NMI nor beyond seed variation (LastFM: NMI 0.285–0.301, 0.032–0.048), in line with its role of shaping the encoder rather than the outcome. Finally, is best kept moderate: without it (), the gap on LastFM more than doubles (0.042 0.098), while at NMI on LastFM drops to 0.228, so values in [0.3, 1] balance the two.
Partitions. Figure 8 varies the number of partitions (one seed, 50 epochs). As predicted by Proposition 2, peak memory follows closely at small and flattens once the per-node terms dominate: it falls from 11.9 GB to 0.75 GB on LastFM (), from 50 GB to 5.5 GB on Facebook, and from 88 GB to 8.1 GB on Credit (), while Pokec does not fit at and fits from (our default needs 72 GB, Table 5). Time per epoch falls accordingly, by up to . Importantly, restricting attention to partitions does not cost quality: on LastFM, NMI even rises with , from 0.16 at to 0.34–0.38 at , and on Facebook, Credit, and Pokec it changes by at most 0.04.
| Method | NBA | German | LastFM | Credit | Pokec-n | Pokec-z | |
| DMoN | 0.7 / 0.03 | 0.7 / 0.03 | 0.7 / 0.26 | 2.1 / 4.51 | 4.6 / 7.24 | 1.0 / 0.74 | 1.2 / 0.86 |
| SDCN | 3.2 / 0.41 | 3.1 / 0.34 | 6.9 / 1.04 | 74.0 / 18.61 | 16.1 / 9.48 | 52.8 / 19.83 | 60.4 / 23.14 |
| CCGC | 1.0 / 0.07 | 0.9 / 0.06 | 1.6 / 0.87 | 19.4 / 14.67 | 10.4 / 25.36 | – | – |
| SCGC | 6.6 / 0.03 | 15.1 / 0.06 | 85.8 / 1.04 | 601.4 / 17.32 | 228.8 / 29.18 | – | – |
| DinkNet | 1.3 / 0.07 | 1.2 / 0.06 | 2.1 / 0.42 | 8.7 / 6.74 | 12.7 / 11.08 | 56.8 / 36.03 | 59.3 / 37.37 |
| DiffPool | 0.7 / 0.02 | 0.6 / 0.05 | 1.7 / 0.98 | 10.3 / 16.66 | 17.2 / 28.89 | – | – |
| MinCutPool | 1.1 / 0.03 | 1.2 / 0.04 | 4.2 / 0.51 | 71.3 / 8.61 | 94.2 / 14.51 | – | – |
| DMoN-SP | 1.0 / 0.03 | 1.0 / 0.03 | 1.5 / 0.26 | 1.8 / 4.55 | 2.9 / 7.24 | 2.0 / 0.74 | 1.3 / 0.86 |
| FairGC | 1.4 / 0.04 | 1.3 / 0.10 | 25.6 / 2.04 | 752.5 / 33.25 | – | – | – |
| FairGT | 1.9 / 0.07 | 1.6 / 0.06 | 2.5 / 0.26 | 4.7 / 4.51 | 3.6 / 7.24 | 8.1 / 2.67 | 9.3 / 3.17 |
| FairGP | 1.7 / 0.03 | 1.7 / 0.03 | 2.4 / 0.26 | 3.9 / 4.55 | 8.8 / 7.24 | 8.9 / 3.63 | 9.7 / 4.21 |
| sFairSC | 0.0 / 0.00 | 0.2 / 0.00 | 0.2 / 0.12 | 3.3 / 2.44 | 6.7 / 3.60 | 5.4 / 0.03 | 5.1 / 0.04 |
| iFairSC | 0.2 / 0.02 | 0.7 / 0.02 | 56.2 / 0.14 | – | – | – | – |
| FairPGT | 5.8 / 0.12 | 4.5 / 0.20 | 9.5 / 1.92 | 37.8 / 24.92 | 43.3 / 32.69 | 94.1 / 71.56 | 93.3 / 71.72 |
Table 5. Training time in seconds↓ / peak GPU memory in GB↓ (200 epochs, mean over five seeds; memory is the peak allocated by PyTorch). –: skipped or out of memory. Runs used different GPUs (§ 4.1), so times are indicative.
Cost. FairPGT is heavier than lightweight GNN clustering methods: with the default , a run on Pokec takes 94 s and 72 GB, against 1 s and 0.7 GB for DMoN and 9 s and 3.6 GB for FairGP (Table 5). It is, however, faster than several deep clustering baselines on the same GPU, taking 38 s on Facebook against 71 s for MinCutPool and 752 s for FairGC, and it completes on Pokec, where CCGC and SCGC run out of memory. Moreover, memory, its main cost, is directly controlled by : on Pokec, 64 partitions need less than half the memory of the default (Figure 8) wit similar NMI.
In summary, FairPGT has a single weight that steers the trade-off, two weights that need no tuning within a broad range, and one structural knob, , that reduces memory with little change in NMI over the tested settings.
Discussion, limitations, and outlook
Fairness in assignments and attention. Taken together, the experiments separate two levels of fairness. Outcome fairness comes from the assignment-level group term: it lowers the statistical-parity gap wherever there is a gap to lower, that is, on every dataset except Credit, where the gap is already 0.007. Attention-level balance, in turn, comes from the nCGAR term, which discourages both same-group and cross-group preference in the aggregate partition-local attention but does not make the clusters fair on its own. The reason is architectural: a residual connection carries each node’s own features, which can encode the group, past any attention pattern. Aggregate attention balance is therefore a property of the encoder that can be audited separately from the fairness of the assignments, rather than a guarantee on the outcome. This is exactly the role in which we use nCGAR: as a diagnostic of the trained encoder, and as a regularizer that counters the attention imbalance the group term produces when used alone. This separation is, in our view, the main lesson of this work.
Limitations and future work. Like any method, FairPGT has a scope that our experiments delineate, and each part of it points to a concrete next step. First, FairPGT does not maximize modularity: on Pokec, its clusters are less modular than those of DMoN ( vs. ) but follow the labels more closely, so when the most modular partition is itself the goal, a modularity-based method remains the better choice. Second, on the two smallest graphs, fair spectral clustering remains a strong competitor, which suggests that the benefits of attention grow with the size and richness of the graph. Third, attention within partitions makes FairPGT more demanding than lightweight GNN methods; the number of partitions, however, offers a direct way to reduce its memory with little change in NMI over the tested settings (Figure 8). Fourth, nCGAR balances the aggregate attention of each partition, not separately for each group; the per-group diagnostic of § 4.3 makes this visible, so practitioners can check it on any trained encoder. Fifth, FairPGT is transductive: partitions and spectral encodings are computed on the whole graph, so adding new nodes currently requires rerunning the pipeline. Finally, the method handles any number of categorical groups, so several attributes can be combined into intersectional groups (for example, gender and four age groups give ). Our experiments use one protected attribute at a time, binary on five graphs and with four groups on Pokec; evaluating intersectional settings, in which small intersections can make the group shares noisy, is a natural next step.
Ethical considerations. FairPGT is meant for settings where clusters inform decisions about people, such as customer segmentation in finance or community analysis in social networks, and three cautions apply. First, it needs the protected attribute of every training node. Such attributes are personal data, some of them legally protected, so collecting and storing them requires a legal basis and safeguards; the trained model does not use them at inference, which confines their use to training. Second, statistical parity is one notion of fairness among several: clusters with equal group shares can still feed unfair decisions downstream, parity on one attribute does not imply parity for intersections of attributes, and fair clusters must not be used to justify treating groups differently. Third, the groups of LastFM and Facebook are constructed from the features and serve only as benchmarks, without demographic meaning. Conversely, the nCGAR of a trained encoder offers practitioners a way to audit whether a graph transformer’s attention mixes the groups evenly, independently of how its output is later used.
Conclusion
We presented FairPGT, a partitioned graph transformer for fair unsupervised graph clustering. Partition-local attention with routing tokens makes a transformer encoder feasible on graphs with tens of thousands of nodes, and a graph-aware self-training target lets it exploit the community structure. On top of this, FairPGT imposes fairness at two complementary levels. The assignment-level term makes the clusters fair, and on the three largest benchmarks FairPGT has both the highest mean NMI and the lowest statistical-parity gap. The nCGAR term, in turn, keeps the encoder’s attention balanced across groups; when communities and groups align strongly, the assignment term alone drives the attention to become group-heterophilous. Moreover, on controlled graphs where communities and groups coincide, FairPGT reaches 97% of the best NMI that any exactly fair clustering can achieve, so its loss in quality there is largely the price of fairness itself rather than a weakness of the encoder. Above all, our results show that fair clusters and balanced attention are distinct goals, and that a fair clustering method should, and can, reach both. Two extensions follow naturally from this work: an inductive version for evolving graphs and unseen nodes, and control of the quality–fairness trade-off at inference time.
Acknowledgments
Siamak Ghodsi gratefully acknowledges support from the German Research Foundation (DFG SPP 2443 (543081196)). Amjad Seyedi acknowledges support from the European Union (ERC consolidator, eLinoR, no. 101085607).
References
- [1]S. Fortunato, D. Hric, Community detection in networks: A user guide, Physics reports 659 (2016) 1–44.DOI
- [2]M. E. Newman, Modularity and community structure in networks, PNAS 103 (23) (2006) 8577–8582.pubmed.ncbi.nlm.nih.gov/16723398
- [3]W. Ju, S. Yi, Y. Wang, Q. Long, J. Luo, Z. Xiao, M. Zhang, A survey of data-efficient graph learning, in: IJCAI, 2024, pp. 8104–8113.arxiv.org/abs/2402.00447
- [4]Y. Dong, J. Ma, S. Wang, C. Chen, J. Li, Fairness in graph mining: A survey, IEEE Trans. Knowl. Data Eng. 35 (10) (2023) 10583–10602.arxiv.org/abs/2204.09888
- [5]Y. Liu, X. Yang, S. Zhou, X. Liu, S. Wang, K. Liang, W. Tu, L. Li, Simple contrastive graph clustering, IEEE Trans. Neural Networks Learn. Syst. 35 (10) (2024) 13789–13800.DOI
- [6]S. K. Bera, D. Chakrabarty, N. Flores, M. Negahbani, Fair algorithms for clustering, in: NeurIPS, 2019, pp. 4955–4966.arxiv.org/abs/1901.02393
- [7]S. Ghodsi, S. A. Seyedi, E. Ntoutsi, Towards cohesion-fairness harmony: Contrastive regularization in individual fair graph clustering, in: PAKDD (1), Vol. 14645, 2024, pp. 284–296.arxiv.org/abs/2402.10756
- [8]C. Dwork, M. Hardt, T. Pitassi, O. Reingold, R. S. Zemel, Fairness through awareness, in: Proceedings of the 3rd ITCS Conference, 2012, pp. 214–226.
- [9]A. Chen, R. A. Rossi, N. Park, P. Trivedi, Y. Wang, T. Yu, S. Kim, F. Dernoncourt, N. K. Ahmed, Fairness-aware graph neural networks: A survey, ACM Trans. Knowl. Discov. Data 18 (6) (2024) 138:1–138:23.arxiv.org/abs/2307.03929
- [10]Z. Jiang, X. Han, C. Fan, Z. Liu, N. Zou, A. Mostafavi, X. Hu, FMP: toward fair graph message passing against topology bias, CoRR abs/2202.04187 (2022).arxiv.org/abs/2202.04187
- [11]X. Lin, J. Kang, W. Cong, H. Tong, Bemap: Balanced message passing for fair graph neural network, in: LoG, Vol. 231 of Proceedings of Machine Learning Research, PMLR, 2023, p. 37.arxiv.org/abs/2306.04107
- [12]D. Kreuzer, D. Beaini, W. L. Hamilton, V. Létourneau, P. Tossou, Rethinking graph transformers with spectral attention, in: NeurIPS, 2021, pp. 21618–21629.arxiv.org/abs/2106.03893
- [13]L. Rampásek, M. Galkin, V. P. Dwivedi, A. T. Luu, G. Wolf, D. Beaini, Recipe for a general, powerful, scalable graph transformer, in: NeurIPS, Vol. 35, 2022, pp. 14501–14515.arxiv.org/abs/2205.12454
- [14]D. Chen, L. O’Bray, K. M. Borgwardt, Structure-aware transformer for graph representation learning, in: ICML, Vol. 162 of Proceedings of Machine Learning Research, PMLR, 2022, pp. 3469–3489.arxiv.org/abs/2202.03036
- [15]F. Chierichetti, R. Kumar, S. Lattanzi, S. Vassilvitskii, Fair clustering through fairlets, in: NeurIPS, 2017, pp. 5029–5037.arxiv.org/abs/1802.05733
- [16]M. Kleindessner, S. Samadi, P. Awasthi, J. Morgenstern, Guarantees for spectral clustering with fairness constraints, in: ICML, Proceedings of Machine Learning Research, PMLR, 2019, pp. 3458–3467.arxiv.org/abs/1901.08668
- [17]S. Gupta, A. Dukkipati, Consistency of constrained spectral clustering under graph induced fair planted partitions, in: NeurIPS, 2022, pp. 13527–13540.arxiv.org/abs/2105.03714
- [18]J. Wang, D. Lu, I. Davidson, Z. Bai, Scalable spectral clustering with group fairness constraints, in: AISTATS, 2023, pp. 6613–6629.arxiv.org/abs/2210.16435
- [19]R. Feng, C. Zhong, J. Qian, T. Pan, X. Yue, A fair spectral clustering with weighted fairness constraints, Pattern Recognit. 173 (2026) 112821.DOI
- [20]P. Li, H. Zhao, H. Liu, Deep fair clustering for visual learning, in: CVPR, Computer Vision Foundation / IEEE, 2020, pp. 9067–9076.DOI
- [21]H. Zhang, X. Wang, T. Ren, Y. Wang, S. Yi, F. Meng, Z. Ma, Q. Long, W. Ju, FairGC: Fostering individual and group fairness for deep graph clustering, in: AAAI, AAAI Press, 2026, pp. 28194–28202.
- [22]M. Jiang, J. Zhou, L. Hu, X. Liu, Z. He, Z. Chen, Adversarial fair multi-view clustering, Pattern Recognit. 179 (2026) 113708.arxiv.org/abs/2508.04071
- [23]S. Ghodsi, A. Seyedi, T. L. Quy, F. Karimi, E. Ntoutsi, A deep latent factor graph clustering with fairness-utility trade-off perspective, in: IEEE Big Data, IEEE, 2025, pp. 1705–1714.DOI
- [24]E. Dai, S. Wang, Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information, in: WSDM, ACM, 2021, pp. 680–688.arxiv.org/abs/2009.01454
- [25]C. Agarwal, H. Lakkaraju, M. Zitnik, Towards a unified framework for fair and stable graph representation learning, in: UAI, Vol. 161, AUAI Press, 2021, pp. 2114–2124.arxiv.org/abs/2102.13186
- [26]Y. Dong, N. Liu, B. Jalaian, J. Li, EDITS: modeling and mitigating data bias for graph neural networks, in: WWW, ACM, 2022, pp. 1259–1269.DOI
- [27]Q. Chen, W. Wei, D. Cheng, J. Li, L. Liu, X. Zhu, Learning fair graph representation through neighbor counterfactual information, Pattern Recognit. 180 (2026) 114308.DOI
- [28]X. Wang, Y. Li, T. Gu, X. Bao, L. Chang, G. Cai, T. Liu, Towards unified frameworks for fair and privacy-preserving graph neural networks, Neural Networks 196 (2026) 108448.DOI
- [29]J. Zhao, T. Huang, S. Liu, J. Yin, Y. Pei, M. Fang, M. Pechenizkiy, FS-GNN: improving fairness in graph neural networks via joint sparsification, Neurocomputing 648 (2025) 130641.DOI
- [30]W. Zhang, X. Zhu, R. Shang, J. Ren, L. Jiao, Adaptive graph clustering based on feature adversarial and graph transformer, Expert Syst. Appl. 281 (2025) 127541.DOI
- [31]R. Luo, H. Huang, S. Yu, X. Zhang, F. Xia, FairGT: A fairness-aware graph transformer, in: IJCAI, 2024, pp. 449–457.arxiv.org/abs/2404.17169
- [32]R. Luo, H. Huang, I. Lee, C. Xu, J. Qi, F. Xia, FairGP: A scalable and fair graph transformer using graph partitioning, in: AAAI, AAAI Press, 2025, pp. 12319–12327.arxiv.org/abs/2412.10669
- [33]J. Xie, R. Girshick, A. Farhadi, Unsupervised deep embedding for clustering analysis, in: ICML, 2016, pp. 478–487.arxiv.org/abs/1511.06335
- [34]A. Tsitsulin, J. Palowitch, B. Perozzi, E. Müller, Graph clustering with graph neural networks, J. Mach. Learn. Res. 24 (2023) 127:1–127:21.
- [35]D. Bo, X. Wang, C. Shi, M. Zhu, E. Lu, P. Cui, Structural deep clustering network, in: WWW, ACM / IW3C2, 2020, pp. 1400–1410.DOI
- [36]X. Yang, Y. Liu, S. Zhou, S. Wang, W. Tu, Q. Zheng, X. Liu, L. Fang, E. Zhu, Cluster-guided contrastive graph clustering network, in: AAAI, 2023, pp. 10834–10842.arxiv.org/abs/2301.01098
- [37]Y. Liu, K. Liang, J. Xia, S. Zhou, X. Yang, X. Liu, S. Z. Li, Dink-net: Neural clustering on large graphs, in: ICML, Vol. 202 of Proceedings of Machine Learning Research, PMLR, 2023, pp. 21794–21812.arxiv.org/abs/2305.18405
- [38]Z. Ying, J. You, C. Morris, X. Ren, W. L. Hamilton, J. Leskovec, Hierarchical graph representation learning with differentiable pooling, in: NeurIPS, 2018, pp. 4805–4815.arxiv.org/abs/1806.08804
- [39]F. M. Bianchi, D. Grattarola, C. Alippi, Spectral clustering with graph neural networks for graph pooling, in: ICML, Vol. 119 of Proceedings of Machine Learning Research, PMLR, 2020, pp. 874–883.arxiv.org/abs/1907.00481
- [40]C. Gkartzios, E. Pitoura, P. Tsaparas, Modularity-fair deep community detection, in: ICDM, IEEE, 2025, pp. 287–296.DOI
- [41]C. Wang, S. Pan, G. Long, X. Zhu, J. Jiang, MGAE: marginalized graph autoencoder for graph clustering, in: CIKM, ACM, 2017, pp. 889–898.DOI
- [42]J. Chen, C. Liu, K. Gao, G. Li, K. He, Nagphormer+: A tokenized graph transformer with neighborhood augmentation for node classification in large graphs, IEEE Trans. Big Data 11 (4) (2025) 2085–2098.DOI
- [43]S. S. Hotegni, S. Mahabadi, A. Vakilian, Approximation algorithms for fair range clustering, in: ICML, Vol. 202 of Proceedings of Machine Learning Research, PMLR, 2023, pp. 13270–13284.arxiv.org/abs/2306.06778
- [44]Y. Bechavod, C. Jung, S. Wu, Metric-free individual fairness in online learning, in: NeurIPS, Vol. 33, 2020, pp. 11214–11225.arxiv.org/abs/2002.05474
- [45]C. Gkartzios, E. Pitoura, P. Tsaparas, Fair network communities through group modularity, in: WWW, ACM, 2025, pp. 506–517.DOI
- [46]G. Panayiotou, A. M. M. Simon, M. Magnani, E. Calikus, MOUFLON: multi-group modularity-based fairness-aware community detection, CoRR abs/2510.12348 (2025).DOI
- [47]Ö. D. Köse, Y. Shen, FairGAT: Fairness-aware graph attention networks, ACM Trans. Knowl. Discov. Data 18 (7) (2024) 164.arxiv.org/abs/2303.14591
- [48]G. Karypis, V. Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput. 20 (1) (1998) 359–392.DOI
- [49]J. Lee, Y. Lee, J. Kim, A. R. Kosiorek, S. Choi, Y. W. Teh, Set transformer: A framework for attention-based permutation-invariant neural networks, in: ICML, Vol. 97, 2019, pp. 3744–3753.arxiv.org/abs/1810.00825
- [50]K. Kim, B. Ji, D. Yoon, S. Hwang, Self-knowledge distillation with progressive refinement of targets, in: ICCV, IEEE, 2021, pp. 6547–6556.arxiv.org/abs/2006.12000
- [51]R. Gomes, A. Krause, P. Perona, Discriminative clustering by regularized information maximization, in: NIPS, Curran Associates, Inc., 2010, pp. 775–783.
- [52]L. Takac, M. Zabovsky, Data analysis in public social networks, International Scientific Conference and International Workshop Present Day Trends of Innovations (2012) 1–6.
- [53]T. L. Quy, A. Roy, V. Iosifidis, W. Zhang, E. Ntoutsi, A survey on datasets for fairness-aware machine learning, WIREs Data Mining Knowl. Discov. 12 (3) (2022).
- [54]B. Rozemberczki, R. Sarkar, Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models, in: CIKM, 2020, pp. 1325–1334.
- [55]B. Rozemberczki, C. Allen, R. Sarkar, Multi-scale attributed node embedding, J. Complex Networks 9 (2) (2021) cnab014.arxiv.org/abs/1909.13021
- [56]E. Abbe, Community detection and stochastic block models: Recent developments, J. Mach. Learn. Res. 18 (2017) 177:1–177:86.
- [57]Y. Deshpande, S. Sen, A. Montanari, E. Mossel, Contextual stochastic block models, in: NeurIPS, 2018, pp. 8590–8602.arxiv.org/abs/1807.09596
- [58]T. Qin, K. Rohe, Regularized spectral clustering under the degree-corrected stochastic blockmodel, in: NIPS, 2013, pp. 3120–3128.arxiv.org/abs/1309.4111
- [59]A. Strehl, J. Ghosh, Cluster ensembles — A knowledge reuse framework for combining multiple partitions, J. Mach. Learn. Res. 3 (2002) 583–617.DOI
- [60]M. Sokolova, G. Lapalme, A systematic analysis of performance measures for classification tasks, Inf. Process. Manag. 45 (4) (2009) 427–437.DOI
- [61]H. W. Kuhn, The hungarian method for the assignment problem, in: 50 Years of Integer Programming, Springer, 2010, pp. 29–47.
- [62]G. Alain, Y. Bengio, Understanding intermediate layers using linear classifier probes, ICLR (Workshop) (2017).arxiv.org/abs/1610.01644
- [63]A. J. Bose, W. L. Hamilton, Compositional fairness constraints for graph embeddings, in: ICML, Vol. 97 of Proceedings of Machine Learning Research, PMLR, 2019, pp. 715–724.arxiv.org/abs/1905.10674
- [64]K. H. Brodersen, C. S. Ong, K. E. Stephan, J. M. Buhmann, The balanced accuracy and its posterior distribution, in: ICPR, IEEE Computer Society, 2010, pp. 3121–3124.DOI
- [65]D. P. Kingma, J. Ba, Adam: A method for stochastic optimization, ICLR (Poster) (2015).arxiv.org/abs/1412.6980






