FairPGT: 이중 수준 공정 그래프 군집화를 위한 분할 그래프 트랜스포머
FairPGT: Partitioned Graph Transformers for Dual-Level Fair Graph Clustering
한국어 초록
속성 그래프에 대한 군집화는, 특히 커뮤니티가 보호 집단과 일치할 때 인구통계학적으로 편향된 군집을 만들 수 있다. 그래프 트랜스포머는 동일 집단 어텐션을 통해 이러한 편향을 증폭할 수 있으며, 전역 어텐션은 확장성을 제한한다. 우리는 공정한 그래프 군집화를 위한 분할 그래프 트랜스포머인 FairPGT를 제안한다. FairPGT는 어텐션을 METIS 분할 내부로 제한하고 라우팅 토큰을 통해 분할들을 연결하며, 이를 통해 어텐션의 이차 비용을 분할 수로 나눈다. 그래프 인식 자기 학습 목표가 군집화를 안내하며, 이 목표는 표준 DEC 목표와의 편차가 증명 가능하게 유계이다. 공정성은 두 수준에서 부과된다. 상호 정보량 항은 군집 할당에서 인구통계학적 균형(demographic parity)을 촉진하고, 정규화된 교차 집단 어텐션 비율(nCGAR)은 자기 증류를 통해 어텐션이 집단 중립성을 향하도록 안내한다. 우리는 nCGAR 보정이 어텐션을 중립성 쪽으로 이동시킴을 증명하고, 과도한 이동을 방지하는 조건을 제시한다. 일곱 개의 벤치마크 전반에서 FairPGT는 가장 큰 세 그래프(Credit, Pokec-n, Pokec-z)에서 최고의 군집화 성능과 통계적 균형을 달성하였으며, 통계적 균형 격차는 DMoN보다 약 열 배 낮고, 하나의 데이터셋에서만 파레토 열위에 놓인다. 통제된 확률적 블록 모형에서 FairPGT는 커뮤니티와 보호 집단이 일치할 때 정확히 공정한 군집화에 대해 도출된 NMI 상한의 97%에 도달한다. 이 그래프들은 또한 강한 정렬 하에서 할당 수준의 공정성만으로는 어텐션이 집단 이질적(group-heterophilous)이 되고, 어텐션 수준의 공정성만으로는 중립성은 개선되지만 공정한 군집이 보장되지 않음을 보여준다. 재현을 위한 코드는 https://github.com/SiamakGhodsi/FairPGT 에서 확인할 수 있다.
원문 초록
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.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2611.23631v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.