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

この論文は、既存のダイアディック公平性の概念を超えてノード間の距離（k ホップ）に基づいた構造的不公平性を定量化し、リンク予測におけるバイアス低減と性能の両立を目指す「k ホップ公平性」という新たな枠組みと、そのための前処理・後処理手法を提案しています。

要約

🎯 核心となる問題：「近所の友達」だけを紹介する AI

みなさんは、SNS で「おすすめ友達」機能を使ったことがありますか？
AI は、あなたの現在の友達（1 歩先のつながり）を見て、「あなたと似た人」や「共通の友達がいる人」を提案します。

しかし、現実の社会には**「同質性（ホモフィリー）」**という現象があります。つまり、「似た者同士は集まりやすい」ということです。

• 政治的な意見が似ている人同士はつながりやすい。
• 同じ趣味の人同士は集まりやすい。

AI はこの「似た者同士が集まる」傾向をそのまま学習してしまいます。その結果、AI は**「すでに似たようなグループにいる人」ばかりを提案し、異なるグループの人とのつながりを提案しなくなります。**
これでは、情報のバブル（フィルターバブル）が強化され、社会の分断が深まってしまう恐れがあります。

🚫 従来の解決策の限界：「ただ混ぜるだけ」ではダメ

これまでも「公平な AI」を作る試みはありました。それは**「異なるグループ（例えば、男性と女性、異なる国籍など）の人同士をつなげるように指示する」**という方法です。

しかし、この論文の著者たちは、この方法には**「大きな落とし穴」**があると言います。

例え話：
街中に「青い服のグループ」と「赤い服のグループ」が住んでいるとします。
青い服のグループの中には、すでに街の中心で多くの赤い服の人と知り合っている「人気者（A さん）」と、山奥の奥深くで孤立している「隠れ家の人（B さん）」がいます。

従来の公平な AI は、「青い服と赤い服をつなげよう！」と叫びます。
しかし、AI は計算が楽な「A さん」と赤い服の人をつなげてしまいます。なぜなら、A さんはもともと赤い服の人と知り合いだからです。

結果：

• A さん： すでに多くのつながりがあるのに、さらに増やされて「さらに有利」になる。
• B さん： 孤立したまま、誰ともつながれない。

これでは、グループ全体としての公平性は改善されたように見えても、「グループ内の不公平（B さんの孤立）」はむしろ悪化してしまいます。

✨ 新しい解決策：「k-ホップ公平性（k-hop Fairness）」

そこで、この論文が提案するのが**「k-ホップ公平性」**という考え方です。

「k-ホップ」とは？

• 1 ホップ： 直接の友達（1 歩先）。
• 2 ホップ： 友達の友達（2 歩先）。
• 3 ホップ： 友達の友達の友達（3 歩先）。

この新しい考え方は、**「AI が提案するつながりが、どの『距離』にある人に対して公平か」**を厳しくチェックします。

1. 距離ごとにチェックする：
   「1 歩先の友達」だけでなく、「2 歩先、3 歩先の人」に対しても、異なるグループの人とつながる機会が平等に与えられているかを確認します。
2. 孤立した人を救う：
   先ほどの例え話で言うと、A さん（人気者）ではなく、B さん（孤立者）が、山奥から 3 歩先にある赤い服の人とつながれるように、AI が調整します。
3. 構造そのものを見る：
   単に「男女のつながり数」を数えるのではなく、**「グラフ（つながりの地図）の形そのもの」**が公平かどうかを評価します。

🛠️ 具体的なアプローチ：2 つの方法

著者たちは、この新しい公平性を実現するために、2 つのアプローチを提案しています。

1. 事前処理（Pre-processing）：地図を修正する
   AI を学習させる前に、グラフ（つながりの地図）自体を少し書き換えます。「孤立している人」に、意図的に新しい道（つながり）を引いてあげて、AI が公平な学習ができるようにします。

   • 例： 山奥の B さんに、あえて赤い服の人との「仮の道」を描いておく。

2. 事後処理（Post-processing）：提案を修正する
   AI が「おすすめ友達」を提案した後、その結果を人間（アルゴリズム）がチェックして修正します。「この提案は、孤立している人への配慮が足りないな」と判断したら、別の提案に差し替えます。

   • 例： AI が「A さん」を提案しようとしたら、「いや、B さんへの提案に変えよう」と調整する。

📊 実験結果：何がわかった？

さまざまな実社会のデータ（政治ブログ、Facebook、学術論文の共著ネットワークなど）で実験した結果、以下のことがわかりました。

• 偏見は「距離」によって違う：
  1 歩先のつながりでは偏見が強くても、3 歩先では偏見が弱まっている（あるいは逆）というケースがありました。従来の「全体で平均する」方法では、この微妙な違いが見逃されていました。
• 距離を調整すると、他の距離も影響を受ける：
  2 歩先のつながりを公平にしようとすると、1 歩先や 3 歩先のつながりも勝手に変わってしまいます。これは、社会のつながりが複雑に絡み合っている証拠です。
