跳到正文
arXiv cs.AI· Siamak Ghodsi, Amjad Seyedi, Sahar Tahmasebi, Eirini Ntoutsi, S\"oren Auer·· 1 小时前AI 评分36

FairPGT:基于分区的图 Transformer 实现双层公平图聚类

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

AI 导读

研究者提出 FairPGT,一种用于公平图聚类的分区图 Transformer,通过将注意力限制在 METIS 分区内并借助 routing tokens 连接,把二次方注意力成本除以分区数来提升可扩展性。

正文 · 原文

View PDF HTML (experimental)

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