arXiv cs.AI· Siamak Ghodsi, Amjad Seyedi, Sahar Tahmasebi, Eirini Ntoutsi, S\"oren Auer·· 10 小时前AI 评分18
FairPGT:面向双层公平图聚类的分区图 Transformer
FairPGT: Partitioned Graph Transformers for Dual-Level Fair Graph Clustering
AI 导读
FairPGT 是一种分区图 Transformer,将注意力限制在 METIS 分区内并通过路由 token 连接,把注意力的二次成本按分区数分摊。它在聚类分配上用互信息项促进人口统计均等,并用归一化跨群体注意力比(nCGAR)通过自蒸馏引导注意力趋于群体中立,且证明了 nCGAR 修正的有效性与防过冲条件。
正文 · 原文
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 this https URL.
| Comments: | Under review. 36 pages, 8 figures, 5 tables. Code: this https URL |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2611.23631 [cs.LG] |
| (or arXiv:2611.23631v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2611.23631 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Siamak Ghodsi [view email]
[v1]
Tue, 17 Nov 2026 23:41:54 UTC (2,762 KB)
来源:arXiv cs.AI · arxiv.org