공정성 인식 부분그래프 확산을 통한 편향 없는 GNN 학습

기본 정보

• 논문 ID: 2501.00595
• 제목: Unbiased GNN Learning via Fairness-Aware Subgraph Diffusion
• 저자: Abdullah Alchihabi, Yuhong Guo (Carleton University)
• 분류: cs.LG cs.AI
• 발표 시간: 2024년 12월 31일 (arXiv 사전인쇄본)
• 논문 링크: https://arxiv.org/abs/2501.00595

초록

그래프 신경망(GNNs)은 다양한 그래프 관련 작업 처리에서 우수한 성능을 보이지만, 나이, 성별 등 민감한 노드 속성과 관련된 편향된 예측을 생성하는 중요한 과제에 직면해 있습니다. 메시지 전달 메커니즘으로 인해 노드가 상호 영향을 미치므로, GNNs의 편향은 전통적인 머신러닝 모델보다 더욱 심각합니다. 본 논문은 편향 없는 GNN 학습을 달성하기 위해 새로운 생성형 공정성 인식 부분그래프 확산(FASD) 방법을 제안합니다. 이 방법은 먼저 원본 대규모 그래프에서 전략적으로 작은 부분그래프를 샘플링한 후, 확률 미분 방정식(SDEs) 기반의 생성형 공정성 인식 그래프 확산 과정을 통해 부분그래프를 편향 제거합니다. 전방 확산 과정에서 대립적 편향 섭동을 도입하여 점수 기반 모델을 훈련시켜 이러한 섭동을 예측함으로써 데이터의 편향에 대한 잠재 동역학을 학습합니다. 그 후, 훈련된 점수 모델을 활용하여 역방향 확산 과정을 통해 원본 부분그래프 샘플을 편향 제거합니다. 마지막으로, 편향 제거된 부분그래프에서 표준 GNN 학습을 수행하여 공정한 노드 예측을 생성합니다.

연구 배경 및 동기

문제 정의

1. 핵심 문제: GNNs는 노드 분류 작업에서 나이, 성별, 인종 등 민감한 속성에 기반한 편향된 예측을 생성하기 쉬움
2. 편향 증폭 메커니즘: GNNs의 메시지 전달 메커니즘으로 인해 편향이 그래프 전체에 전파되고 증폭되어 전통적인 ML 모델보다 더 심각함
3. 응용 중요성: 의료, 채용 평가 등 중요한 분야에서 모델 공정성이 필수적

기존 방법의 한계

1. 전통적 공정성 학습 방법: 그래프 구조와 노드 간 메시지 전파의 상호작용을 고려하지 않음
2. 기존 공정성 GNN 방법:
   • 전처리 방법은 견고성이 부족하고 특정 편향 형태에 대해 설계됨
   • 처리 중 방법은 공정성과 정확성 간의 신중한 균형이 필요하며 안정성이 낮음
   • 후처리 방법은 예측 결과만 수정함
3. 그래프 확산 방법: 기존 방법은 입력 데이터의 편향을 쉽게 상속함

연구 동기

GNNs의 다양한 응용 분야에 광범위하게 적용할 수 있는 데이터 자적응형 공정성 인식 그래프 증강 및 학습 방법 개발

핵심 기여

1. 선도적 방법: 확산 과정을 활용하여 부분그래프 인스턴스를 편향 제거하고 하위 작업의 공정성을 촉진하는 첫 번째 공정성 인식 그래프 확산 방법 FASD 제안
2. 기술 혁신: 대립적 편향 섭동을 SDE 기반 전방 확산 과정에 통합하고 점수 모델을 통해 편향 동역학 학습
3. 실험 검증: 여러 벤치마크 데이터셋에서 최첨단 공정성 GNN 기준선 대비 우수한 성능 입증
4. 이론적 기여: 공정성 인식 그래프 확산을 위한 이론적 프레임워크 및 구현 방안 제공

방법 상세 설명

작업 정의

• 입력: 그래프 G=(V,E), 노드 특성 행렬 X∈R^(N×D), 민감 속성 벡터 S, 레이블 행렬 Y^ℓ
• 목표: 노드 레이블을 정확하고 공정하게 예측할 수 있는 GNN 모델 학습
• 공정성 기준: 집단 공정성, 통계적 균등성과 기회 균등성을 사용하여 평가

모델 아키텍처

1. 부분그래프 수준 인스턴스 샘플링

G^(i) = Subgraph_Sampling(G, u, d, k)

• 시작 노드 u에서 시작하여 깊이 d, 각 홉에서 k개 이웃 샘플링
• 부분그래프 집합 G = {G^(i)}_^M 생성

