k-hop Fairness: Addressing Disparities in Graph Link Prediction Beyond First-Order Neighborhoods

이 논문은 기존 1 차 이웃 중심의 공정성 접근법의 한계를 지적하고, 노드 간 거리 ($k$-hop) 에 따른 구조적 편차를 고려한 새로운 'k-hop 공정성' 개념을 제안하여 링크 예측의 불공정성을 완화하는 전처리 및 사후처리 전략을 제시합니다.

핵심

이 논문은 **"그래프 기반 추천 시스템 **(링크 예측)에 대한 연구입니다.

쉽게 말해, "페이스북 친구 추천"이나 "링크드인 연결 제안" 같은 기능이 어떻게 작동하는지, 그리고 그 과정에서 어떤 불공정함이 발생할 수 있는지, 그리고 어떻게 고칠 수 있는지를 다룹니다.

이 복잡한 내용을 세 가지 핵심 비유로 설명해 드릴게요.

---

1. 문제: "동일한 반쪽"만 추천하는 시스템 (기존 방식의 한계)

지금까지의 공정한 추천 시스템은 주로 **"남자와 여자 **(또는 A 그룹과 B 그룹)에 집중했습니다.

• 비유: imagine (상상해 보세요) 학교에서 친구를 소개해 주는 선생님이 있다고 칩시다.
  • **기존 방식 **(Dyadic Fairness) 선생님은 "남학생과 여학생이 서로 친구가 되도록" 노력합니다. 하지만, 이미 인기 있는 남학생은 이미 많은 친구가 있는데도 계속 새로운 여자 친구를 소개해 줍니다. 반면, 외톨이인 남학생은 아무리 노력해도 소개받지 못합니다.
  • 결과: 전체적으로 보면 남녀 연결이 늘어났지만, 외톨이들은 여전히 외톨이로 남습니다. 인기 있는 사람들만 더 인기를 얻는 '부익부 빈익빈' 현상이 발생합니다.

이 논문은 "단순히 그룹 간 연결만 늘리는 건 불공정할 수 있다"고 지적합니다. 중요한 건 개별 학생이 얼마나 다양한 친구를 사귀고 있는지입니다.

2. 새로운 아이디어: "k-hop (k-단계) 거리"를 고려한 공정한 추천

저자들은 **"k-hop Fairness **(k-단계 공정성)라는 새로운 개념을 제안합니다.

• 비유: 친구 관계를 **거리 **(Hop)로 생각해보세요.
  • 1-hop: 바로 옆에 있는 친구 (직접 연결).
  • 2-hop: 내 친구의 친구 (간접 연결).
  • 3-hop: 내 친구의 친구의 친구.

기존 시스템은 **1-hop **(바로 옆)만 보며 "남녀 연결을 늘려라"라고 했지만, 저자들은 "1-hop, 2-hop, 3-hop 등 모든 거리에서 공정한가?"를 봅니다.

• 핵심 메시지: 어떤 학생은 1-hop 거리에서는 다양한 친구가 있지만, 3-hop 거리에서는 여전히 같은 반 친구들만 있을 수 있습니다. 반대로 외톨이는 3-hop 거리에서도 전혀 다른 친구를 만나지 못합니다.
• 해결책: 우리는 각 학생이 '내 친구의 친구의 친구'까지 포함했을 때 다양한 배경을 가진 사람들과 연결되어 있는지 확인해야 합니다. 이를 통해 **외톨이들이 더 넓은 세상 **(다양한 그룹)을 보장합니다.

3. 해결책: "교정기"와 "리모델링" (Mitigation Strategies)

논문은 이 불공정함을 고치는 두 가지 방법을 제시합니다.

A. 사후 처리 (Post-processing): "추천 결과 수정하기"

• 비유: 이미 만들어진 친구 추천 목록을 편집기로 수정하는 것입니다.
  • 시스템이 "A 학생에게 B 학생을 추천했다"고 했을 때, 만약 A 학생이 이미 B 학생과 비슷한 친구들이 너무 많다면, 추천을 **C 학생 **(다른 배경)으로 바꿔줍니다.
  • 장점: 원래 추천 시스템의 성능 (AUC) 을 크게 해치지 않으면서, 특정 거리 (예: 2-hop) 에서의 불공정함을 줄일 수 있습니다.