• 新しい方法は効果的：
  提案した「事後処理」の方法を使えば、「AI の精度（AUC）」を下げずに、公平性（特に孤立した人への配慮）を大幅に向上させることができました。

💡 まとめ

この論文が伝えたいことはシンプルです。

「AI に『公平なつながり』を作らせるには、単に『異なるグループ同士をつなげろ』と命令するだけでは不十分だ。
『誰が、どの距離で、孤立しているのか』まで見据えて、細かく調整する必要がある」

これは、AI が社会の分断を深めるのではなく、むしろ**「見えない孤立」を解消し、多様な人々が公平に機会を得られる社会**を作るための重要な一歩となります。

技術概要

論文「k-hop Fairness: Addressing Disparities in Graph Link Prediction」の技術的サマリー

この論文は、グラフリンク予測（Link Prediction: LP）における公平性の評価と改善に関する新しい枠組みを提案しています。従来の「対称的公平性（Dyadic Fairness）」の限界を指摘し、ノード間の距離（k-hop）に依存した構造的バイアスを考慮した「k-hop Fairness」を導入し、その緩和手法を提案しています。

以下に、問題定義、手法、主要な貢献、実験結果、および意義について詳細にまとめます。

---

1. 背景と問題定義

背景

グラフベースのアプリケーション（特にソーシャル推薦）において、リンク予測は重要な役割を果たしています。しかし、現実世界のグラフには構造的バイアス（特に同質性：Homophily、属性が似たノード同士が接続する傾向）が存在し、これがアルゴリズムによって増幅されることで、既存の社会的格差（フィルターバブルやガラスの天井効果など）を強化するリスクがあります。

従来のアプローチとその限界

現在の公平性意識型リンク予測（Fair LP）の主流は**対称的公平性（Dyadic Fairness）**です。これは、ノードの属性（性別、人種など）をエッジに拡張し、「グループ内リンク」と「グループ間リンク」の予測バランスを調整するパラダイムです（例：Demographic Parity, Equal Opportunity）。

しかし、この論文は対称的公平性には以下の重大な欠陥があると指摘しています：

1. 構造の無視: グラフのトポロジー（構造）を考慮せず、単にエッジの属性タイプに基づいて公平性を評価するため、グラフ内のノードの位置（孤立しているか、中心にあるか）が考慮されない。
2. 隔離現象の隠蔽: グループ間リンクを促進しようとする際、すでに多様な構造を持つ領域（例：図1の右側のクラスター）でのみリンクを増やす傾向があり、隔離された領域（例：図1の左側の青いノード群）へのアクセス改善には寄与しない。
3. 局所的不平等の看過: すでに多様な近傍を持つノードと、孤立したノードに対して、同じ重みで「グループ間リンク」を評価してしまうため、孤立したノードの地位向上が阻害される。

2. 提案手法：k-hop Fairness

この問題に対処するため、著者らはk-hop Fairnessという新しい公平性の概念を提案しました。これは、ノードの k-hop 近傍内での予測の多様性を評価する構造的なアプローチです。

主要な定義と指標

