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 ).
Attributed graph clustering aims to discover node groups by jointly exploiting node attributes and graph topology, yet its unsupervised nature makes model selection and adaptation inherently difficult. Existing methods typically train and tune a separate model for each input graph, leading to costly and fragile pipelines that often fail to transfer across graphs with different feature spaces, structural patterns, and attribute-structure correlations. In this paper, we study a one-for-all alternative: can a single model be trained once and directly applied to diverse attributed graphs without graph-specific training, fine-tuning, or hyperparameter search? We propose OFAG, a foundation model for attributed graph clustering. Building upon Prior-data Fitted Networks, OFAG learns a reusable clustering inference strategy from synthetic attributed graphs generated under broad priors over latent clusters, node attributes, and graph structures. To handle incompatible feature spaces across graphs, OFAG adopts a dimension-agnostic signal-wise graph encoder that treats each feature channel as a graph signal and models its response to shared graph filters. The model is trained with a hyperspherical clustering objective, producing clustering-friendly node representations in a single forward pass at inference time. On ten datasets, one frozen OFAG model achieves the best mean performance and average rank across NMI, ACC, ARI, and F1, while completing all ten datasets in 12.43 minutes total---over 6* faster than the second-fastest baseline and nearly 28* faster than the second-best on clustering quality. Our code and pretrained checkpoint are available at https://github.com/Cloudy1225/OFAG, allowing practitioners to directly apply OFAG to their own attributed graph datasets without additional training or tuning.
Yunhui Liu, Xudong Jin, Kang Zhang +5
State Key Laboratory for Novel Software Technology Nanjing University Nanjing, China
Graph neural networks (GNNs) frequently encounter group fairness issues, often yielding biased predictions against specific demographic groups defined by sensitive attributes such as gender or race. While this challenge has motivated extensive research, most existing solutions rely on the strong assumption that demographics are fully available. To bypass this strict requirement, a few recent studies have attempted to use predicted demographics as proxies to enforce fairness constraints. However, predicted demographics may be inaccurate, resulting in the failure to improve fairness. In this work, we investigate the problem of graph fairness without demographic information and avoid the utilization of predicted demographics. Motivated by our observation that the gradient distributions of misclassified nodes implicitly encode demographic information, we first propose GradDist, a gradient-based metric that quantifies bias by measuring the distance between local modes within these distributions. To mitigate this bias, we propose Gradient-to-Fairness (Grad2Fair), a gradient-guided approach for group fairness without demographics. Due to the potential demographics in gradients, Grad2Fair directly leverages gradients to debias and eliminates demographic prediction, thereby enabling stable fairness performance. Experiments on several real-world datasets demonstrate the effectiveness of Grad2Fair, as evidenced by superior performance over baselines in most cases. Our code is available at https://github.com/ZzoomD/Grad2Fair.
Yuchang Zhu, Zezhong Xie, Huizhe Zhang +4
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
Message Passing Neural Networks have recently become the most popular approach to graph machine learning tasks; however, their receptive field is limited by the number of message passing layers. To increase the receptive field, Graph Transformers with global attention have been proposed; however, global attention does not take into account the graph topology and thus lacks graph-structure-based inductive biases, which are typically very important for graph machine learning tasks. In this work, we propose an alternative approach: cluster attention (CLATT). We divide graph nodes into clusters with off-the-shelf graph community detection algorithms and let each node attend to all other nodes in each cluster. CLATT provides large receptive fields while still having strong graph-structure-based inductive biases. We show that augmenting Message Passing Neural Networks or Graph Transformers with CLATT significantly improves their performance on a wide range of graph datasets including datasets from the recently introduced GraphLand benchmark representing real-world applications of graph machine learning.