リンク予測とは？ネットワーク上の未知の関係性を予測する手法を解説
リンク予測は、ネットワーク内のノード間に将来エッジが形成されるかを予測する手法です。共通近傍・Jaccard係数・Adamic-Adar指標などの主要手法と、推薦・不正検知での活用法を解説します。
リンク予測とは
リンク予測（Link Prediction）は、ネットワーク内で現在存在しないエッジが将来形成される可能性を予測する手法です。「まだつながっていないが、つながる可能性が高いノードの組み合わせ」を特定します。
SNSの友人推薦、ECサイトの商品推薦、知識グラフの補完、学術論文の共著予測など、実務上の多くの課題がリンク予測問題として定式化できます。ネットワークの構造情報を活用することで、属性情報だけでは得られない予測精度を実現します。
リンク予測の体系的な研究は、2003年にジョン・リベン=ノウェル（Jon Liben-Nowell）とジョン・クラインバーグ（Jon Kleinberg）がコーネル大学で発表した論文「The Link Prediction Problem for Social Networks」に端を発します。この研究はソーシャルネットワーク上の共著関係を対象に、ネットワーク構造のみからリンクの出現を予測する手法を体系的に比較評価し、このテーマが独立した研究分野として確立するきっかけとなりました。
構成要素
ノード近傍ベースの手法
2つのノードの局所的なネットワーク構造から、リンクの可能性を評価します。
- 共通近傍数（Common Neighbors）: 2ノードが共有する隣接ノードの数。最もシンプルな指標です
- Jaccard係数: 共通近傍数を、両ノードの近傍の和集合で割った比率。ノードの次数差を補正します
- Adamic-Adar指標: 共通近傍の次数の逆対数で重み付けし、「珍しい共通の知人」を高く評価します
- Preferential Attachment: 両ノードの次数の積。「つながりの多いノード同士はさらにつながりやすい」という仮説に基づきます
パスベースの手法
ノード間の経路情報を活用します。
- Katz指標: 2ノード間の全パスを、長さに応じた減衰係数で重み付けして合算します
- SimRank: 「類似したノードとつながるノード同士は類似する」という再帰的な定義に基づきます
機械学習ベースの手法
上記の構造指標をノード属性と組み合わせ、分類問題として解く手法です。GNNを用いたリンク予測が近年主流になりつつあります。
| 手法カテゴリ | 代表手法 | 特徴 |
|---|---|---|
| 近傍ベース | Common Neighbors, Jaccard | 計算が高速、局所構造のみ使用 |
| パスベース | Katz, SimRank | 大域的構造を考慮、計算コスト高 |
| 機械学習ベース | GNN, Node2Vec | 高精度、属性情報も活用可能 |
実践的な使い方
ステップ1: ネットワークデータの準備と分割
ネットワークデータを時間的に分割し、過去のスナップショットを学習データ、将来のリンクをテストデータとします。ランダム分割ではなく時間分割を行うことで、実運用時の性能をより正確に評価できます。
ステップ2: 候補ペアの特徴量算出
対象となるノードペアごとに、共通近傍数やJaccard係数などの構造指標を算出します。ノード属性が利用可能であれば、属性の類似度も特徴量に含めます。
ステップ3: モデルの学習と評価
正例（実際にリンクが形成されたペア）と負例（リンクが形成されなかったペア）でモデルを学習します。AUC-ROCやPrecision@Kなどの指標で評価し、ビジネス要件に合った閾値を設定します。
ステップ4: 結果の活用
予測スコアの高いペアをリストアップし、推薦や施策に反映します。定期的にモデルを再学習し、ネットワークの変化に追従させます。
活用場面
- 友人推薦: SNSで「知り合いかも」機能として、つながる可能性の高いユーザーペアを提示します
- 商品推薦: 購買ネットワーク上のリンク予測で、関連商品のレコメンデーションを生成します
- 知識グラフ補完: 企業内の知識グラフにおける欠損リンクを予測し、情報の網羅性を高めます
- 共著予測: 学術ネットワーク上で、将来共同研究する可能性の高い研究者ペアを特定します
- 不正検知: 取引ネットワーク上の異常なリンクパターンを検出し、不正の兆候を捉えます
注意点
負例のサンプリングバイアスに注意する
リンクが存在しないペアは膨大な数になるため、負例のサンプリング方法が結果に大きく影響します。ランダムサンプリングでは容易に区別できるペアが多くなり、モデルの性能が過大評価されるリスクがあります。
時間的リークを防ぐ
学習データとテストデータの分割で時間の前後関係を守らないと、将来の情報が学習に混入してしまいます。実運用では得られない情報でモデルが学習してしまう「リーク」は精度の大幅な過大評価につながります。
コールドスタート問題への対処
新しくネットワークに参加したノードは構造情報が乏しいため、構造ベースの手法だけでは予測精度が低下します。ノード属性やコンテンツ情報を補助的に活用する設計が必要です。
リンク予測の結果を自動的にアクションにつなげる際は、偽陽性の影響を十分に検討してください。不正検知では無関係なペアを誤って不正と判定するリスクがあり、推薦システムではプライバシーを侵害する推薦（非公開の関係の暴露など）を生む可能性があります。予測結果は必ず人間のレビューを経てから施策に反映する運用設計を推奨します。
まとめ
リンク予測は、ネットワーク構造から未知の関係性の出現を予測する実用的な手法です。共通近傍やJaccard係数といったシンプルな指標から、GNNを用いた高度な手法まで、目的と規模に応じた選択肢があります。推薦、知識グラフ補完、不正検知など幅広い領域で価値を発揮しますが、負例サンプリングや時間的リークなどの評価上の落とし穴に注意が必要です。