Skip to content
検索結果に戻る

ネットワークにおける欠損および将来のエッジ推論

年
2003
種類
Network inference task

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

リンク予測は、観測されたグラフから欠損しているエッジ、または将来形成される可能性が高いエッジを推定するネットワーク分析タスクである。Liben-NowellとKleinberg (2003, 2007) によって形式化されたこのタスクは、共通隣接ノード、Jaccard係数、Adamic-Adarなどの単純な構造的類似性指標から、行列分解、グラフニューラルネットワーク(GNN)手法に至るまで、幅広いアプローチをカバーしており、実際のリンクと存在しないリンクの著しく不均衡な比率を考慮するために、AUCと平均適合率(Average Precision)で評価される。

手法の背後にある直感

現実世界のあらゆるネットワークにおいて、記録されたエッジは真の接続のごく一部しか表していない。友人関係プラットフォームは未公開のつながりを欠き、引用データベースは未索引の論文を省略し、タンパク質相互作用アッセイは多くのペアを未検査のままにする。リンク予測は、観測可能な接続に基づいて、どの観測されていないペアが最も接続される可能性が高いかを問う。その中心的な直観は、多くの共通隣接ノードを共有する2つのノード、または学習された埋め込み空間で互いに近くに位置する2つのノードは、構造的に遠い2つのノードよりもリンクされる可能性が高いということである。類似性ベースの指標は、単一の数式でこれを明示する。GNNベースのアプローチは、ラベル付けされた例から接続性を予測するのに最適な構造的パターンを学習する。

歴史学

このタスクは、Liben-NowellとKleinbergによって2003年のSODA論文とその拡張版である2007年のJASIST版で正式に定義され、共著ネットワークで単純な構造的類似性指標をベンチマークし、トポロジーだけでも強力な予測信号を持つことを示した。その後の研究では、行列分解や確率的生成モデルにタスクが拡張された。この分野は、局所的な包囲サブグラフを抽出し、GNNで分類するSealフレームワークを提案したZhangとChen (2018) によって大幅に進歩し、学習された構造的特徴が多様なベンチマークネットワーク全体で手作りの類似性指標を一貫して上回ることを示した。

使うべき場面

リンク予測は、ネットワークが不完全または進化しており、エッジを回復または予測することを目的とするあらゆる問題に適している。適切なシナリオには、ソーシャルネットワークでの新しい接続の推奨、将来の引用または共同研究の予測、タンパク質間相互作用の推論、知識グラフの補完が含まれる。この手法は、少なくとも50ノードと、構造的パターンが学習可能であるのに十分な観測エッジの密度を必要とする。ノードが20未満の場合、中心性分析の方が安全な選択肢である。グラフの観測部分は代表的でなければならない。サンプリングメカニズムが著しく偏っている場合、推論されたエッジは真の構造ではなくサンプリングのアーティファクトを反映する可能性がある。

限界と注意点

  • パフォーマンスは負サンプリング戦略に決定的に依存する。異なる戦略は、同じモデルから異なる結論を導き出す可能性がある。
  • GNNベースの手法は、十分に大きなラベル付きエッジセットとかなりの計算リソースを必要とする。
  • 構造的指標は、観測されたトポロジーの類似性が将来の接続性を示唆すると仮定するが、これはヘテロフィル構造を持つネットワークでは当てはまらない可能性がある。
  • 時間的訓練・テスト分割は不可欠であるが、信頼できるタイムスタンプを必要とする。それがない場合、情報漏洩は観測されるパフォーマンスを膨張させる。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 単純なJaccardまたはAdamic-Adar指標は訓練を必要とせず、グラフのトポロジー上で直接機能するのに対し、GNNベースの手法は複雑な構造的パターンを学習するという、幅広い複雑性に対応する。
  • モデルフリーの類似性指標は、高速で解釈可能であり、訓練信号が限られたスパースなグラフで堅牢である。
  • GNNアプローチは、ドメイン(ソーシャル、生物学、知識グラフ)全体でよく一般化し、高次のトポロジーを捉える。
  • AUC/AP評価フレームワークは、実際のリンクと存在しないリンク間の深刻なクラス不均衡に対して堅牢である。

応用

  • ソーシャルネットワークにおける友人または接続の推奨(Facebookの「知り合いかも」機能、LinkedIn)。
  • 学術ネットワークにおける将来の研究協力または引用関係の予測。
  • 部分的な実験データから生物学的ネットワークにおけるタンパク質間相互作用の欠損を推論すること。
  • エンティティ間の関係を予測することによる知識グラフの補完。
  • 薬理学的ネットワークにおける薬物標的相互作用の予測。

使い方

使い方

1

