betaFeedback

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 kk-means (K=3K = 3). (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 O(n2)O(n^2) 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 NpN_p, 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.

MethodVenueTaskUnsup.Assign.Repr.Attn.GroupsEncoderKey idea
Deep graph clustering (fairness-agnostic)
DMoN [34]JMLR’23Clust.✓–GNNDifferentiable modularity
SDCN [35]WWW’20Clust.✓–AE+GCNAE–GCN fusion, DEC self-training
CCGC [36]AAAI’23Clust.✓–Contr. MLPCluster-guided positives and negatives
SCGC [5]TNNLS’24Clust.✓–Contr. MLPLow-pass filter, cross-view consistency
DinkNet [37]ICML’23Clust.✓–GNNCluster dilation and shrink
DiffPool [38]NeurIPS’18Pooling✗–GNNHierarchical differentiable pooling
MinCutPool [39]ICML’20Pooling✓–GNNRelaxed normalized min-cut
Fair clustering: classical, spectral, and factorization
Fairlets [15]NeurIPS’17Clust.*✓✓2–Fair micro-clusters, kk-center/median
Fair SC [16]ICML’19Clust.✓✓≥2\ge2SpectralProportionality constraint
sFairSC [18]AISTATS’23Clust.✓✓≥2\ge2SpectralScalable fair spectral clustering
iFairSC [17]NeurIPS’22Clust.✓indiv.–SpectralRepresentation-graph constraint
iFairNMTF [7]PAKDD’24Clust.✓indiv.≥2\ge2NMFContrastive individual-fair NMTF
DFNMF [23]BigData’25Clust.✓✓≥2\ge2Deep NMFStatistical-parity regularized deep NMF
Fair deep graph clustering and fair graph transformers
Mod.-fair DMoN [40]ICDM’25Clust.✓✓2GNNGroup-modularity terms in DMoN
FairGC [21]AAAI’26Clust.✓indiv.✓2Contr. MLPAdversarial and covariance debiasing
FairGT [31]IJCAI’24Class.✗✓2Hop-token attnSS-aware hop aggregation, eigenvector encodings
FairGP [32]AAAI’25Class.✗✓–Part. attnNo attention across partitions
FairPGT (ours)–Clust.✓✓✓≥2\ge2Part. attnRouting 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 kk-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 kk-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 G=(V,E)\mathcal{G} = (\mathcal{V}, \mathcal{E}) be an undirected attributed graph with n=∣V∣n = |\mathcal{V}| nodes, adjacency matrix A∈{0,1}n×nA \in\{0,1\}^{n \times n}, node degrees di=∑jAijd_i = \sum_j A_{ij}, and normalized Laplacian Lsym=I−AˉL_{\mathrm{sym}} = I - \bar{A}, where Aˉij=Aij/didj\bar{A}_{ij} = A_{ij}/\sqrt{d_i d_j}. Each node ii carries a feature vector xi∈Rdx_i \in\mathbb{R}^{d}, collected as X∈Rn×dX \in\mathbb{R}^{n \times d}, and a protected attribute si∈{1,…,G}s_i \in\{1,\ldots,G\}, collected as S∈{1,…,G}nS \in\{1,\ldots,G\}^{n}. Given (A,X,S)(A, X, S), our goal is to learn a model fθf_\theta that maps (A,X)(A, X) to soft cluster assignments C=fθ(A,X)∈Rn×KC = f_\theta(A, X) \in\mathbb{R}^{n \times K}, with Cik≥0C_{ik} \ge0 and ∑kCik=1\sum_k C_{ik} = 1, where KK 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 y^i=arg⁡max⁡kCik\hat{y}_i = \arg\max_k C_{ik}. Importantly, the protected attributes are not part of the feature matrix XX: they are provided separately as SS 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 (A,X)(A, X) 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 (A,X)(A, X) 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 CC. The objective combines two quality terms, the graph-aware target PP and the information term, with two fairness terms: Lgrp\mathcal{L}_{\mathrm{grp}} on the assignments and Latt\mathcal{L}_{\mathrm{att}}, 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 LL 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(⋅)(\cdot) denotes standard multi-head attention, FFN(⋅)(\cdot) a position-wise feed-forward network, and LN(⋅)(\cdot) 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 (λm,um)(\lambda_m,u_m) denote the eigenpairs of the Laplacian LsymL_{\mathrm{sym}}. We compute the normalized degree d~i=di/max⁡jdj\tilde{d}_i=d_i/\max_j d_j and the first bb nontrivial Laplacian eigenvectors U=[u1,…,ub]∈Rn×bU=[u_1,\ldots,u_b]\in\mathbb{R}^{n\times b}. The initial token matrix

H(0)=[X∥U∥d~]∈Rn×d0,d0=d+b+1,(1)H^{(0)} = [X \mathbin{\|} U \mathbin{\|} \tilde{d}] \in\mathbb{R}^{n \times d_0}, \qquad d_0 = d + b + 1, \tag*{(1)}

thus combines node attributes with spectral position information and degree-based centrality. Before training, each column of H(0)H^{(0)} 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 O(n2)O(n^2) per layer, which quickly becomes prohibitive on large graphs. To scale beyond it, we partition the graph into NpN_p disjoint blocks P={V1,…,VNp}\mathcal{P} = \{\mathcal{V}_1, \ldots, \mathcal{V}_{N_p}\} using METIS [48], a widely used multilevel partitioning algorithm that scales to large graphs and keeps densely connected nodes together. We set Np=max⁡(8,⌈n/2500⌉)N_p = \max(8, \lceil n/2500 \rceil), 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 NpN_p. Within each partition Vp\mathcal{V}_p and for every layer ℓ\ell, local multi-head attention is then computed from the projected representations Qp,Kp,Vp=LN⁡(Hp(ℓ−1))W{Q,K,V}(ℓ)Q_p, K_p, V_p = \operatorname{LN}(H_p^{(\ell-1)})W_{\{Q,K,V\}}^{(\ell)} as

A~p(ℓ)=softmax⁡(Qp(ℓ)Kp(ℓ)T/dh),p∈{1,…,Np}.(2)\widetilde{A}_p^{(\ell)} = \operatorname{softmax}\left(Q_p^{(\ell)}K_p^{(\ell)\mathsf{T}}/\sqrt{d_h}\right), \qquad p \in\{1,\ldots,N_p\}. \tag*{(2)}

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 QpKpTQ_pK_p^{\mathsf{T}} 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 ℓ\ell each partition is summarized by the mean of its normalized states, rp(ℓ)=∣Vp∣−1∑i∈VpLN⁡(hi(ℓ−1))r_p^{(\ell)} = |\mathcal{V}_p|^{-1}\sum_{i\in\mathcal{V}_p}\operatorname{LN}(h_i^{(\ell-1)}). The resulting set of tokens R(ℓ)=[r1(ℓ);…;rNp(ℓ)]R^{(\ell)} = [r_1^{(\ell)}; \ldots; r_{N_p}^{(\ell)}] exchanges information through global self-attention with a residual connection, R^(ℓ)=R(ℓ)+MHA⁡(LN⁡(R(ℓ)),LN⁡(R(ℓ)),LN⁡(R(ℓ)))\widehat{R}^{(\ell)} = R^{(\ell)} + \operatorname{MHA}(\operatorname{LN}(R^{(\ell)}), \operatorname{LN}(R^{(\ell)}), \operatorname{LN}(R^{(\ell)})), and each node then absorbs global context through cross-attention to the tokens, gi(ℓ)=MHA⁡(LN⁡(hi(ℓ−1)),R^(ℓ),R^(ℓ))g_i^{(\ell)} = \operatorname{MHA}(\operatorname{LN}(h_i^{(\ell-1)}), \widehat{R}^{(\ell)}, \widehat{R}^{(\ell)}). Since there are only NpN_p 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:

h^i(ℓ)=hi(ℓ−1)+(1−γ(ℓ))[A~p(ℓ)Vp(ℓ)WO(ℓ)]i+γ(ℓ)gi(ℓ),hi(ℓ)=h^i(ℓ)+FFN⁡(LN⁡(h^i(ℓ))),(3)\widehat{h}_i^{(\ell)} = h_i^{(\ell-1)} + (1-\gamma^{(\ell)})\left[\widetilde{A}_p^{(\ell)}V_p^{(\ell)}W_O^{(\ell)}\right]_i + \gamma^{(\ell)}g_i^{(\ell)}, \qquad h_i^{(\ell)} = \widehat{h}_i^{(\ell)} + \operatorname{FFN}(\operatorname{LN}(\widehat{h}_i^{(\ell)})), \tag*{(3)}

where i∈Vpi \in\mathcal{V}_p, WO(ℓ)W_O^{(\ell)} is the output projection, and γ(ℓ)=σ(γ‾(ℓ))∈(0,1)\gamma^{(\ell)} = \sigma(\overline{\gamma}^{(\ell)}) \in(0,1) 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 SS; inference uses (A,X)(A, X) alone.

Input: Graph AA, features XX, protected attribute SS (training only), number of clusters KK; weights λgrp,λatt,λinfo\lambda_{\mathrm{grp}},\lambda_{\mathrm{att}},\lambda_{\mathrm{info}}; CGAR step α\alpha and tolerance ϵ\epsilon; target interval TPT_{\mathrm{P}}; epochs TT

Output: Trained model fθf_{\theta}; soft assignments CC and cluster labels y^\hat{y}

Preprocessing (once)

1: Build the input tokens H(0)H^{(0)} from features, Laplacian eigenvectors, and degrees, standardized per column // Eq. (1)

2: Partition the graph with METIS into Np=max⁡(8,⌈n/2500⌉)N_{\mathrm{p}}=\max(8,\lceil n/2500\rceil) blocks P\mathcal{P}

3: ▶ Record the group composition τp\tau_p of every partition with at least two groups // Eq. (4)

4: Initialize θ\theta, and place the centers {μk}\{\mu_k\} by kk-means on the initial embeddings

Training

5: for t=1,…,Tt=1,\ldots,T do

6:     Encode: H(L)H^{(L)} and attention {A~p(ℓ)}\{\widetilde{A}^{(\ell)}_p\} from (H(0),P)(H^{(0)},\mathcal{P}) // Algorithm 2

7:     Assign: project ziz_i and compute the soft assignments CC // Eq. (7)

8:     if (t−1) mod TP=0(t-1)\bmod T_{\mathrm{P}}=0 then

9:         Refresh: recompute the graph-aware target PP and hold it fixed // Eqs. (8)–(10)

10:     end if

11:     ▶ Rebalance: build the CGAR target Ap(ℓ)\mathcal{A}^{(\ell)}_p for every layer, head, and mixed partition, held fixed // Eq. (5)

12:     ▶ Score: L←Lclust+λgrpLgrp+λattLatt+λinfoLinfo\mathcal{L}\leftarrow\mathcal{L}_{\mathrm{clust}}+\lambda_{\mathrm{grp}}\mathcal{L}_{\mathrm{grp}}+\lambda_{\mathrm{att}}\mathcal{L}_{\mathrm{att}}+\lambda_{\mathrm{info}}\mathcal{L}_{\mathrm{info}} // Eq. (13)

13:     Update: one Adam step on the encoder, the gates, WzW_z, and the centers

14: end for

Inference

15: Encode and assign as in training: C←fθ(A,X)C\leftarrow f_{\theta}(A,X)

16: y^i←arg⁡max⁡kCik\hat{y}_i\leftarrow\arg\max_k C_{ik} for every node ii

17: return fθf_{\theta}, CC, y^\hat{y}

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 Vp\mathcal{V}_p at layer ℓ\ell with attention

matrix A~p(ℓ)\widetilde{\mathcal{A}}_{p}^{(\ell)}, the CGAR and its normalized form nCGAR are

CGARp(ℓ)=∑i,j∈Vp:si≠sjA~ij(ℓ)∑i≠j∈Vp:si=sjA~ij(ℓ),nCGARp(ℓ)=CGARp(ℓ)τp,τp=Mp×Mp==np2−∑gnpg2∑gnpg(npg−1),(4)\mathrm{CGAR}_{p}^{(\ell)}=\frac{\sum_{i,j\in\mathcal{V}_{p}:s_i\ne s_j}\widetilde{\mathcal{A}}_{ij}^{(\ell)}}{\sum_{i\ne j\in\mathcal{V}_{p}:s_i=s_j}\widetilde{\mathcal{A}}_{ij}^{(\ell)}},\qquad\mathrm{nCGAR}_{p}^{(\ell)}=\frac{\mathrm{CGAR}_{p}^{(\ell)}}{\tau_p},\qquad\tau_p=\frac{M_p^{\times}}{M_p^{=}}=\frac{n_p^2-\sum_g n_{pg}^2}{\sum_g n_{pg}(n_{pg}-1)}, \tag*{(4)}

where npgn_{pg} is the number of nodes of group gg in Vp\mathcal{V}_p, np=∑gnpgn_p=\sum_g n_{pg}, and Mp×M_p^{\times} and Mp=M_p^{=} are the numbers of ordered cross-group and within-group pairs of distinct nodes in Vp\mathcal{V}_p. 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 nCGARp=1_p=1, whereas the raw ratio equals τp\tau_p, which is close to G−1G-1 for GG equally sized groups and depends on the composition of the partition otherwise. Accordingly, nCGARp<1_p<1 indicates group-homophilous attention, concentrated on same-group pairs beyond what the composition explains, and nCGARp>1_p>1 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 =1=1 group-neutral in this aggregate sense.

We turn nCGAR into a training signal through a simple correction. Whenever nCGARp(ℓ)<1−ϵ_p^{(\ell)}<1-\epsilon, we multiplicatively boost the cross-group attention entries; conversely, whenever nCGARp(ℓ)>1+ϵ_p^{(\ell)}>1+\epsilon, we boost the within-group entries. The result serves as a target for the encoder’s attention:

Aij(ℓ)∝{A~ij(ℓ)(1+α),if si≠sj, nCGARp(ℓ)<1−ϵA~ij(ℓ)(1+α),if si=sj, nCGARp(ℓ)>1+ϵA~ij(ℓ),otherwise,(5)\mathcal{A}_{ij}^{(\ell)}\propto \begin{cases} \widetilde{\mathcal{A}}_{ij}^{(\ell)}(1+\alpha), & \text{if }s_i\ne s_j,\ \mathrm{nCGAR}_{p}^{(\ell)}<1-\epsilon\\ \widetilde{\mathcal{A}}_{ij}^{(\ell)}(1+\alpha), & \text{if }s_i=s_j,\ \mathrm{nCGAR}_{p}^{(\ell)}>1+\epsilon\\ \widetilde{\mathcal{A}}_{ij}^{(\ell)}, & \text{otherwise,} \end{cases} \tag*{(5)}

after which row renormalization restores stochasticity. As with the DEC target PP in § 3.2, the target A\mathcal{A} 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

Latt=1∣I∣∑(ℓ,p,i)∈IKL(Ap,i(ℓ)∥A~p,i(ℓ)),(6)\mathcal{L}_{\mathrm{att}}=\frac{1}{|\mathcal{I}|}\sum_{(\ell,p,i)\in\mathcal{I}}\mathrm{KL}\left(\mathcal{A}_{p,i}^{(\ell)}\middle\|\widetilde{\mathcal{A}}_{p,i}^{(\ell)}\right), \tag*{(6)}

where Ap,i(ℓ)\mathcal{A}_{p,i}^{(\ell)} is row ii of the attention matrix of partition Vp\mathcal{V}_p at layer ℓ\ell, and I\mathcal{I} 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 ϵ\epsilon 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 [1−ϵ,1+ϵ][1-\epsilon,1+\epsilon], and in Proposition 1 that minimizing Latt\mathcal{L}_{\mathrm{att}} moves the encoder’s own attention in the same direction, with Latt=0\mathcal{L}_{\mathrm{att}}=0 once every partition lies inside the band. Finally, since the corrected attention appears only in the loss, the forward pass in Eq. (3) uses A~\widetilde{A} 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 H(L)H^{(L)} denote the final encoder output and zi=LN⁡(Wzhi(L))∈Rdzz_i=\operatorname{LN}(W_z h_i^{(L)})\in\mathbb{R}^{d_z} 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 {μk}k=1K\{\mu_k\}_{k=1}^{K}, initialized by kk-means on the initial embeddings, the row-stochastic soft assignment matrix C∈Rn×KC\in\mathbb{R}^{n\times K} is computed with a Student’s tt kernel as

Cik=δik−1/∑k′δik′−1,δik=1+∥zi−μk∥22.(7)C_{ik}=\delta_{ik}^{-1}\big/\sum_{k'}\delta_{ik'}^{-1},\qquad\delta_{ik}=1+\lVert z_i-\mu_k\rVert_2^2. \tag*{(7)}

Graph-aware target. Standard DEC sharpens the assignments using only CC and thus ignores the graph. To bring the community structure into the target, we first score each node–cluster pair by its modularity gain,

Mik=∑j∈N(i)Cjk−di2∣E∣∑j=1ndjCjk,N(i)={j:Aij=1},(8)M_{ik}=\sum_{j\in\mathcal{N}(i)}C_{jk}-\frac{d_i}{2\lvert E\rvert}\sum_{j=1}^{n}d_jC_{jk},\qquad\mathcal{N}(i)=\{j:A_{ij}=1\}, \tag*{(8)}

where ∣E∣\lvert E\rvert is the number of edges and N(i)\mathcal{N}(i) the neighborhood of node ii. The first term measures how strongly the neighbors of ii belong to cluster kk, and the second subtracts what a degree-preserving random graph would produce, so that Mik>0M_{ik}>0 means that the neighbors of node ii favor cluster kk beyond random connectivity. To keep these scores on a bounded scale, we center them and apply a parameter-free nonlinearity,

M~ik=tanh⁡(Mik−M‾i),M‾i=1K∑r=1KMir.(9)\widetilde{M}_{ik}=\tanh(M_{ik}-\overline{M}_i),\qquad\overline{M}_i=\frac{1}{K}\sum_{r=1}^{K}M_{ir}. \tag*{(9)}

Under exact row-stochasticity of CC the gains already satisfy ∑kMik=0\sum_k M_{ik}=0, so the centering merely guards against finite-precision drift during training. The graph-aware target then combines DEC confidence with this structural guidance,

Pik=(Cik2/fk)exp⁡(M~ik)∑k′(Cik′2/fk′)exp⁡(M~ik′),fk=∑iCik,(10)P_{ik}=\frac{(C_{ik}^2/f_k)\exp(\widetilde{M}_{ik})}{\sum_{k'}(C_{ik'}^2/f_{k'})\exp(\widetilde{M}_{ik'})},\qquad f_k=\sum_i C_{ik}, \tag*{(10)}

and the clustering loss is Lclust=KL⁡(P∥C)\mathcal{L}_{\mathrm{clust}}=\operatorname{KL}(P\mathbin\Vert C). Following DEC, PP is held fixed during back-propagation and recomputed every TPT_P training steps. Intuitively, when the graph structure is informative, M~ik\widetilde{M}_{ik} sharpens cluster preferences along local modularity gains; when it is weak or homogeneous, the target reduces to standard DEC. Moreover, because M~ik\widetilde{M}_{ik} is bounded, the structural guidance can tip close calls but cannot overturn confident DEC preferences: Theorem 2 shows that PP always stays within a factor e2e^2 of the DEC target.

Group fairness. Next, we turn to the fairness of the assignments. Let p∗(g)={i:p^*(g)=\{i: si=g}∣/ns_i = g\}|/n be the global proportion of group gg, and let p^k(g)=∑i:si=gCik/∑iCik\hat{p}_k(g) = \sum_{i:s_i=g} C_{ik}/\sum_i C_{ik} be its soft proportion in cluster kk. We penalize deviations from statistical parity by the mutual information between cluster and group under the soft assignments,

Lgrp=I(C;S)=∑k=1KcˉkKL⁡(p^k∥p∗),cˉk=1n∑i=1nCik,(11)\mathcal{L}_{\mathrm{grp}} = I(C;S) = \sum_{k=1}^{K} \bar{c}_k \operatorname{KL}(\hat{p}_k \mathbin{\|} p^{*}), \qquad\bar{c}_k = \frac{1}{n}\sum_{i=1}^{n} C_{ik}, \tag*{(11)}

which is zero exactly when every cluster has the global group proportions. Weighting each cluster by its expected size cˉk\bar{c}_k 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 Lgrp=0\mathcal{L}_{\mathrm{grp}} = 0, 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,

Linfo=1n∑i=1nH(Ci)−H(cˉ),(12)\mathcal{L}_{\mathrm{info}} = \frac{1}{n}\sum_{i=1}^{n} H(C_i) - H(\bar{c}), \tag*{(12)}

where H(p)=−∑k=1Kpklog⁡pkH(p) = -\sum_{k=1}^{K} p_k \log p_k is the Shannon entropy (natural logarithm) of a distribution pp over the KK clusters, CiC_i is the assignment vector of node ii, and cˉ=(cˉ1,…,cˉK)\bar{c} = (\bar{c}_1,\ldots,\bar{c}_K) 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, Linfo\mathcal{L}_{\mathrm{info}} always lies between −log⁡K-\log K and 00. It reaches its minimum −log⁡K-\log K only when every node is assigned with certainty and all clusters have equal size, and its maximum 00 exactly when all nodes share the same assignment vector, that is, precisely for the degenerate solutions that satisfy Lgrp\mathcal{L}_{\mathrm{grp}} trivially. In short, Lclust\mathcal{L}_{\mathrm{clust}} and Linfo\mathcal{L}_{\mathrm{info}} 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 Lgrp\mathcal{L}_{\mathrm{grp}}, the mutual information between clusters and groups, and of Latt\mathcal{L}_{\mathrm{att}}.

Final objective. Putting the pieces together, FairPGT minimizes

LFairPGT=Lclust+λgrpLgrp+λattLatt+λinfoLinfo,(13)\mathcal{L}_{\mathrm{FairPGT}} = \mathcal{L}_{\mathrm{clust}} + \lambda_{\mathrm{grp}} \mathcal{L}_{\mathrm{grp}} + \lambda_{\mathrm{att}} \mathcal{L}_{\mathrm{att}} + \lambda_{\mathrm{info}} \mathcal{L}_{\mathrm{info}}, \tag*{(13)}

in which two terms serve clustering quality and two serve fairness: Lclust\mathcal{L}_{\mathrm{clust}} aligns the clusters with the community structure and Linfo\mathcal{L}_{\mathrm{info}} keeps them informative, while Lgrp\mathcal{L}_{\mathrm{grp}} makes the clusters independent of the protected attribute and Latt\mathcal{L}_{\mathrm{att}} keeps the encoder’s attention balanced across groups. Accordingly, λgrp\lambda_{\mathrm{grp}} and λatt\lambda_{\mathrm{att}} control the fairness–utility trade-off at the assignment and attention levels, and λinfo\lambda_{\mathrm{info}} sets the strength of the information term; in addition, α\alpha and ϵ\epsilon set the step size and tolerance of the CGAR target, and the gates γ(ℓ)\gamma^{(\ell)} 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 (A,X)(A,X) alone; the CGAR target A\mathcal{A} and the graph-aware target PP 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 Lgrp\mathcal{L}_{\mathrm{grp}}, both of which belong to the training objective. At inference, the trained model therefore computes CC from (A,X)(A, X) alone. One encoder layer is detailed in Algorithm 2.

Algorithm 2 FairPGT encoder layer ℓ\ell. The layer never receives the protected attribute; it returns its attention matrices so that the CGAR targets can be built during training.

Input: States H(ℓ−1)∈Rn×DH^{(\ell-1)} \in\mathbb{R}^{n \times D}, partitions P={V1,…,VNp}\mathcal{P} = \{\mathcal{V}_1, \ldots, \mathcal{V}_{N_p}\}

Output: States H(ℓ)H^{(\ell)} and partition attention matrices {A~p(ℓ)}\{\widetilde{A}^{(\ell)}_p\}

  1. Normalize the states: Hˉ←LN⁡(H(ℓ−1))\bar{H} \leftarrow\operatorname{LN}(H^{(\ell-1)}) // shared by both branches Local branch: attention within partitions

  2. for each partition Vp∈P\mathcal{V}_p \in\mathcal{P} (in parallel) do

  3. Compute the self-masked attention A~p(ℓ)\widetilde{A}^{(\ell)}_p from Hˉp\bar{H}_p // Eq. (2), per head

  4. Aggregate the values: Op←A~p(ℓ)VpWO(ℓ)O_p \leftarrow\widetilde{A}^{(\ell)}_p V_p W_O^{(\ell)}

  5. end for Global branch: routing tokens

  6. Summarize each partition by a token rpr_p, the mean of its normalized states

  7. Let the tokens exchange information by self-attention, giving R^\hat{R}

  8. Broadcast: every node attends to the tokens, giving its global context gig_i Fusion

  9. Mix local and global outputs with the learned gate γ(ℓ)\gamma^{(\ell)}, then apply the feed-forward block // Eq. (3)

  10. return H(ℓ)H^{(\ell)}, {A~p(ℓ)}\{\widetilde{A}^{(\ell)}_p\}

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 Vp\mathcal{V}_p with at least two groups, attention A~\widetilde{A}, and target AA from Eq. (5). Let qi=∑j:sj≠siA~ijq_i = \sum_{j:s_j \ne s_i} \widetilde{A}_{ij} and qi′=∑j:sj≠siAijq'_i = \sum_{j:s_j \ne s_i} A_{ij} be the cross-group mass of row ii before and after the correction.

(i) If nCGAR⁡(A~)<1−ϵ\operatorname{nCGAR}(\widetilde{A}) < 1 - \epsilon, then qi′=(1+α)qi/(1+αqi)≥qiq'_i = (1 + \alpha)q_i/(1 + \alpha q_i) \ge q_i for every row, with strict inequality whenever qi<1q_i < 1, and nCGAR⁡(A~)<nCGAR⁡(A)≤(1+α)nCGAR⁡(A~)\operatorname{nCGAR}(\widetilde{A}) < \operatorname{nCGAR}(A) \le(1 + \alpha)\operatorname{nCGAR}(\widetilde{A}).

(ii) If nCGAR⁡(A~)>1+ϵ\operatorname{nCGAR}(\widetilde{A}) > 1 + \epsilon, then qi′=qi/(1+α(1−qi))≤qiq'_i = q_i/(1 + \alpha(1 - q_i)) \le q_i for every row, with strict inequality whenever qi<1q_i < 1, and nCGAR⁡(A~)/(1+α)≤nCGAR⁡(A)<nCGAR⁡(A~)\operatorname{nCGAR}(\widetilde{A})/(1 + \alpha) \le\operatorname{nCGAR}(A) < \operatorname{nCGAR}(\widetilde{A}).

(iii) If α≤2ϵ/(1−ϵ)\alpha\le2\epsilon/(1 - \epsilon), the target does not overshoot: whenever the correction is active, nCGAR⁡(A)\operatorname{nCGAR}(A) is strictly closer to the band [1−ϵ,1+ϵ][1 - \epsilon, 1 + \epsilon] than nCGAR⁡(A~)\operatorname{nCGAR}(\widetilde{A}).

Parts (i) and (ii) show that one correction step always moves nCGAR in the right direction, by at most a factor 1+α1 + \alpha. Part (iii) is needed because a large α\alpha could push nCGAR from just below the band to far above it; the condition holds for any α≤ϵ\alpha\le\epsilon, including our setting α=ϵ=0.05\alpha= \epsilon= 0.05.

The theorem concerns the target, whereas training changes the encoder. The next result connects the two.

Proposition 1 (Attention alignment). (i) Latt=0\mathcal{L}_{\mathrm{att}}=0 if and only if nCGAR ∈[1−ϵ,1+ϵ]\in[1-\epsilon,1+\epsilon] for every layer, head, and partition with at least two groups.

(ii) Let A~i=softmax⁡(ai)\widetilde{A}_i=\operatorname{softmax}(a_i) be a row with logits aia_i, and ℓi=KL⁡(Ai∥A~i)\ell_i=\operatorname{KL}(A_i\mathbin{\|}\widetilde{A}_i) with the target AiA_i held fixed. Then ∇aiℓi=A~i−Ai\nabla_{a_i}\ell_i=\widetilde{A}_i-A_i, and if the target boosts cross-group entries, the gradient step ai−η∇aiℓia_i-\eta\nabla_{a_i}\ell_i changes qiq_i at rate

dqidη∣η=0=α1+αqi[(1−qi)2∑j:sj≠siA~ij2+qi2∑j≠i:sj=siA~ij2]≥0,\left.\frac{\mathrm{d}q_i}{\mathrm{d}\eta}\right|_{\eta=0}=\frac{\alpha}{1+\alpha q_i}\left[(1-q_i)^2\sum_{j:s_j\ne s_i}\widetilde{A}_{ij}^{2}+q_i^2\sum_{j\ne i:s_j=s_i}\widetilde{A}_{ij}^{2}\right]\ge0,

with strict inequality whenever qi<1q_i<1; if the target boosts within-group entries, the rate is the same bracket times −α/(1+α(1−qi))≤0-\alpha/(1+\alpha(1-q_i))\le0.

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 Latt\mathcal{L}_{\mathrm{att}} 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 WQW_Q and WKW_K, 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 PikDEC=(Cik2/fk)/∑k′(Cik′2/fk′)P^{\mathrm{DEC}}_{ik}=(C_{ik}^{2}/f_k)/\sum_{k'}(C_{ik'}^{2}/f_{k'}) be the standard DEC target. For every node ii and clusters k,k′k,k', the target PP of Eq. (10) satisfies:

(i) Bounded modulation: e−2PikDEC<Pik<e2PikDECe^{-2}P^{\mathrm{DEC}}_{ik}<P_{ik}<e^{2}P^{\mathrm{DEC}}_{ik}.

(ii) Agreement: Pik/Pik′=(PikDEC/Pik′DEC)exp⁡(M~ik−M~ik′)P_{ik}/P_{ik'}=(P^{\mathrm{DEC}}_{ik}/P^{\mathrm{DEC}}_{ik'})\exp(\widetilde{M}_{ik}-\widetilde{M}_{ik'}). Hence, if Mik>Mik′M_{ik}>M_{ik'} and PikDEC≥Pik′DECP^{\mathrm{DEC}}_{ik}\ge P^{\mathrm{DEC}}_{ik'}, then Pik>Pik′P_{ik}>P_{ik'}; and PP can reverse a DEC preference for kk over k′k' only if PikDEC/Pik′DEC<e2P^{\mathrm{DEC}}_{ik}/P^{\mathrm{DEC}}_{ik'}<e^2 and Mik′>MikM_{ik'}>M_{ik}.

(iii) Reduction to DEC: if MikM_{ik} is the same for all kk, then Pi=PiDECP_i=P_i^{\mathrm{DEC}}.

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 e2≈7.4e^2\approx7.4. 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, D=HdhD=H d_h denotes the width of the encoder with HH heads, and d0d_0 the input dimension of Eq. (1) and dzd_z the dimension of the clustering projection.

Proposition 2 (Complexity of FairPGT). Let the encoder have LL layers of width DD, and let the NpN_p partitions be balanced.

(i) One encoder layer costs O(n2D/Np+nNpD+Np2D+nD2)\mathcal{O}(n^2D/N_p+nN_pD+N_p^2D+nD^2) time.

(ii) One full-batch training step costs O(L(n2D/Np+nNpD+Np2D+nD2)+nd0D+nDdz+nKdz+∣E∣K)\mathcal{O}\left(L\left(n^{2}D/N_{p}+nN_{p}D+N_{p}^{2}D+nD^{2}\right)+nd_{0}D+nDd_{z}+nKd_{z}+|\mathcal{E}|K\right) time and O(LHn2/Np+LHnNp+LnD+∣E∣+nK)\mathcal{O}\left(LHn^{2}/N_{p}+LHnN_{p}+LnD+|\mathcal{E}|+nK\right) memory for activations.

(iii) Inference has the time cost of (ii) without the ∣E∣K|\mathcal{E}|K term and needs O(Hn2/Np+nD)\mathcal{O}(Hn^{2}/N_{p}+nD) memory, since attention matrices can be released layer by layer.

For Np=Θ(n)N_{p}=\Theta(\sqrt{n}), one layer costs O(n3/2D+nD2)\mathcal{O}(n^{3/2}D+nD^{2}) time, compared to O(n2D+nD2)\mathcal{O}(n^{2}D+nD^{2}) for global attention.

In (i), the four terms are local attention within partitions of size np=n/Npn_{p}=n/N_{p}, the broadcast from the NpN_{p} routing tokens to all nn 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 O(∣E∣K)\mathcal{O}(|\mathcal{E}|K) for sparse neighbor aggregation and never forms dense n×nn \times n matrices. In contrast, the CGAR target (Eq. (5)) and Latt\mathcal{L}_{\mathrm{att}} (Eq. (6)) reuse the partition attention matrices that the forward pass has already computed, while Lgrp\mathcal{L}_{\mathrm{grp}} and Linfo\mathcal{L}_{\mathrm{info}} cost O(nK)\mathcal{O}(nK); 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 Np=max⁡(8,⌈n/2500⌉)N_{p}=\max(8,\lceil n/2500\rceil) keeps partitions at about np≤2,500n_{p}\leq2{,}500 nodes, so the local-attention term becomes O(nnpD)\mathcal{O}(nn_{p}D), linear in nn. The broadcast term nNpD=n2D/npnN_{p}D=n^{2}D/n_{p} still grows quadratically, but with the small factor 1/np1/n_{p}: on Pokec-n (Np=27N_{p}=27) 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 1/Np1/N_{p}, until the per-node terms dominate, from 11.9 GB to 0.75 GB on LastFM as NpN_{p} 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 NpN_p (one seed, 50 epochs). Dashed lines in (a) show the ideal 1/Np1/N_p scaling from each dataset’s first feasible point; crosses mark runs that exceed the GPU memory (Facebook and Credit at Np≤2N_p \le2, Pokec at Np≤16N_p \le16).

Proofs of Theoretical Claims

Proof of Theorem 1 (CGAR Target)

Setup. Fix a layer, a head, and a partition Vp\mathcal{V}_{p} with npn_{p} nodes and at least two groups; sis_{i} may take any number of values. Let A~∈Rnp×np\widetilde{A}\in\mathbb{R}^{n_{p}\times n_{p}} be the row-stochastic attention of this partition, whose diagonal is masked, and write j∈c(i)j\in c(i) if sj≠sis_{j}\ne s_{i} and j∈w(i)j\in w(i) if sj=sis_{j}=s_{i} and j≠ij\ne i. The cross-group mass of row ii is qi=∑j∈c(i)A~ijq_{i}=\sum_{j\in c(i)}\widetilde{A}_{ij}, and its within-group mass is 1−qi1-q_{i}. Softmax entries outside the diagonal are positive and c(i)≠∅c(i)\ne\varnothing, so qi∈(0,1]q_{i}\in(0,1], with qi=1q_{i}=1 exactly when node ii 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 qi∈(0,1)q_{i}\in(0,1). Summing over rows,

CGAR⁡(A~)=∑iqi∑i(1−qi),nCGAR⁡(A~)=CGAR⁡(A~)τp.(14)\operatorname{CGAR}(\widetilde{A})=\frac{\sum_i q_i}{\sum_i(1-q_i)}, \qquad n\operatorname{CGAR}(\widetilde{A})=\frac{\operatorname{CGAR}(\widetilde{A})}{\tau_p}. \tag*{(14)}

Since τp>0\tau_p>0 depends only on the group composition of Vp\mathcal{V}_{p}, it suffices to prove all statements for CGAR.

Proof. (i) Correction from below. The target multiplies the cross-group entries of each row by 1+α1+\alpha and renormalizes by Zi=(1−qi)+(1+α)qi=1+αqiZ_i=(1-q_i)+(1+\alpha)q_i=1+\alpha q_i. Hence

qi′=(1+α)qi1+αqi,qi′−qi=αqi(1−qi)1+αqi≥0.q_i'=\frac{(1+\alpha)q_i}{1+\alpha q_i},\qquad q_i'-q_i=\frac{\alpha q_i(1-q_i)}{1+\alpha q_i}\ge0.

with equality only for rows with qi=1q_i=1. Since at least one row has qi<1q_i<1, ∑iqi′>∑iqi\sum_i q_i'>\sum_i q_i; and because ∑i(1−qi)=np−∑iqi\sum_i(1-q_i)=n_p-\sum_iq_i and Q↦Q/(np−Q)Q\mapsto Q/(n_p-Q) is strictly increasing on [0,np)[0,n_p), this gives CGAR⁡(A)>CGAR⁡(A~)\operatorname{CGAR}(\mathcal{A})>\operatorname{CGAR}(\widetilde{\mathcal{A}}).

For the upper bound, let ui=1/Ziu_i=1/Z_i. Then qi′=(1+α)qiuiq_i'=(1+\alpha)q_i u_i and 1−qi′=(1−qi)ui1-q_i'=(1-q_i)u_i, so

CGAR⁡(A)=(1+α)∑iqiui∑i(1−qi)ui.\operatorname{CGAR}(\mathcal{A})=(1+\alpha)\frac{\sum_i q_i u_i}{\sum_i(1-q_i)u_i}.

It remains to show ∑iqiui⋅∑j(1−qj)≤∑iqi⋅∑j(1−qj)uj\sum_iq_i u_i\cdot\sum_j(1-q_j)\le\sum_iq_i\cdot\sum_j(1-q_j)u_j. The difference of the two sides is

∑i,jqi(1−qj)(ui−uj)=12∑i,j(ui−uj)(qi−qj)≤0,\sum_{i,j}q_i(1-q_j)(u_i-u_j)=\frac{1}{2}\sum_{i,j}(u_i-u_j)(q_i-q_j)\le0,

where the equality follows by adding the expression to itself with ii and jj exchanged, and the inequality holds because ui=1/(1+αqi)u_i=1/(1+\alpha q_i) is decreasing in qiq_i. Therefore CGAR⁡(A)≤(1+α)CGAR⁡(A~)\operatorname{CGAR}(\mathcal{A})\le(1+\alpha)\operatorname{CGAR}(\widetilde{\mathcal{A}}), with equality when all qiq_i are equal.

(ii) Correction from above. The within-group entries are multiplied by 1+α1+\alpha, so Zi=1+α(1−qi)Z_i=1+\alpha(1-q_i) and qi′=qi/(1+α(1−qi))<qiq_i'=q_i/(1+\alpha(1-q_i))<q_i. Exchanging the roles of qiq_i and 1−qi1-q_i in (i) gives 1/CGAR⁡(A~)<1/CGAR⁡(A)≤(1+α)/CGAR⁡(A~)1/\operatorname{CGAR}(\widetilde{\mathcal{A}})<1/\operatorname{CGAR}(\mathcal{A})\le(1+\alpha)/\operatorname{CGAR}(\widetilde{\mathcal{A}}), which is the claim.

(iii) No overshoot. Let x=nCGAR⁡(A~)x=n\operatorname{CGAR}(\widetilde{\mathcal{A}}) and y=nCGAR⁡(A)y=n\operatorname{CGAR}(\mathcal{A}). The condition α≤2ϵ/(1−ϵ)\alpha\le2\epsilon/(1-\epsilon) is equivalent to both (1+α)(1−ϵ)≤1+ϵ(1+\alpha)(1-\epsilon)\le1+\epsilon and (1+ϵ)/(1+α)≥1−ϵ(1+\epsilon)/(1+\alpha)\ge1-\epsilon. If x<1−ϵx<1-\epsilon, then by (i) x<y<(1+α)(1−ϵ)≤1+ϵx<y<(1+\alpha)(1-\epsilon)\le1+\epsilon: yy moves toward the band and does not leave it on the other side, so its distance to the band, max⁡(0,1−ϵ−y)\max(0,1-\epsilon-y), is strictly smaller than 1−ϵ−x1-\epsilon-x. The case x>1+ϵx>1+\epsilon is symmetric by (ii). If x∈[1−ϵ,1+ϵ]x\in[1-\epsilon,1+\epsilon], the target equals A~\widetilde{\mathcal{A}}.

Remark 1 (Repeated correction). Applying the correction tt times multiplies the cross-group entries by (1+α)t(1+\alpha)^t before a single renormalization, so each qi→1q_i\to1 and nCGAR⁡→∞n\operatorname{CGAR}\to\infty as t→∞t\to\infty (and nCGAR⁡→0n\operatorname{CGAR}\to0 in the symmetric case). Starting outside the band, nCGAR⁡n\operatorname{CGAR} 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 Latt\mathcal{L}_{\mathrm{att}} is a KL divergence and is therefore nonnegative, and it is zero if and only if Ai=A~iA_i=\widetilde{A}_i. 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), qi′≠qiq_i'\ne q_i for every row with qi<1q_i<1, and at least one such row exists; hence Ai≠A~iA_i\ne\widetilde{A}_i for that row, and it contributes a positive term. Partitions with a single group are not in I\mathcal{I}.

(ii) Write σ=softmax⁡(ai)=A~i\sigma=\operatorname{softmax}(a_i)=\widetilde{A}_i and t=Ait=A_i. Since tt is constant and sums to one,

ℓi=∑jtjlog⁡tj−∑jtjaj+log⁡∑keak,∇aiℓi=σ−t.\ell_i=\sum_j t_j\log t_j-\sum_j t_j a_j+\log\sum_k e^{a_k},\qquad\nabla_{a_i}\ell_i=\sigma-t.

The gradient step changes the logits by η(t−σ)\eta(t-\sigma). The cross-group mass qi=∑j∈c(i)σjq_i=\sum_{j\in c(i)}\sigma_j has partial derivatives ∂qi/∂ak=σk(I[k∈c(i)]−qi)\partial q_i/\partial a_k=\sigma_k(\mathbb{I}[k\in c(i)]-q_i), so

dqidη∣η=0=(1−qi)∑j∈c(i)σj(tj−σj)−qi∑j∈w(i)σj(tj−σj).\left.\frac{dq_i}{d\eta}\right|_{\eta=0}=(1-q_i)\sum_{j\in c(i)}\sigma_j(t_j-\sigma_j)-q_i\sum_{j\in w(i)}\sigma_j(t_j-\sigma_j).

When cross-group entries are boosted, the target of Theorem 1(i) gives tj−σj=σjα(1−qi)/(1+αqi)t_j-\sigma_j=\sigma_j\alpha(1-q_i)/(1+\alpha q_i) for j∈c(i)j\in c(i) and tj−σj=−σjαqi/(1+αqi)t_j-\sigma_j=-\sigma_j\alpha q_i/(1+\alpha q_i) for j∈w(i)j\in w(i). Substituting gives the stated rate, which is positive since qi∈(0,1)q_i\in(0,1) and both sums contain positive terms. When within-group entries are boosted, tj−σj=−σjα(1−qi)/(1+α(1−qi))t_j-\sigma_j=-\sigma_j\alpha(1-q_i)/(1+\alpha(1-q_i)) for j∈c(i)j\in c(i) and tj−σj=σjαqi/(1+α(1−qi))t_j-\sigma_j=\sigma_j\alpha q_i/(1+\alpha(1-q_i)) for j∈w(i)j\in w(i), which gives the same bracket with factor −α/(1+α(1−qi))-\alpha/(1+\alpha(1-q_i)).

Proof of Theorem 2 (Graph-Aware Target)

Proof. Let δik=Mik−M‾i\delta_{ik}=M_{ik}-\overline{M}_i, so that M~ik=tanh⁡(δik)∈(−1,1)\widetilde{M}_{ik}=\tanh(\delta_{ik})\in(-1,1) and eM~ik∈(e−1,e)e^{\widetilde{M}_{ik}}\in(e^{-1},e). Student-t assignments are positive, so PikDEC>0P^{\mathrm{DEC}}_{ik}>0. Dividing the numerator and denominator of Eq. (10) by ∑k′Cik′2/fk′\sum_{k'}C_{ik'}^2/f_{k'} gives

Pik=PikDECeM~ik∑k′Pik′DECeM~ik′.(15)P_{ik}=\frac{P^{\mathrm{DEC}}_{ik}e^{\widetilde{M}_{ik}}}{\sum_{k'}P^{\mathrm{DEC}}_{ik'}e^{\widetilde{M}_{ik'}}}. \tag*{(15)}

(i) The denominator of Eq. (15) is a convex combination of values in (e−1,e)(e^{-1},e) and therefore lies in (e−1,e)(e^{-1},e). Hence Pik/PikDEC=eM~ik/∑k′Pik′DECeM~ik′∈(e−2,e2)P_{ik}/P^{\mathrm{DEC}}_{ik}=e^{\widetilde{M}_{ik}}/\sum_{k'}P^{\mathrm{DEC}}_{ik'}e^{\widetilde{M}_{ik'}}\in(e^{-2},e^2).

(ii) The ratio follows from Eq. (15), since the denominator does not depend on kk. Centering subtracts the same M‾i\overline{M}_i from MikM_{ik} and Mik′M_{ik'}, and tanh⁡\tanh is strictly increasing, so M~ik−M~ik′\widetilde{M}_{ik}-\widetilde{M}_{ik'} has the sign of Mik−Mik′M_{ik}-M_{ik'} and lies in (−2,2)(-2,2). If Mik>Mik′M_{ik}>M_{ik'} and PikDEC≥Pik′DECP^{\mathrm{DEC}}_{ik}\ge P^{\mathrm{DEC}}_{ik'}, both factors of the ratio are at least 1 and the second is larger than 1, so Pik>Pik′P_{ik}>P_{ik'}. If PikDEC≥Pik′DECP^{\mathrm{DEC}}_{ik}\ge P^{\mathrm{DEC}}_{ik'} but Pik′>PikP_{ik'}>P_{ik}, then PikDEC/Pik′DEC<exp⁡(M~ik′−M~ik)<e2P^{\mathrm{DEC}}_{ik}/P^{\mathrm{DEC}}_{ik'}<\exp(\widetilde{M}_{ik'}-\widetilde{M}_{ik})<e^2, and the exponent is positive, so Mik′>MikM_{ik'}>M_{ik}.

(iii) If MikM_{ik} is the same for all kk, then δik=0\delta_{ik}=0 and eM~ik=1e^{\widetilde{M}_{ik}}=1 for all kk, and Eq. (15) reduces to PikDECP^{\mathrm{DEC}}_{ik}.

Remark 2 (Centering). For row-stochastic CC, ∑kMik=∑jAij∑kCjk−di2∣E∣∑jdj∑kCjk=di−di=0\sum_k M_{ik}=\sum_j A_{ij}\sum_k C_{jk}-\frac{d_i}{2|E|}\sum_jd_j\sum_kC_{jk}=d_i-d_i=0, using ∑jdj=2∣E∣\sum_jd_j=2|E|. Hence M‾i=0\overline{M}_i=0 and M~ik=tanh⁡(Mik)\widetilde{M}_{ik}=\tanh(M_{ik}); the explicit centering only guards against numerical drift. In the case of (iii), all gains of node ii 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, np=n/Npn_p=n/N_p, and D=HdhD=Hd_h.

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 O(D)O(D) cost O(nD2)O(nD^2). Local attention: in each partition and head, QpKp⊤Q_pK_p^\top and the product with VpV_p cost O(np2dh)O(n_p^2d_h); over HH heads and NpN_p partitions, this gives NpH O(n2dh/Np2)=O(n2D/Np)N_pH\,O(n^2d_h/N_p^2)=O(n^2D/N_p). Routing tokens: mean pooling into NpN_p tokens costs O(nD)O(nD); self-attention among the tokens costs O(Np2D)O(N_p^2D), plus O(NpD2)O(N_pD^2) for their projections, which is dominated by O(nD2)O(nD^2); and the broadcast, in which each node attends to all NpN_p tokens, costs O(nNpD)\mathcal{O}(nN_pD). Gate, residuals, and normalization: these cost O(nD)\mathcal{O}(nD). Summing all terms gives (i).

(ii) Training step. The input embedding costs O(nd0D)\mathcal{O}(nd_0D), and the LL layers cost LL times (i). The projection zi=LN⁡(Wzhi)z_i = \operatorname{LN}(W_z h_i) costs O(nDdz)\mathcal{O}(nDd_z), and the DEC assignments cost O(nKdz)\mathcal{O}(nK d_z). In Eq. (8), the neighbor term ∑j∈N(i)Cjk\sum_{j\in\mathcal{N}(i)} C_{jk} for all i,ki,k is a sparse–dense product costing O(∣E∣K)\mathcal{O}(|\mathcal{E}|K), and the null-model term needs the KK sums ∑jdjCjk\sum_j d_j C_{jk} only once, so it costs O(nK)\mathcal{O}(nK); centering, tanh, and the normalization in Eq. (10) also cost O(nK)\mathcal{O}(nK). The losses Lclust\mathcal{L}_{\mathrm{clust}}, Lgrp\mathcal{L}_{\mathrm{grp}}, and Linfo\mathcal{L}_{\mathrm{info}} each cost O(nK)\mathcal{O}(nK); for Lgrp\mathcal{L}_{\mathrm{grp}}, each node adds its row of CC to the column of its group. The CGAR target and Latt\mathcal{L}_{\mathrm{att}} need two passes over each partition attention matrix, O(Hn2/Np)\mathcal{O}(Hn^2/N_p) per layer, which is dominated by local attention since H≤DH \le D. For memory, back-propagation stores the partition attention matrices, O(Hn2/Np)\mathcal{O}(Hn^2/N_p) per layer, the broadcast attention, O(HnNp)\mathcal{O}(HnN_p) per layer, and the node activations, O(nD)\mathcal{O}(nD) per layer, while the graph and the matrices CC and PP need O(∣E∣+nK)\mathcal{O}(|\mathcal{E}| + nK).

(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 O(Hn2/Np+nD)\mathcal{O}(Hn^2/N_p + nD).

Choice of NpN_p. Balancing the local-attention term n2D/Npn^2D/N_p against the broadcast term nNpDnN_pD gives Np=nN_p = \sqrt{n}, for which both are n3/2Dn^{3/2}D and the token self-attention is nDnD. One layer then costs O(n3/2D+nD2)\mathcal{O}(n^{3/2}D + nD^2), compared to O(n2D+nD2)\mathcal{O}(n^2D + nD^2) for global attention.

Example. On Pokec-n (n=66,569n = 66{,}569), our default gives Np=27N_p = 27 partitions of about 2,470 nodes, so the partition attention matrices of one head in one layer hold about 27⋅2,4702≈1.6×10827 \cdot2{,}470^2 \approx1.6 \times10^8 entries, compared to n2≈4.4×109n^2 \approx4.4 \times10^9 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 (≤18\le18, 19–25, 26–35, >35> 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.

DatasetNN∣E∣|E|ddKKGGMaj.hSh_ShYh_YCCProtected attributeLabel
NBA39110,416952273.7%0.730.511Nationality (US / non-US)Salary class (majority vs. rest)
German1,0007,156392269.0%0.780.641GenderGood / bad credit
LastFM5,46519,0241286253.1%0.730.9216Synthetic (feature kk-means)Country (6)
Facebook22,470170,8234,7144260.1%0.640.891Synthetic (feature kk-means)Page type (4)
Credit30,000137,377122254.5%0.650.64120Marital statusDefault next month
Pokec-n66,569517,0471282446.2%0.580.75226Age (4 bins)Working field (majority vs. rest)
Pokec-z67,796617,9581282447.1%0.610.73170Age (4 bins)Working field (majority vs. rest)
SBM (a∈[0,1]a \in[0, 1])2,00011,925324250.0–69.7%0.56–0.820.731Planted, aligned by aaPlanted community

Table 2. Dataset statistics. NN: nodes; ∣E∣|E|: undirected edges; dd: feature dimension; KK: label classes (number of clusters); GG: protected groups; Maj.: share of the largest group; hSh_S, hYh_Y: 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 kk-means (k=2k = 2) 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 (hS=0.73h_S = 0.73 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 n=2000n = 2000 nodes, K=4K = 4 equal communities, and two groups. A node in community kk belongs to group k mod 2k \bmod2 with probability aa and otherwise follows the population share (minority 0.3), so the alignment aa 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 A+(τ/n)11⊤A + (\tau/n)11^{\top} [58], τ\tau the mean degree, because the leading eigenvectors of graphs with many connected components (LastFM, Credit, Pokec) are otherwise component indicators, and kk-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 kk-center and kk-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 clusteringFair deepFair spectralOurs
DMoNSDCNCCGCSCGCDinkNetDiffPoolMinCutPoolDMoN-SPFairGCFairGTFairGPsFairSCiFairSCFairPGT
NBANMI↑.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
ΔSP_{\mathrm{SP}}↓.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
GermanNMI↑.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
ΔSP_{\mathrm{SP}}↓.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
LastFMNMI↑.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
ΔSP_{\mathrm{SP}}↓.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
FacebookNMI↑.196±.08.080±.18†.054±.01.113±.05.053±.04.068±.04†.195±.06.192±.08.010±.01.095±.04.085±.02.118±.00n/s.057±.01
ΔSP_{\mathrm{SP}}↓.124±.06.025±.06†.133±.04.204±.08.214±.11.329±.12†.238±.06.110±.05.063±.02.519±.09.106±.03.468±.00n/s.027±.01
CreditNMI↑.010±.01.009±.00.013±.01.013±.01.012±.01.015±.01.008±.00.010±.01n/s.022±.01.012±.01.002±.00†n/s.042±.05
ΔSP_{\mathrm{SP}}↓.018±.00.014±.00.010±.00.024±.01.014±.01.012±.01.010±.00.018±.00n/s.010±.00.013±.01.030±.00†n/s.003±.00
Pokec-nNMI↑.001±.00.020±.00OOMOOM.011±.00†n/sn/s.001±.00n/s.072±.01.009±.01.003±.00n/s.098±.01
ΔSP_{\mathrm{SP}}↓.054±.00.118±.01OOMOOM.102±.03†n/sn/s.053±.00n/s.023±.01.093±.03.113±.00n/s.006±.00
Pokec-zNMI↑.001±.00.018±.00OOMOOM.015±.00†n/sn/s.001±.00n/s.062±.04.007±.01.001±.00n/s.106±.01
ΔSP_{\mathrm{SP}}↓.056±.01.145±.01OOMOOM.143±.02†n/sn/s.057±.00n/s.019±.01.075±.05.141±.00n/s.005±.00

Table 3. Clustering quality (NMI) and group fairness (ΔSP\Delta_{\mathrm{SP}}) 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 KK 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 nn); 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. KK 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 nn are skipped above a size limit (DiffPool and MinCutPool above 5×1045 \times10^{4} nodes, FairGC above 2.5×1042.5 \times10^{4}, iFairSC above 8×1038 \times10^{3}) 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 KK 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 QQ [2], which measures community structure without labels. For fairness, we report the statistical-parity gap [8] of the hard clustering,

ΔSP=max⁡kmax⁡g∣Pr⁡(s=g∣c=k)−Pr⁡(s=g)∣,(16)\Delta_{\mathrm{SP}} = \max_{k}\max_{g}\left|\Pr(s=g \mid c=k)-\Pr(s=g)\right|, \tag*{(16)}

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 QQ, and lower is better (↓) for ΔSP\Delta_{\mathrm{SP}}. 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 SS-probe, measures how much of the protected attribute remains in the node embeddings: a logistic-regression probe [62] is trained to predict sis_i from ziz_i, 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 1/G1/G (0.5 for two groups) means that SS 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 Np=max⁡(8,⌈n/2500⌉)N_p = \max(8, \lceil n/2500 \rceil) METIS partitions. Input features are standardized, and cluster centres are initialized by kk-means on the initial embeddings. The CGAR target uses α=ϵ=0.05\alpha= \epsilon= 0.05, the graph-aware target is refreshed every TP=5T_P = 5 epochs, and the loss weights are λgrp=10\lambda_{\mathrm{grp}} = 10, λatt=1\lambda_{\mathrm{att}} = 1, and λinfo=1\lambda_{\mathrm{info}} = 1. We train with Adam [65] (learning rate 5×10−45 \times10^{-4}, weight decay 10−510^{-5}, 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 ΔSP\Delta_{\mathrm{SP}} 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–ΔSP\Delta_{\mathrm{SP}} plane, together with FairPGT trained without its fairness terms.

Deep graph clusteringFair deepFair spectralOurs
DatasetMetricDMoNSDCNCCGCSCGCDinkNetDiffPoolMinCutPoolDMoN-SPFairGCFairGTFairGPsFairSCiFairSCFairPGT
NBAF1↑.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
NBAQ↑.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
GermanF1↑.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
GermanQ↑.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
LastFMF1↑.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
LastFMQ↑.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
FacebookF1↑.493±.08.196±.18†.369±.01.416±.06.276±.06.274±.04†.449±.06.493±.08.288±.02.389±.04.375±.03.253±.00n/s.373±.02
FacebookQ↑.648±.01.107±.24†.556±.02.568±.03.376±.13.350±.12†.606±.03.648±.02.208±.06.396±.11.596±.02.409±.00n/s.592±.02
CreditF1↑.468±.05.477±.02.507±.02.514±.04.489±.05.497±.05.494±.01.468±.05n/s.527±.02.505±.03.452±.00†n/s.536±.12
CreditQ↑.462±.00.472±.01.414±.03.374±.02.412±.07.393±.04.443±.01.462±.00n/s.382±.04.440±.02.236±.00†n/s.368±.09
Pokec-nF1↑.428±.01.445±.03OOMOOM.459±.00†n/sn/s.431±.00n/s.525±.00.448±.03.525±.00n/s.453±.06
Pokec-nQ↑.411±.00.186±.01OOMOOM.004±.00†n/sn/s.411±.00n/s.012±.01.266±.07.320±.00n/s.059±.03
Pokec-zF1↑.434±.01.443±.03OOMOOM.451±.00†n/sn/s.432±.01n/s.529±.03.451±.03.517±.00n/s.491±.01
Pokec-zQ↑.440±.00.167±.02OOMOOM.002±.00†n/sn/s.441±.00n/s.014±.01.298±.11.354±.00n/s.053±.02

Table 4. Complementary quality metrics: macro-F1 against the labels and modularity QQ 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 KK clusters used, or one cluster holding over 90% of the nodes, in at least half of the runs). n/sn/s: not scalable, skipped (memory quadratic or cubic in nn); 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 λgrp∈{0,0.1,0.3,1,3,10}\lambda_{\mathrm{grp}} \in\{0, 0.1, 0.3, 1, 3, 10\} on NBA, German and LastFM. (h) SBM at full alignment; the diamond is the best NMI any clustering with ΔSP=0\Delta_{\mathrm{SP}} = 0 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 ΔSP\Delta_{\mathrm{SP}}. On Pokec-n and Pokec-z, its ΔSP\Delta_{\mathrm{SP}} 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 (Q=0.41Q = 0.41), but its clusters are unrelated to the labels (NMI 0.001) and differ by group (ΔSP=0.054\Delta_{\mathrm{SP}} = 0.054). FairPGT, in contrast, trades modularity (Q=0.06Q = 0.06, 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 ΔSP=0.399\Delta_{\mathrm{SP}} = 0.399. These are therefore the graphs where fairness costs the most, and FairPGT pays this price openly. It reduces ΔSP\Delta_{\mathrm{SP}} tenfold on LastFM (0.399 →\to 0.040) and more than fourfold on Facebook (0.124 →\to 0.027), while keeping NMI at 0.289 and 0.057. Among the methods that reach ΔSP≤0.05\Delta_{\mathrm{SP}} \le0.05 without collapsing, FairPGT has the highest NMI on both graphs; the only fairer method on LastFM, iFairSC (ΔSP=0.029\Delta_{\mathrm{SP}} = 0.029), 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 ΔSP\Delta_{\mathrm{SP}} (0.011 vs. 0.016). On German, no method recovers the labels (NMI ≤0.013\le0.013 for all), so German measures fairness only; here too, sFairSC has the lowest ΔSP\Delta_{\mathrm{SP}} (0.006).

Summary. Taken together, in mean NMI and ΔSP\Delta_{\mathrm{SP}}, 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 (ΔSP\Delta_{\mathrm{SP}} 0.39–0.45), and sFairSC, although it enforces exact parity on the relaxed problem, reaches ΔSP\Delta_{\mathrm{SP}} 0.37–0.47 on LastFM and Facebook after kk-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

t-SNE plots of node embeddings for LastFM and SBM, comparing DMoN, sFairSC, FairGP, FairPGT without fairness terms, and FairPGT (ours)

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 ΔSP\Delta_{\mathrm{SP}} 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 kk-means on this embedding yields ΔSP=0.37\Delta_{\mathrm{SP}} = 0.37.

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 aa moves from groups that are independent of the communities (a=0a = 0) to groups that coincide with them (a=1a = 1), 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 a=1a = 1, K=4K = 4 equal communities YY, and S=Y mod 2S = Y \bmod2. Every clustering CC with ΔSP=0\Delta_{\mathrm{SP}} = 0 satisfies NMI(C,Y)≤2/3(C, Y) \le2/3 (arithmetic normalization), with equality for the pairing {0,1},{2,3}\{0, 1\}, \{2, 3\}.

Proof. ΔSP=0\Delta_{\mathrm{SP}} = 0 means CC is independent of SS, so H(S∣C)=H(S)=1H(S \mid C) = H(S) = 1 bit. Since SS is a function of YY, H(Y∣C)≥H(S∣C)=1H(Y \mid C) \ge H(S \mid C) = 1, hence I(C;Y)=H(Y)−H(Y∣C)≤2−1=1I(C;Y) = H(Y) - H(Y \mid C) \le2 - 1 = 1. Also H(C)≥I(C;Y)H(C) \ge I(C;Y). With NMI=2I/(H(Y)+H(C))≤2I/(2+I)\mathrm{NMI} = 2I/(H(Y) + H(C)) \le2I/(2 + I), which increases in II, the bound is 2/32/3 at I=1I = 1. The pairing {0,1},{2,3}\{0,1\}, \{2,3\} is independent of SS and has I=H(C)=1I = H(C) = 1.

Figure 5 shows the results. At a=0a = 0, all methods recover the communities (NMI≥0.92\mathrm{NMI} \ge0.92) and are fair (ΔSP≈0.035\Delta_{\mathrm{SP}} \approx0.035, the sampling noise of the generator). As aa 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 ΔSP\Delta_{\mathrm{SP}} rises almost linearly to 0.50; sFairSC follows the same trend (0.48 at a=1a = 1). FairPGT, by contrast, keeps ΔSP≤0.081\Delta_{\mathrm{SP}} \le0.081 at every alignment and reaches 0.002 at a=1a = 1. Its NMI falls to 0.57 at a=0.75a = 0.75 and recovers to 0.646 at a=1a = 1, 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 KK 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 aa (mean, shaded ±\pm one std over three seeds). (a) The diamond marks the NMI bound of Proposition 3 at a=1a = 1. (c) nCGAR of the trained encoder (log scale; shaded band: 1±0.051 \pm0.05); DMoN-SP and sFairSC have no attention. (d) SS-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 a=1a = 1, it is strongly group-homophilous (nCGAR 0.29), and the group can be read off the embeddings perfectly (SS-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 a=0.75a = 0.75 and 3.7 at a=1a = 1), 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 a=1a = 1) but leaves ΔSP\Delta_{\mathrm{SP}} 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 a=0.75a = 0.75 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 a=0.75a = 0.75 (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 a=0.75a = 0.75, 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 a=1a = 1, against 0.62 without fairness terms (the maximum for two groups is log⁡2≈0.69\log2 \approx0.69). 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 Latt\mathcal{L}_{\mathrm{att}} and w/o Lgrp\mathcal{L}_{\mathrm{grp}} remove one fairness term, w/o both fairness terms removes both; DEC target instead of PP 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 Linfo\mathcal{L}_{\mathrm{info}} 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 (Lgrp\mathcal{L}_{\mathrm{grp}}) is what makes the clusters fair. Removing it raises ΔSP\Delta_{\mathrm{SP}} on every dataset except Credit, where it is already 0.007: LastFM 0.034 →\to 0.286, German 0.032 →\to 0.132, Facebook 0.028 →\to 0.082, NBA 0.020 →\to 0.075, and Pokec-n 0.007 →\to 0.034. Without it, FairPGT is a capable but unfair clustering method.

  • The attention term (Latt\mathcal{L}_{\mathrm{att}}), in contrast, shapes the encoder, not the outcome. Removing it changes NMI and ΔSP\Delta_{\mathrm{SP}} 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 (PP) 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 ΔSP\Delta_{\mathrm{SP}} 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 →\to 0.00) and drops on Pokec (0.10 →\to 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 (ΔSP\Delta_{\mathrm{SP}} 0.034 →\to 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], K∥c∥22−1\sqrt{K}\lVert c\rVert_{2}^{2}-1, which constrains only the cluster sizes and, unlike Linfo\mathcal{L}_{\mathrm{info}}, is already minimal when all nodes share the uniform assignment. To test whether our choice matters, we replace Linfo\mathcal{L}_{\mathrm{info}} with this regularizer and keep everything else fixed. The replacement lowers NMI on NBA (0.09 →\to 0.06) and Pokec (0.10 →\to 0.06–0.08), and triples ΔSP\Delta_{\mathrm{SP}} on LastFM (0.034 →\to 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 λgrp\lambda_{\mathrm{grp}} is the main control of the trade-off (three seeds per value; red line in Figure 3). On LastFM, small weights (λgrp≤0.3\lambda_{\mathrm{grp}} \le0.3) leave the gap almost unchanged, and from λgrp=1\lambda_{\mathrm{grp}} = 1 upward ΔSP\Delta_{\mathrm{SP}} falls steadily, from 0.260 at 1 to 0.125 at 3 and 0.035 at 10, while NMI decreases from 0.362 at λgrp=0\lambda_{\mathrm{grp}} = 0 to 0.288. On NBA, by contrast, fairness costs no measurable accuracy: ΔSP\Delta_{\mathrm{SP}} 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: λatt∈[0,10]\lambda_{\mathrm{att}} \in[0, 10] changes neither NMI nor ΔSP\Delta_{\mathrm{SP}} beyond seed variation (LastFM: NMI 0.285–0.301, ΔSP\Delta_{\mathrm{SP}} 0.032–0.048), in line with its role of shaping the encoder rather than the outcome. Finally, λinfo\lambda_{\mathrm{info}} is best kept moderate: without it (λinfo=0\lambda_{\mathrm{info}} = 0), the gap on LastFM more than doubles (0.042 →\to 0.098), while at λinfo=3\lambda_{\mathrm{info}} = 3 NMI on LastFM drops to 0.228, so values in [0.3, 1] balance the two.

Partitions. Figure 8 varies the number of partitions NpN_p (one seed, 50 epochs). As predicted by Proposition 2, peak memory follows 1/Np1/N_p closely at small NpN_p and flattens once the per-node terms dominate: it falls from 11.9 GB to 0.75 GB on LastFM (Np=1→64N_p = 1 \to64), from 50 GB to 5.5 GB on Facebook, and from 88 GB to 8.1 GB on Credit (Np=4→64N_p = 4 \to64), while Pokec does not fit at Np≤16N_p \le16 and fits from Np=32N_p = 32 (our default Np=27N_p = 27 needs 72 GB, Table 5). Time per epoch falls accordingly, by up to 7×7\times. Importantly, restricting attention to partitions does not cost quality: on LastFM, NMI even rises with NpN_p, from 0.16 at Np=1N_p = 1 to 0.34–0.38 at Np≥32N_p \ge32, and on Facebook, Credit, and Pokec it changes by at most 0.04.

MethodNBAGermanLastFMFacebookCreditPokec-nPokec-z
DMoN0.7 / 0.030.7 / 0.030.7 / 0.262.1 / 4.514.6 / 7.241.0 / 0.741.2 / 0.86
SDCN3.2 / 0.413.1 / 0.346.9 / 1.0474.0 / 18.6116.1 / 9.4852.8 / 19.8360.4 / 23.14
CCGC1.0 / 0.070.9 / 0.061.6 / 0.8719.4 / 14.6710.4 / 25.36––
SCGC6.6 / 0.0315.1 / 0.0685.8 / 1.04601.4 / 17.32228.8 / 29.18––
DinkNet1.3 / 0.071.2 / 0.062.1 / 0.428.7 / 6.7412.7 / 11.0856.8 / 36.0359.3 / 37.37
DiffPool0.7 / 0.020.6 / 0.051.7 / 0.9810.3 / 16.6617.2 / 28.89––
MinCutPool1.1 / 0.031.2 / 0.044.2 / 0.5171.3 / 8.6194.2 / 14.51––
DMoN-SP1.0 / 0.031.0 / 0.031.5 / 0.261.8 / 4.552.9 / 7.242.0 / 0.741.3 / 0.86
FairGC1.4 / 0.041.3 / 0.1025.6 / 2.04752.5 / 33.25–––
FairGT1.9 / 0.071.6 / 0.062.5 / 0.264.7 / 4.513.6 / 7.248.1 / 2.679.3 / 3.17
FairGP1.7 / 0.031.7 / 0.032.4 / 0.263.9 / 4.558.8 / 7.248.9 / 3.639.7 / 4.21
sFairSC0.0 / 0.000.2 / 0.000.2 / 0.123.3 / 2.446.7 / 3.605.4 / 0.035.1 / 0.04
iFairSC0.2 / 0.020.7 / 0.0256.2 / 0.14––––
FairPGT5.8 / 0.124.5 / 0.209.5 / 1.9237.8 / 24.9243.3 / 32.6994.1 / 71.5693.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 NpN_p, 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 NpN_p: 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, NpN_p, 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 (Q=0.06Q = 0.06 vs. 0.410.41) 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 G=8G = 8). 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. [1]S. Fortunato, D. Hric, Community detection in networks: A user guide, Physics reports 659 (2016) 1–44.DOI
  2. [2]M. E. Newman, Modularity and community structure in networks, PNAS 103 (23) (2006) 8577–8582.pubmed.ncbi.nlm.nih.gov/16723398
  3. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [40]C. Gkartzios, E. Pitoura, P. Tsaparas, Modularity-fair deep community detection, in: ICDM, IEEE, 2025, pp. 287–296.DOI
  41. [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. [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. [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. [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. [45]C. Gkartzios, E. Pitoura, P. Tsaparas, Fair network communities through group modularity, in: WWW, ACM, 2025, pp. 506–517.DOI
  46. [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. [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. [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. [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. [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. [51]R. Gomes, A. Krause, P. Perona, Discriminative clustering by regularized information maximization, in: NIPS, Curran Associates, Inc., 2010, pp. 775–783.
  52. [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. [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. [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. [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. [56]E. Abbe, Community detection and stochastic block models: Recent developments, J. Mach. Learn. Res. 18 (2017) 177:1–177:86.
  57. [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. [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. [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. [60]M. Sokolova, G. Lapalme, A systematic analysis of performance measures for classification tasks, Inf. Process. Manag. 45 (4) (2009) 427–437.DOI
  61. [61]H. W. Kuhn, The hungarian method for the assignment problem, in: 50 Years of Integer Programming, Springer, 2010, pp. 29–47.
  62. [62]G. Alain, Y. Bengio, Understanding intermediate layers using linear classifier probes, ICLR (Workshop) (2017).arxiv.org/abs/1610.01644
  63. [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. [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. [65]D. P. Kingma, J. Ba, Adam: A method for stochastic optimization, ICLR (Poster) (2015).arxiv.org/abs/1412.6980

Paper details

vlnc:W_xpvtnpue
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents