Fair graph clustering now corrects attention too: FairPGT keeps encoders group-neutral and cuts the parity gap about tenfold versus DMoN on the three largest graphs
Synopsis
When communities in an attributed graph line up with protected groups, clustering inherits demographic bias, and a graph transformer's attention can itself favor same-group nodes. FairPGT restricts attention to METIS partitions linked by routing tokens, constrains statistical parity on cluster assignments with a mutual-information term, and steers encoder attention toward neutrality by self-distilling a normalized cross-group attention ratio (nCGAR). On the three largest graphs, Credit, Pokec-n and Pokec-z, it attains both the highest NMI and the lowest statistical-parity gap, about ten times lower than DMoN; on stochastic block models where communities and groups coincide, its NMI reaches 97% of the bound for any exactly fair clustering.
Interpretation
Fair graph clustering can now constrain two places at once: the group proportions of cluster assignments and the group preference of encoder attention. Earlier fair clustering methods constrained assignments or representations, and their encoders used no attention, so the group dependence of attention was neither measured nor controlled. On the three largest graphs, Credit, Pokec-n and Pokec-z, FairPGT is the only method with both the highest NMI and the lowest statistical-parity gap; on Pokec-n and Pokec-z the gaps are 0.006 and 0.005, about ten times lower than DMoN's 0.054 and 0.056.
The approach cuts global attention into blocks and reconnects them with a few tokens, so the transformer can handle graphs with tens of thousands of nodes. Full attention costs per layer grow with the square of the node count, which is prohibitive on the larger graphs of fair graph learning benchmarks. Attention is computed within METIS partitions of about 2,500 nodes, and partitions exchange information through one routing token each via global self-attention and broadcast; on LastFM, raising the partition count from 1 to 64 lowers peak memory from 11.9 GB to 0.75 GB.
Attention-level fairness is measured by a readable ratio, the normalized cross-group attention ratio (nCGAR), where 1 means group-neutral attention consistent with group composition. A raw count of attention mass cannot separate a preference for one's own group from the fact that a larger group naturally receives more attention; nCGAR normalizes by each partition's group composition, so it compares across partitions, layers and heads. During training the current attention is rebalanced by nCGAR and used as a self-distillation target; on stochastic block models at full alignment, assignment-level fairness alone drives attention to become group-heterophilous (nCGAR 2.9 to 3.7), while using both terms keeps nCGAR between 0.84 and 1.01.
Perspective
Experiments cover seven attributed graphs from 391 to 67,796 nodes, with binary protected attributes on five graphs and four groups on the two Pokec graphs; class labels are used only for evaluation, and the protected attribute enters only the training objective, so inference computes clusters from node features alone. On the two smallest graphs, NBA and German, the fair spectral method sFairSC is better than FairPGT in NMI or in statistical-parity gap.
nCGAR balances aggregate attention within each partition rather than separately per group; in LastFM's second layer one group sends 56% to 62% of its attention across groups and the other 34% to 49%, so part of the aggregate balance comes from the two deviations offsetting. The method is transductive, with partitions and spectral encodings computed once on the whole graph, so adding new nodes currently requires rerunning the pipeline; intersectional groups combining several attributes, such as gender with four age groups, are not evaluated.