B. 사전 처리 (Pre-processing): "학교 구조 바꾸기"

• 비유: 친구 추천을 하기 전에 **학교의 복도 구조 **(그래프 구조)를 바꾸는 것입니다.
  • 외톨이들이 다른 반 친구들을 만날 수 있도록 **새로운 복도 **(새로운 연결)를 만들어줍니다.
  • 장점: 근본적인 구조를 고쳐 불공정함을 줄이지만, 계산이 복잡하고 원래 구조를 너무 많이 바꿀 수 있다는 단점이 있습니다.

4. 실험 결과: "원하는 거리만큼만 고칠 수 있다"

연구자들은 다양한 실제 데이터 (정치 블로그, 페이스북, 학술 네트워크 등) 로 실험했습니다.

• 발견 1: 기존 시스템은 1-hop 거리에서는 공정한 척하지만, 3-hop이나 4-hop으로 가면 여전히 심각한 불공정함이 숨어있었습니다.
• 발견 2: 한 거리 (예: 2-hop) 의 불공정함을 고치려고 하면, 다른 거리 (예: 3-hop) 의 불공정함이 더 심해질 수도 있었습니다. (서로 영향을 줌)
• 발견 3: 하지만 저자들이 제안한 **사후 처리 **(Post-processing)는 **특정 거리 **(k-hop)를 선택적으로 고칠 수 있었습니다. 예를 들어, "2-hop 거리만 공평하게 만들어줘"라고 하면, 1-hop이나 3-hop에는 영향을 주지 않고 딱 그 부분만 고쳐주는 것이 가능했습니다.

요약: 이 논문이 우리에게 주는 교훈

이 논문은 "공정함은 단순히 '그룹 A 와 B 를 섞는 것'이 아니다"라고 말합니다.

**"우리는 각 개인이 자신의 친구圈子 **(네트워크)

기존의 "남녀 연결 늘리기" 방식은 겉보기엔 좋아 보이지만, 실제로는 **가장 도움이 필요한 사람들 **(외톨이)을 놓칠 수 있습니다. 이 논문은 **거리 **(k-hop)를 고려하여, 누구도 소외되지 않는 더 넓은 세상을 만드는 새로운 기준을 제시합니다.

한 줄 요약:

"친구 추천 시스템이 단순히 '다른 그룹'끼리 연결하는 것만으로는 부족합니다. 각 사람이 '친구의 친구의 친구'까지 포함해 얼마나 다양한 사람들과 연결되어 있는지를 확인하고, 그 거리를 기준으로 공평하게 고쳐야 진짜 공정합니다."

기술 요약

1. 문제 정의 (Problem Definition)

배경:
그래프 기반 애플리케이션, 특히 소셜 추천 시스템에서 링크 예측 (Link Prediction, LP) 은 핵심적인 역할을 합니다. 그러나 실제 세계의 그래프 데이터는 종종 구조적 편향 (structural biases), 특히 **동질성 (Homophily)**을 반영합니다. 동질성이란 유사한 속성 (예: 성별, 인종) 을 가진 노드들이 서로 연결되는 경향을 의미합니다.

기존 접근법의 한계:
기존의 공정한 링크 예측 (Fair LP) 방법들은 주로 이항적 공정성 (Dyadic Fairness) 패러다임에 의존합니다. 이는 민감한 속성이 다른 노드들 간의 연결 (Inter-group links) 을 촉진하여 그룹 간 편향을 완화하는 것을 목표로 합니다.
하지만 이 논문은 기존 접근법의 두 가지 치명적인 결함을 지적합니다.

1. 구조적 맥락의 무시: 이항적 공정성은 그래프의 기존 구조 (토폴로지) 를 고려하지 않습니다. 단순히 그룹 간 연결을 늘리는 것이 항상 공정한 것은 아니며, 오히려 이미 잘 연결된 다양성 있는 지역은 더 강화되고, 고립된 지역은 방치되는 결과를 초래할 수 있습니다.
2. 내부 불평등의 간과: 동질적인 그룹 내부에서도 노드의 위치 (위치적 지위) 는 다릅니다. 모든 노드를 동일하게 취급하는 기존 방식은 특정 그룹 내의 소외된 노드들을 보호하지 못합니다.