• k-hop ノード属性曝露（Exposure）:
  特定のノード $v$ が、距離 $k$ にあるノードの中で、特定の属性 $s$ を持つノードと接続する確率を定義します。
  $$f^{(k)}_s(v; h) = \mathbb{E}[h(V, V') \mathbb{1}_{\{S'=s\}} | \sigma(V, V') = k, V=v]$$

• k-hop グループ曝露（Group Exposure）:
  同じ属性を持つノード群全体での平均曝露を計算します。
  $$\phi^{(k)}_{s \to s'}(h) = \frac{1}{|V^{(k)}_s|} \sum_{v \in V^{(k)}_s} f^{(k)}_{s'}(v; h)$$

• k-hop 近傍公平性ギャップ（NF）:
  特定の k-hop 距離において、ソースグループ $s$ のノードが、異なるターゲットグループ $s_1, s_2$ に対して均等に曝露されているかを測定します。
  $$NF^{(k)}(h) = \max_{s \in S} \max_{s_1 \neq s_2} |\phi^{(k)}_{s_1 \to s}(h) - \phi^{(k)}_{s_2 \to s}(h)|$$
  この値が小さいほど、k-hop 距離における公平性が高いことを示します。

• k-hop 構造的バイアス（NB）:
  実際のグラフ構造（リンク予測モデルではなく、既存のグラフ）におけるバイアスを測定する指標です。
  $$NB^{(k)}(G) = \max_{s \in S} \max_{s_1 \neq s_2} |\phi^{(k)}_{s_1 \to s}(r^{(k)}) - \phi^{(k)}_{s_2 \to s}(r^{(k)})|$$
  ここで $r^{(k)}$ は k-hop 距離の指示関数です。

緩和戦略（Mitigation Strategies）

提案された指標に基づき、事前処理（Pre-processing）と事後処理（Post-processing）の両方のアプローチを提案しています。

1. 事後処理（Post-processing）:

   • 既存のリンク予測モデルの出力確率行列 $P$ に対して、距離 $k$ のノードペアのみを対象に最適化を行います。
   • 目的関数：$\min_U \ell^{(k)}_{post} = NF^{(k)}(P') + \alpha \|U \odot \tilde{A}^{(k)}\|_F$
   • ここで、$P'$ は修正後の行列、$\tilde{A}^{(k)}$ は k-hop 距離の指示行列、$\alpha$ は忠実度（元の予測からの乖離）を制御する正則化項です。
   • 特徴: 特定の k-hop 距離の公平性のみを最適化するため、他の距離のバイアスに悪影響を与えず、モジュール化されたトレードオフが可能。

2. 事前処理（Pre-processing）:

   • グラフの隣接行列 $A$ 自体を修正し、構造的バイアス $NB^{(k)}$ を低減します。
   • 目的関数：$\min_{A'} \ell^{(k)}_{pre} = NB^{(k)}(A') + \alpha \|A' - A\|_F$
   • 勾配降下法を用いて、バイアスを減らすエッジの追加や重み調整を行います。

3. 主要な貢献

1. k-hop Fairness の導入:
   対称的公平性の限界を克服し、ノードの k-hop 近傍内の多様性を評価する包括的な枠組みを確立しました。これは多値の敏感属性や、重み付き・有向グラフにも自然に拡張可能です。
2. アルゴリズム的解決策:
   k-hop 不均衡を定量化し、事前・事後処理の両方で緩和するモデル非依存（Model-agnostic）な手法を提案しました。
3. 包括的な実験的検証:
   複数の実世界グラフ（Polblogs, Facebook, Pokec, Citeseer など）と標準的な LP モデル（Node2Vec, GCN, GraphSAGE）を用いて、以下の知見を得ました。
   • 異なる k-hop において、モデルが構造的バイアスを再現する傾向が強いこと。
   • 事前処理によるバイアス低減は、他の距離のバイアスと複雑な依存関係（相関または相殺）を持つこと。
   • 事後処理手法が、既存の Fair LP ベースラインと比較して、k-hop 公平性と予測性能（AUC）の優れたトレードオフを実現すること。

4. 実験結果の要点

• RQ1: 構造的バイアスと公平性の関係
  • 多くのグラフで 1-hop のバイアスが最も高いですが、特定の距離（例：Polblogs の 4-hop）でも有意なバイアスが観測されました。
  • 構造的バイアス $NB^{(k)}$ と予測公平性 $NF^{(k)}$ は強く相関しており、構造的な分析が公平性の診断に有効であることを示しました。
• RQ2: 異なる距離間の依存関係
  • 事前処理（グラフの書き換え）において、特定の距離 $k$ のバイアスを低減すると、他の距離のバイアスも変化します（強化される場合もあれば、改善される場合もある）。これは単一の距離への対策がグラフ全体に波及効果を持つことを示しています。
• RQ3: 事後処理の効果
  • 提案する事後処理は、ターゲットとした $k$ における $NF^{(k)}$ を顕著に改善しました。
  • 性能への影響:
    • $k=1$ の場合、テストデータ（評価用エッジ）はトレーニングエッジと重なるため、スコア修正が AUC に直接影響しますが、実験では AUC の低下はほとんど見られませんでした。
    • $k=2$ の場合、局所的クラスタリングによりテストエッジと重なる割合が高く、AUC の低下が顕著になる傾向がありました。
    • 大きな $k$ の場合、テストエッジとの重なりが少なく、性能低下は最小限に抑えられ、場合によっては AUC が向上することもありました（バイアス除去による有用なシグナルの露出）。
  • 独立性: 事後処理は特定の距離 $k$ に対してのみ最適化を行うため、他の距離 $k'$ の予測バイアスを悪化させることなく、制御されたトレードオフを実現します。

5. 意義と結論

この研究は、グラフリンク予測における公平性の議論を「エッジの属性タイプ」から「ノードの構造的な位置（k-hop 近傍）」へと転換させる重要な一歩です。

• 理論的意義: 従来の対称的公平性が隠蔽していた「隔離されたノードへのアクセス不平等」や「局所的不平等」を可視化・定量化する新しい指標を提供しました。
• 実用的意義: 産業応用（LinkedIn などの 2 次・3 次以上の推薦）において、特定の距離での公平性を制御する実用的な手法（事後処理）を提示しました。
• 限界と将来展望: 現在の手法は正確な最短経路距離に依存しており、大規模グラフでのスケーラビリティに課題があります。また、ノードの属性特徴量（Feature-based）を考慮していないため、将来的には構造的公平性と特徴量ベースの公平性を統合する方向性が期待されます。

総じて、この論文はグラフベースの AI システムが、単なる統計的な公平性を超えて、ネットワーク構造そのものの公正さを考慮する必要性を強く示唆しています。