2. 공정성 인식 전방 확산

SDE 모델링:

dG_t^(i) = f_t(G_t^(i))dt + g_t(G_t^(i))dw

민감 속성 예측 모델:

Ŝ^(i) = g_sen(X^(i), A^(i))

공정성 인식 섭동:

X_t^(i) = μ_t(X_0^(i)) + σ_t(X_0^(i)) × ε_X - γ_X∇_X L_sen(X_0^(i), A_0^(i))
A_t^(i) = μ_t(A_0^(i)) + σ_t(A_0^(i)) × ε_A - γ_A∇_A L_sen(X_0^(i), A_0^(i))

3. 점수 기반 섭동 추정

노드 특성 점수 모델:

s_{θ,t}(G_t^(i)) = MLP_X([{H_j}_{j=0}^L])
H_{j+1} = GNN_X(H_j, A_t^(i)), H_0 = X_t^(i)

그래프 구조 점수 모델:

s_{φ,t}(G_t^(i)) = MLP_A([{GMH(H_j, (A_t^(i))^p)}_{j=0,p=1}^{K,P}])

손실 함수:

L_θ = E_t{E_{G_0^(i)} E_{G_t^(i)|G_0^(i)} ||s_{θ,t}(G_t^(i)) - ε_X + (γ_X/σ_t(X_0^(i)))∇_X L_sen||_2^2}

4. 역방향 확산 편향 제거

역방향 SDE:

dX_t^(i) = [f_{1,t}(X_t^(i)) - g_{1,t}^2 s_{θ,t}(G_t^(i))]dt̄ + g_{1,t}dw̄_1
dA_t^(i) = [f_{2,t}(A_t^(i)) - g_{2,t}^2 s_{φ,t}(G_t^(i))]dt̄ + g_{2,t}dw̄_2

Predictor-Corrector 샘플러를 사용하여 근사 해결.

5. 공정한 노드 분류

편향 제거된 부분그래프 G̃에서 표준 GNN 훈련:

P^(i) = f(X̃^(i), Ã^(i))
L = Σ_{G̃^(i)∈G̃} Σ_{u∈V_ℓ^(i)} ℓ_ce(P_u^(i), Y_u^ℓ)

기술 혁신 포인트

1. 공정성 인식 섭동 설계: 민감 속성 예측 손실의 그래디언트를 대립적 섭동으로 사용하여 편향을 직접 모델링
2. 이중 점수 모델: 노드 특성과 그래프 구조의 섭동을 각각 모델링하여 복잡한 편향 패턴 포착
3. 부분그래프 수준 처리: 부분그래프 샘플링을 통해 대규모 그래프의 계산 복잡성 해결
4. 생성형 편향 제거: 확산 모델의 생성 능력을 활용하여 데이터 수준의 편향 제거 실현

실험 설정

데이터셋

1. NBA: NBA 선수 데이터, 민감 속성은 국적, 레이블은 급여가 중앙값을 초과하는지 여부
2. Pokec-z/Pokec-n: 슬로바키아 소셜 네트워크 데이터, 민감 속성은 지역, 레이블은 직업 분야
3. 데이터 분할: NBA(20%/35%/45%), Pokec-z(10%/10%/80%), Pokec-n(10%/10%/80%)

평가 지표

1. 정확도(Acc.): 분류 정확성
2. 통계적 균등성(ΔDP): |P(Ŷ=1|S=0) - P(Ŷ=1|S=1)|
3. 기회 균등성(ΔEO): |P(Ŷ=1|S=0,Y=1) - P(Ŷ=1|S=1,Y=1)|

주: ΔDP와 ΔEO가 작을수록 공정성이 우수함

비교 방법

• 공정성 GNN 방법: FairWalk, FairDrop, NIFTY, FairAug, Graphair
• 그래프 대조 학습 방법: GRACE, GCA

구현 세부사항

• 부분그래프 샘플링: d=2(NBA), d=3(Pokec), k=10
• 민감 속성 예측기: 2층 GCN + 2층 완전연결, 은닉 차원(64,32,16)
• 점수 모델: 은닉 차원 32, 1000 에포크 훈련
• 역방향 확산 스텝: N_steps=5(NBA), 4(Pokec-z), 2(Pokec-n)

실험 결과

주요 결과

주요 발견:

1. 공정성 현저한 개선: 기회 균등성 측면에서 Pokec-z와 Pokec-n에서 각각 29%와 43% 개선
2. 통계적 균등성 우위: NBA와 Pokec-n에서 2위 대비 각각 64%와 60% 초과
3. 정확도 유지: 공정성을 현저히 개선하면서 정확도 감소는 미미함