ネットワークは観測されたエッジから構築され、時間的またはランダムな分割を用いて訓練セットとテストセットに分割される。時間的分割はタイムスタンプが利用可能な場合に好まれる。なぜなら、将来のエッジが過去のエッジに関するモデルに影響を与えることを防ぐからである。訓練グラフは、スコアリング方法が観測できる唯一のグラフである。

2

ノードペアの大多数は接続されていないため、すべての不在ペアを評価することは非現実的である。負例として機能する非存在エッジのセットを選択するために、負サンプリング戦略が用いられる。サイズとサンプリング戦略(ランダム、ハードネガティブ、次数バランス)は、測定されたパフォーマンスに大きく影響し、結果とともに報告されなければならない。

3

各候補ペアは尤度スコアを受け取る。構造的指標は、観測されたグラフのトポロジーからスコアを計算する。共通隣接ノードは共有隣接ノードの数を数え、Jaccard係数はその数を和集合で正規化し、Adamic-Adarは共有隣接ノードをその次数(degree)の逆対数で重み付けする。行列分解手法は、隣接行列を潜在因子に分解し、それらの内積がエッジ確率を近似する。GNNベースの手法、特にZhangとChen (2018) のSealフレームワークは、各候補ペアの周りの局所的なサブグラフを抽出し、実際のリンクと偽のリンクを区別するためにグラフ分類器を訓練し、単純な指標が見落とす高次の構造的パターンを捉える。

4

予測はスコアでランク付けされ、保持された正例と負例と比較される。AUC-ROCは、ランダムな正例ペアがランダムな負例ペアよりも上位にランク付けされる確率を測定する。平均適合率(AP)は、ランキング全体にわたる適合率を要約し、正例がまれな場合に、より多くの情報を提供する。両方の指標を報告する必要がある。クラスの不均衡が深刻な場合、精度だけでは誤解を招く。

よくある落とし穴

  • 訓練グラフに将来のエッジを漏洩させること。常に時間的または厳密にランダムな分割を使用し、テストエッジが訓練隣接行列に現れないことを確認すること。
  • 精度のみを報告すること。非エッジは真のエッジをはるかに上回るため、精度はほとんど無意味である。常にAUCとAPを報告すること。
  • モデル間のランキングを逆転させる可能性があるサンプリング戦略の変更を無視すること。
  • 20ノード未満のグラフにリンク予測を適用すること。ノードが非常に少ない場合、構造的パターンは信頼できる予測を生成するにはあまりにもスパースである。代わりに中心性分析を優先すること。
  • 観測されたエッジが体系的に特定のノードタイプを欠いている場合、推論はそのバイアスを継承するため、偏った観測グラフを代表的なサンプルとして扱うこと。

よくある質問

どの手法を選択すべきか?類似性指標かGNNか?

類似性指標(共通隣接ノード、Jaccard、Adamic-Adar)は良い出発点である。訓練を必要とせず、解釈可能で、スパースなグラフで驚くほどうまく機能する。SealのようなGNNベースの手法は、複雑な高次構造を持つネットワークでは指標を上回るが、十分な数のラベル付きエッジとより多くの計算リソースを必要とする。データが限られている場合や解釈可能性が重要な場合は、指標から始める。

情報漏洩なしに評価のためにグラフをどのように分割するか?

エッジにタイムスタンプが付いている場合は、時間的分割を使用する。カットオフ時間より前に観測されたエッジで訓練し、それ以降に形成されたエッジでテストする。タイムスタンプがない場合は、正例としてエッジのランダムな割合を保持し、負例として同数または固定数の非エッジをサンプリングし、保持されたエッジが訓練隣接行列に現れないようにする。

なぜ精度よりもAUCが好まれるのか?

あらゆる実際のネットワークにおいて、不在エッジの数は存在するエッジの数をはるかに超える。しばしば数桁の違いがある。すべてのペアに「エッジなし」と予測する単純なモデルは、ほぼ完璧な精度を達成するが、有用なものは何も予測しない。AUC-ROCと平均適合率は、この不均衡に影響されず、ランキングの質を直接測定するランクベースの指標である。

リンク予測は、有向グラフまたは加重グラフに適用できるか?

はい。有向グラフの場合、スコアは各方向で個別に計算でき、一部のGNNフレームワークは有向隣接性をネイティブに処理する。加重グラフの場合、類似性指標はエッジ重みを隣接ノード計算に組み込むことができ、GNN手法はエッジ特徴を使用できる。しかし、ほとんどのベンチマーク研究は無加重無向グラフで行われているため、手法を適応させる際には特別な注意が必要である。

関連する手法

参考文献

  1. Liben-Nowell, D. & Kleinberg, J. (2007). The Link-Prediction Problem for Social Networks. Journal of the American Society for Information Science and Technology, 58(7), 1019-1031.

    DOI 文献を開く
    コピーしました。
  2. Zhang, M. & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS), 31.

    出版物の文献を開く
    コピーしました。