cs.LGNov 17, 2026

FairPGT: Partitioned Graph Transformers for Dual-Level Fair Graph Clustering

Authors: Siamak Ghodsi, Amjad Seyedi, Sahar Tahmasebi, Eirini Ntoutsi, Sören Auer

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 · 

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.

Figures & tables

Explore similar work

CardsList
  1. Towards One-for-All Foundation Model for Attributed Graph Clustering

    Oct 6, 2026Yunhui Liu, Xudong Jin, Kang Zhang +5Graph Representation LearningGraph Foundation Models

  2. Grad2Fair: A Gradient-driven Approach for Graph Fairness without Demographics

    Jul 16, 2026Yuchang Zhu, Zezhong Xie, Huizhe Zhang +4Graph Neural NetworksAlgorithmic Fairness

  3. Cluster Attention for Graph Machine Learning

    Apr 8, 2026Oleg Platonov, Liudmila ProkhorenkovaGraph Neural NetworksAttention Mechanisms