절제 실험

절제 실험 결론:

1. 확산 과정의 필요성: 확산 과정 제거 후 공정성이 현저히 감소
2. 공정성 인식 섭동의 중요성: 무작위 섭동만 사용할 경우 효과 부족

초매개변수 민감도 분석

1. 역방향 확산 스텝: 최적값은 2-5 스텝, 과도한 스텝은 성능 저하
2. 공정성 섭동 가중치: λX, λA는 0.1, 10.0 범위에서 최적 성능

관련 연구

공정성 GNN 학습

1. 전처리 방법: FairWalk, FairDrop, Graphair 등, 하지만 견고성 부족
2. 처리 중 방법: NIFTY, FairAug 등, 공정성과 정확성 간 신중한 균형 필요
3. 후처리 방법: GNN 예측 결과 직접 수정

그래프 확산 방법

1. 연속 확산: GDSS 등 SDE 기반 모델링
2. 이산 확산: DiGress 등 마르코프 노이즈 과정 사용
3. 한계: 기존 방법은 입력 데이터 편향을 쉽게 상속

결론 및 논의

주요 결론

1. FASD는 확산 모델을 공정성 GNN 학습에 성공적으로 적용하여 데이터 수준의 편향 제거 실현
2. 공정성 인식 섭동과 점수 모델을 통해 편향 패턴을 효과적으로 학습하고 제거
3. 여러 벤치마크 데이터셋에서 최고의 공정성 성능 달성하면서 경쟁력 있는 정확도 유지

한계

1. 계산 복잡성: 여러 모델(민감 속성 예측기, 점수 모델, 분류기) 훈련 필요
2. 초매개변수 민감성: λX, λA 등 초매개변수의 신중한 조정 필요
3. 이진 민감 속성: 현재는 이진 민감 속성만 처리, 다중 클래스 확장 필요
4. 부분그래프 표현: 부분그래프 샘플링으로 인한 전역 정보 손실 가능성

향후 방향

1. 다중 클래스 민감 속성 및 다중 레이블 분류로 확장
2. 계산 효율성 향상, 훈련 복잡성 감소
3. 다른 공정성 기준의 적용 가능성 탐색
4. 방법의 수렴성 및 공정성 보장에 대한 이론적 분석

심층 평가

장점

1. 방법 혁신성 강함: 확산 모델을 공정성 GNN 학습에 처음 적용, 사고방식 참신
2. 기술 설계 합리적: 공정성 인식 섭동 설계가 직관적이고 효과적, 점수 모델 아키텍처가 그래프 데이터에 적합
3. 실험 충분함: 다중 데이터셋 검증, 절제 실험 및 초매개변수 분석 완전
4. 결과 설득력 강함: 공정성 지표 현저한 개선, 통계적 유의성 명확

부족한 점

1. 이론적 분석 부족: 수렴성 증명 또는 공정성 이론적 보장 미제공
2. 계산 효율성 문제: 다단계 훈련으로 인한 계산 비용 증가, 효율성 분석 부족
3. 적용성 제한: 상대적으로 소규모 그래프에서만 검증, 대규모 그래프의 확장성 미지수
4. 비교 불완전: 최신 공정성 학습 방법과의 비교 부족

영향력

1. 학술 기여: 공정성 GNN 학습을 위한 새로운 기술 경로 제공
2. 실용 가치: 중요한 응용 분야에서 중요한 의미
3. 재현성: 구현 세부사항이 상세하여 재현 및 확장에 유리

적용 시나리오

1. 중소규모 그래프: 현재 방법은 노드 수 만 단위 그래프에 적합
2. 공정성 요구도 높은 분야: 의료, 채용, 신용 등 민감한 응용
3. 이진 분류 작업: 특히 이진 민감 속성이 관련된 시나리오

참고문헌

논문은 공정성 학습, 그래프 신경망, 확산 모델 등 여러 분야의 중요한 연구 61편을 인용하여 연구에 견고한 이론적 기초를 제공합니다.

종합 평가: 이는 공정성 GNN 학습 분야에서 혁신적인 연구로, 확산 모델을 그래프 데이터 편향 제거에 처음 적용했으며, 방법 설계가 합리적이고 실험 결과가 설득력 있습니다. 이론적 분석과 계산 효율성 측면에서 개선의 여지가 있지만, 해당 분야에 가치 있는 새로운 사고방식과 기술 방안을 제공합니다.