핵심 문제:
기존의 '노드 쌍 (Edge)' 중심의 공정성 평가는 그래프의 거리 (hop) 에 따른 구조적 편향을 무시합니다. 따라서 노드의 k-hop 이웃 (k-hop neighborhood) 내에서의 다양성을 고려한 새로운 공정성 정의와 완화 전략이 필요합니다.

---

2. 제안 방법론 (Methodology)

저자들은 k-hop Fairness라는 새로운 구조적 공정성 개념을 제안하고, 이를 정량화 및 완화하기 위한 방법론을 개발했습니다.

A. k-hop 공정성 정의

기존의 이항적 공정성 지표를 노드 기반의 k-hop 노출 (k-hop exposure) 개념으로 재정의했습니다.

• k-hop 노드 속성 노출 ($f^{(k)}_s(v)$): 노드 $v$가 정확히 $k$ hops 거리에 있는 민감한 속성 $s$를 가진 노드들과 연결될 확률을 의미합니다.
• k-hop 그룹 노출 ($\phi^{(k)}_{s \to s'}$): 특정 민감 그룹 $s$에 속한 노드들이 $k$ hops 거리에서 다른 그룹 $s'$에 노출되는 평균 정도입니다. 이는 구조적으로 중심에 있는 소수 노드가 전체를 대표하는 것을 방지하기 위해 각 노드에 동등한 가중치를 부여합니다.
• k-hop 이웃 공정성 ($NF^{(k)}$): $k$ hops 거리에서 동일한 소스 그룹의 노드들이 서로 다른 민감 그룹에 얼마나 균일하게 노출되는지를 측정합니다. 값이 작을수록 $k$ hops 거리에서의 그룹 간 접근성이 균형 잡혀 있음을 의미합니다.
• k-hop 구조적 편향 ($NB^{(k)}$): 실제 그래프 구조 (예측이 아닌) 에 대해 정의된 지표로, $k$ hops 거리에서의 실제 연결 다양성을 측정합니다.

B. 편향 측정 및 완화 전략

논문은 **Pre-processing (전처리)**과 Post-processing (후처리) 두 가지 전략을 제안합니다.

1. 측정 (Measurement):

   • $k$ hops 거리 행렬 $\tilde{A}^{(k)}$를 계산하여 (BFS 또는 행렬 거듭제곱 활용), 각 노드의 $k$ hops 이웃 내 민감 속성 분포를 분석합니다.
   • 시간 복잡도는 희소 그래프 가정 하에 $O(n^2)$ 수준으로 효율적으로 계산 가능합니다.

2. Pre-processing (그래프 구조 수정):

   • 그래프의 인접 행렬 $A$를 직접 수정하여 $k$ hops 구조적 편향 ($NB^{(k)}$) 을 줄입니다.
   • 손실 함수: $\mathcal{L}^{(k)}_{pre} = NB^{(k)}(A') + \alpha \|A' - A\|_F$.
   • 편향을 줄이기 위해 새로운 엣지를 추가하거나 기존 엣지를 재배치 (rewiring) 하되, 원본 그래프와의 충실도 (Fidelity) 를 유지합니다.

3. Post-processing (예측 값 수정):

   • 학습된 링크 예측 모델의 출력 확률 행렬 $P$를 수정합니다.
   • 손실 함수: $\mathcal{L}^{(k)}_{post} = NF^{(k)}(P') + \alpha \|U \odot \tilde{A}^{(k)}\|_F$.
   • 핵심 특징: $k$ hops 거리에 있는 노드 쌍에 대해서만 예측 값을 조정합니다. 이는 특정 거리 $k$에 대한 공정성 최적화가 다른 거리 $k'$의 예측 성능에 영향을 주지 않도록 모듈러 (Modular) 한 제어를 가능하게 합니다.

---

3. 주요 기여 (Key Contributions)

1. k-hop 공정성 프레임워크 도입: 링크 예측의 공정성을 평가할 때, 단순한 노드 쌍이 아닌 노드의 k-hop 이웃 내 다양성을 고려하는 새로운 척도 ($NF^{(k)}$, $NB^{(k)}$) 를 제안했습니다. 이는 다중 민감 속성과 방향성/가중치 그래프에도 일반화됩니다.
2. 이항적 공정성의 한계 규명: 기존 Dyadic Fairness 가 그래프 구조를 무시하여 고립된 노드들을 방치하고, 그룹 내 불평등을 악화시킬 수 있음을 이론적으로 증명하고 사례를 제시했습니다.
3. 모델 무관 (Model-agnostic) 완화 알고리즘: 그래프 구조를 수정하거나 (Pre-processing), 예측 값을 조정하는 (Post-processing) 두 가지 범용적인 완화 전략을 제시했습니다.
4. 실증적 분석: 다양한 실제 데이터셋 (Polblogs, Facebook, Pokec 등) 과 모델 (GCN, SAGE, Node2Vec 등) 을 통해 k-hop 편향과 예측 공정성 간의 상관관계, 그리고 다른 hop 간 편향의 상호 의존성을 분석했습니다.

---

4. 실험 결과 (Results)

실험은 Polblogs, Facebook, Pokec, Citeseer, Synthetic 데이터셋에서 수행되었으며, 주요 결과는 다음과 같습니다.

• RQ1: 구조적 편향과 예측 공정성의 관계:

  • 대부분의 그래프에서 1-hop 편향이 가장 높았으나, 특정 hop (예: Polblogs 의 4-hop) 에서도 유의미한 편향이 존재했습니다.
  • 그래프의 구조적 편향 ($NB^{(k)}$) 과 모델의 예측 편향 ($NF^{(k)}$) 은 높은 상관관계를 보였습니다. 즉, 구조적 분석을 통해 공정성이 낮은 hop 을 예측할 수 있습니다.

• RQ2: 다른 Hop 간의 의존성:

  • Pre-processing (엣지 추가) 을 통해 특정 $k$의 편향을 줄이면, 다른 $k$의 편향에도 영향을 미칩니다.
  • 이 영향은 강화 (reinforcing) 되거나 보상 (compensatory) 되는 등 복잡하게 상호작용하므로, 데이터 특성에 맞는 전략이 필요합니다.

• RQ3: Post-processing 의 효과:

  • 제안된 Post-processing 방법은 기존 공정한 LP 베이스라인 (FairWalk, CrossWalk 등) 보다 목표한 k-hop 거리에서의 공정성 ($NF^{(k)}$) 을 획기적으로 개선했습니다.
  • 성능 - 공정성 트레이드오프:
    • $k=1$일 때: 테스트 데이터와 겹치는 부분이 적어 예측 성능 (AUC) 을 거의 잃지 않으면서 공정성을 크게 향상시켰습니다.
    • $k=2$일 때: 로컬 클러스터링으로 인해 테스트 엣지와 겹치는 경우가 많아 성능 저하가 발생했습니다.
    • $k>2$일 때: 테스트 엣지와의 겹침이 적어 성능 저하가 적거나 오히려 개선되기도 했습니다.
  • 독립성: Post-processing 은 특정 $k$에 대한 최적화를 수행하므로, 다른 $k'$의 예측 편향을 악화시키지 않아 모듈러한 제어가 가능합니다.

---

5. 의의 및 결론 (Significance and Conclusion)

이 논문은 그래프 링크 예측의 공정성 연구에 다음과 같은 중요한 기여를 합니다.

1. 패러다임 전환: "노드 쌍 (Edge)" 중심의 공정성에서 "노드 이웃 (Neighborhood)" 중심의 공정성으로 관점을 전환했습니다. 이는 알고리즘이 특정 그룹 내 소외된 노드들에게 정보 접근 기회를 제공하는지 여부를 더 정교하게 평가할 수 있게 합니다.
2. 실용적 적용 가능성: LinkedIn 과 같은 산업계에서 추천을 2-hop, 3-hop 단위로 분류하는 현실을 반영하여, 특정 거리에서의 공정성을 독립적으로 제어할 수 있는 실용적인 방법론을 제시했습니다.
3. 한계점 및 향후 과제: 정확한 최단 경로 계산으로 인해 대규모 그래프에서의 확장성 (Scalability) 이 제한적일 수 있으며, 노드 특징 (Node features) 을 고려하지 않은 순수 구조적 접근이라는 한계가 있습니다.

결론적으로, 이 연구는 그래프 기반 추천 시스템이 구조적 편향을 단순히 '그룹 간 연결'로만 해결하려 하지 않고, 거리 기반의 구조적 맥락을 고려하여 더 포괄적이고 공정한 연결을 제공할 수 있음을 입증했습니다.