Organizations: L3S Research Center, Hannover, Germany · Leibniz University Hannover, Hannover, Germany · Department of Mathematics and Informatics, Free University Berlin, Berlin, Germany · Department of Mathematics and Operational Research, University of Mons, Mons, Belgium · TIB – Leibniz Information Centre for Science and Technology, Hannover, Germany · Research Institute CODE, University of the Bundeswehr Munich, Munich, Germany
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.
Figures & tables
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 k -means ( K=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.
Figure 2: FairPGT Pipeline: (a) Structural encodings augment the node features, partitioned transformer layers produce embeddings, and a DEC-style head outputs soft assignments C . The objective combines two quality terms, the graph-aware target P and the information term, with two fairness terms: Lgrp on the assignments and Latt , 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.
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} on NBA, German and LastFM. (h) SBM at full alignment; the diamond is the best NMI any clustering with ΔSP=0 can reach (Proposition 3 ). Collapsed runs on the real graphs are omitted.
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 of the plotted run.
Figure 5: SBMs with community–group alignment a (mean, shaded ± one std over three seeds). (a) The diamond marks the NMI bound of Proposition 3 at a=1 . (c) nCGAR of the trained encoder (log scale; shaded band: 1±0.05 ); DMoN-SP and sFairSC have no attention. (d) S -probe: 0.5 means the group cannot be decoded from the embeddings.
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.75 (the whole partition of 250 nodes). Bottom: LastFM (a stratified sample of 400 of the 682 nodes of the partition). Seed 0.
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 and w/o Lgrp remove one fairness term, w/o both fairness terms removes both; DEC target instead of P 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 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.
Figure 8: Effect of the number of METIS partitions Np (one seed, 50 epochs). Dashed lines in (a) show the ideal 1/Np scaling from each dataset’s first feasible point; crosses mark runs that exceed the GPU memory (Facebook and Credit at Np≤2 , Pokec at Np≤16 ).
School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510007, China · Institute of Artificial Intelligence, Xiamen University, Xiamen 361005, China · School of Software Engineering, Sun Yat-sen University, Zhuhai 519082, China