SNSで「知り合いかも？」と表示される候補は、どうやって選ばれているのでしょうか。あなたと友人Aが友達で、AとBも友達なら、あなたとBもいずれつながりそうだ——この「まだ存在しないが、存在しそうなつながり」を当てるのがリンク予測（link prediction）です。観測されたグラフの構造を手がかりに、いま辺（エッジ）が張られていない2つのノードの間に、将来辺ができる確率を推定します。
上の図がリンク予測の全体像です。入力グラフの点線エッジ（未観測）を予測したい。GraphSAGEエンコーダが各ノードを埋め込みベクトル $\bm{z}_v$ に変換し、内積デコーダがノードペアのスコアを計算、シグモイドを通して確率 $\hat{p} = 0.84$ のような値が出てきます。「似たノードはつながりやすい」という仮定が、ベクトルの内積という数学的操作に変換されている様子が一目でわかります。
リンク予測は地味な問題に見えて、応用先は驚くほど広いです。たとえば次のような場面で中心的な役割を果たします。
- 推薦システム — ユーザーと商品を2種類のノードとみなし、「ユーザーが買いそうな商品」をユーザー＝商品間のリンク予測として解く。AmazonやNetflixの推薦の土台です。
- 創薬・タンパク質相互作用 — タンパク質同士の相互作用ネットワークや、薬と標的の相互作用グラフで、まだ実験されていない相互作用を予測し、実験コストを削減します。
- 知識グラフ補完 — 「東京 —首都—→ 日本」のような知識グラフで、欠けている関係（エッジ）を補う。
この記事では、リンク予測を二値分類問題として厳密に定式化し、ノード埋め込みの内積によるスコア $s(u,v) = \bm{z}_u^\top \bm{z}_v$ と、ネガティブサンプリングのもとでの交差エントロピー損失を一行ずつ導出します。さらに、観測エッジを訓練・検証・テストに分割する際に必ず守るべきデータリーク回避の作法、ROC-AUC と Average Precision による評価、そして GraphSAGE エンコーダと内積デコーダの PyTorch 実装までを通して、リンク予測を最後まで自分の手で組めるようにします。
本記事の内容
- リンク予測を二値分類として定式化し、内積デコーダとロジスティック損失を導出する
- ネガティブサンプリングとエッジ分割（train/val/test）の正しい手順とデータリーク回避を理解する
- GraphSAGE エンコーダ＋内積デコーダを PyTorch で実装し、ROC-AUC・AP で評価して隣接行列再構成を可視化する
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- グラフニューラルネットワーク（GNN）とは — グラフ上でノード特徴を伝播・集約する枠組み。リンク予測のエンコーダの基礎です。
- GraphSAGEの理論 — 近傍をサンプリングして集約する帰納的GNN。本記事のエンコーダに使います。
- グラフラプラシアン — グラフの構造を行列で表す基礎。隣接行列・次数行列の扱いに慣れておくと読みやすくなります。
これらの記事で扱った「ノードを低次元ベクトルに埋め込む」という発想が、リンク予測の出発点になります。それでは、まずリンク予測とは何を当てる問題なのかを直感から押さえていきましょう。
リンク予測とは
友人関係のネットワークを思い浮かべてください。すでに引かれている友情の線（観測エッジ）はわかっています。リンク予測がやりたいのは、「いま線が引かれていない2人」のすべてのペアについて、そこに線が引かれるべきか（引かれそうか）を点数付けすることです。点数が高いペアほど、辺が存在する可能性が高いと判断します。
ここで本質的な仮定があります。それは「似たノードはつながりやすい」というものです。SNSなら、同じ趣味・同じ地域・共通の友人を多く持つ人同士はつながりやすい。タンパク質なら、似た機能・似た構造を持つもの同士が相互作用しやすい。つまり、各ノードの「性質」をうまく数値ベクトルに落とし込めれば、2つのベクトルの近さがリンクの張られやすさを表すはずだ、という戦略が立ちます。
この「ノードの性質を表す数値ベクトル」をノード埋め込み（node embedding） $\bm{z}_v \in \mathbb{R}^d$ と呼びます。リンク予測は次の2段階に分解できます。
- エンコーダ — グラフの構造とノード特徴から、各ノード $v$ の埋め込み $\bm{z}_v$ を作る。GNN（GCNやGraphSAGE）がこの役を担います。
- デコーダ — 2つの埋め込み $\bm{z}_u, \bm{z}_v$ を受け取り、エッジが存在する確率（スコア）に変換する。内積などを使います。
教科書的に言えば、リンク予測とは「観測されたエッジ集合 $E_{\text{obs}}$ をもとに、ノードペア $(u, v) \notin E_{\text{obs}}$ に対してエッジ存在の確率 $P\big(\,(u,v) \in E\,\big)$ を推定する問題」です。注意したいのは、これは未観測ペアのランキング問題でもあるという点です。多くの応用（推薦・創薬）では、全ペアの確率の絶対値そのものより、「確率が高い順に並べたとき、本物のエッジが上位に来るか」が重要になります。だからこそ後で AUC や AP といったランキング指標で評価するわけです。
このように、リンク予測は「エンコーダで埋め込みを作り、デコーダでスコアにし、二値分類として学習する」という構図に落ちます。次は、このデコーダの最もシンプルかつ強力な形である内積デコーダを定式化しましょう。
内積デコーダの定式化
2つのノード埋め込み $\bm{z}_u, \bm{z}_v \in \mathbb{R}^d$ から、エッジが存在する確率を作りたいとします。最も素直な「2ベクトルの近さ」の測り方は内積です。
$$ \begin{equation} s(u, v) = \bm{z}_u^\top \bm{z}_v = \sum_{k=1}^{d} z_{u,k}\, z_{v,k} \end{equation} $$
なぜ内積でよいのでしょうか。内積は $\bm{z}_u^\top \bm{z}_v = \|\bm{z}_u\|\,\|\bm{z}_v\|\cos\theta$ と書けるので、2つの埋め込みが同じ向きを向いている（$\cos\theta$ が大きい）ほど、また大きさが揃っているほど大きくなります。「似たノードはつながりやすい」という仮定を、ベクトルの向きの一致として表現したものが内積スコアだ、と理解できます。
左の図はシグモイド関数の形状を示しています。内積スコアが正（埋め込みが同じ向き）なら確率は 0.5 を超え、負（逆向き）なら 0.5 を下回ります。右の図はそのスコアと角度の関係で、2つの埋め込みベクトルのなす角度が 90 度未満（同じ向き）ではエッジ確率が高く、90 度を超えると急速に低下することがわかります。「似たノードはつながりやすい」を数式で表すとこの曲線になるのです。
ただし内積スコア $s(u,v)$ は $-\infty$ から $+\infty$ までの任意の実数を取りうるので、これをそのまま確率とは呼べません。確率は $[0,1]$ に収まる必要があります。そこでロジスティックシグモイド関数を通します。
$$ \begin{equation} \hat{p}(u,v) = \sigma\big(s(u,v)\big) = \sigma\big(\bm{z}_u^\top \bm{z}_v\big), \qquad \sigma(x) = \frac{1}{1 + e^{-x}} \end{equation} $$
シグモイドは、入力が大きな正の値なら出力を1に、大きな負の値なら0に、0付近ならなだらかに0.5付近にマッピングします。これで「内積が大きい（似ている）ペアほどエッジ確率が1に近い」という性質が、確率の言葉で表現できました。
ここで $\sigma$ の便利な性質を2つ確認しておきます。後の損失の導出で使います。第一に、$1 – \sigma(x) = \sigma(-x)$ が成り立ちます。実際、
$$ 1 – \sigma(x) = 1 – \frac{1}{1+e^{-x}} = \frac{e^{-x}}{1+e^{-x}} = \frac{1}{e^{x}+1} = \sigma(-x) $$
と計算できます。第二に、$\sigma$ の微分は $\sigma'(x) = \sigma(x)\big(1-\sigma(x)\big)$ です。商の微分から $\sigma'(x) = e^{-x}/(1+e^{-x})^2 = \sigma(x)\sigma(-x) = \sigma(x)(1-\sigma(x))$ と導けます。
内積デコーダの長所は、パラメータを持たず（埋め込みだけで決まる）、計算が軽く、全ペアのスコアが行列積 $\bm{Z}\bm{Z}^\top$ で一括計算できる点です。一方で「内積は対称（$s(u,v)=s(v,u)$）なので無向グラフ向き」「向き付きや関係種別を区別したいなら DistMult や双線形デコーダ $\bm{z}_u^\top \bm{R}\, \bm{z}_v$ が必要」という限界もあります。本記事では最も基本的な無向グラフ＋内積デコーダに集中します。
スコアを確率に変えるところまで来ました。ではこの確率を、観測データに最もよく合うように学習するには、どんな損失を最小化すればよいのでしょうか。次節で交差エントロピー損失を導出します。
ロジスティック損失の導出
学習とは、エンコーダのパラメータ（GNNの重み）を調整して、できあがる埋め込み $\bm{z}_v$ が「本物のエッジには高い確率、エッジでないペアには低い確率」を出すようにすることです。これを定式化するために、各ノードペアを二値ラベル付きのデータ点とみなします。
エッジが存在するペア（正例）には $y = 1$、エッジが存在しないペア（負例）には $y = 0$ を割り当てます。1つのペア $(u,v)$ に対し、モデルは「エッジあり確率」$\hat{p} = \sigma(s)$ を出します。すると、観測ラベル $y$ が得られる確率は、ベルヌーイ分布で書けます。
$$ \begin{equation} P(y \mid u, v) = \hat{p}^{\,y}\,(1-\hat{p})^{\,1-y} \end{equation} $$
$y=1$ なら右辺は $\hat{p}$、$y=0$ なら $1-\hat{p}$ になり、確かに意図どおりです。ここで最尤推定の方針を取ります。すべての観測ペア $\mathcal{D}$ が独立だと仮定すると、データ全体の尤度はその積です。
$$ L = \prod_{(u,v,y) \in \mathcal{D}} \hat{p}_{uv}^{\,y}\,(1-\hat{p}_{uv})^{\,1-y} $$
積のままでは扱いにくいので、対数を取って和に変えます（対数は単調増加なので、最尤点は変わりません）。対数尤度は
$$ \log L = \sum_{(u,v,y) \in \mathcal{D}} \Big[\, y \log \hat{p}_{uv} + (1-y)\log(1-\hat{p}_{uv}) \,\Big] $$
となります。最尤推定は対数尤度を最大化しますが、機械学習では「損失を最小化」という形に揃えたいので、符号を反転して負の対数尤度（交差エントロピー損失）を定義します。
$$ \begin{equation} \mathcal{L} = -\sum_{(u,v,y) \in \mathcal{D}} \Big[\, y \log \hat{p}_{uv} + (1-y)\log(1-\hat{p}_{uv}) \,\Big] \end{equation} $$
これがロジスティック損失（二値交差エントロピー, BCE）です。$y=1$ のとき項は $-\log\hat{p}$ となり、$\hat{p}$ が1に近いほど損失が小さくなります。$y=0$ のとき項は $-\log(1-\hat{p})$ となり、$\hat{p}$ が0に近いほど損失が小さくなります。つまり「正例は確率1へ、負例は確率0へ」と押し進める力を、この一つの式が同時に与えているのです。
左の図で、正例の損失（緑の曲線）は $\hat{p} \to 1$ に向かって急速にゼロになり、負例の損失（赤の曲線）は $\hat{p} \to 0$ に向かってゼロになることが確認できます。右の図はその「押し力」を直感的に示したもので、正例は右へ（確率を高く）、負例は左へ（確率を低く）と矢印が指しています。この非対称な力のバランスが、埋め込みを「正例は近く・負例は遠く」という構造に整理していきます。
次に、リンク予測の文脈で実際に使う形に書き直します。正例は観測エッジ集合 $E$ から、負例はサンプリングした非エッジ集合 $E^-$ から取ります。$\hat{p}_{uv} = \sigma(\bm{z}_u^\top \bm{z}_v)$ を代入し、$1 – \sigma(s) = \sigma(-s)$ の性質を使うと、損失は次のように整理できます。
$$ \begin{equation} \mathcal{L} = -\sum_{(u,v) \in E} \log \sigma\big(\bm{z}_u^\top \bm{z}_v\big) \;-\; \sum_{(u,v) \in E^-} \log \sigma\big(-\bm{z}_u^\top \bm{z}_v\big) \end{equation} $$
第1項は「正例のスコアを大きく」、第2項は「負例のスコアを小さく（$-s$ を大きく＝ $s$ を小さく）」しようとする力です。この形はワード埋め込みの skip-gram with negative sampling とまったく同じ構造をしており、リンク予測がノード版の「文脈予測」だと見ることもできます。
ここで一つ大きな疑問が残ります。負例 $E^-$ はどう作ればよいのでしょうか。グラフでは、エッジが存在しないペアの数は存在するペアの数より圧倒的に多い（疎なグラフでは $O(N^2)$ 対 $O(N)$）ため、全非エッジを使うのは計算量的にも不均衡の面でも非現実的です。ここで登場するのがネガティブサンプリングです。次節で詳しく見ていきます。
ネガティブサンプリング
実世界のグラフはほとんどが疎（スパース）です。$N$ ノードのグラフで、エッジ数 $|E|$ はせいぜい $O(N)$ 程度ですが、ノードペアの総数は $\binom{N}{2} = O(N^2)$ あります。たとえば $N = 10{,}000$ なら、ペアは約5000万あるのにエッジは数万本、という具合です。
この事実は2つの問題を生みます。第一に、全非エッジを負例にすると計算量が $O(N^2)$ になり大規模グラフでは破綻します。第二に、負例が正例より桁違いに多いため、損失が「ほとんど全部を0と予測する」自明解に支配され、正例の信号が埋もれてしまいます（クラス不均衡）。
ネガティブサンプリングは、この両方を一度に解決します。正例エッジ1本ごとに（あるいはバッチ全体に対して）、エッジが存在しないペアをランダムに少数だけ抜き出して負例とするのです。典型的には、正例と同数の負例をサンプリングします（1:1）。これにより損失の総和は $O(|E|)$ に収まり、クラスバランスも保たれます。
最もシンプルなサンプリング法は一様ネガティブサンプリングです。ノードを2つ一様ランダムに選び、それが既存エッジでなければ負例として採用する、という手続きです。
- ノード $u$ を一様ランダムに選ぶ。
- ノード $v$ を一様ランダムに選ぶ（$u \ne v$）。
- $(u,v) \in E$ なら棄却して1に戻る。そうでなければ負例 $(u,v)$ として採用する。
疎なグラフでは「ランダムに選んだペアがたまたま既存エッジである」確率は $|E| / \binom{N}{2} \approx O(1/N)$ と非常に小さいので、棄却はめったに起きず効率的です。実装では、棄却すらせず「サンプルした負例の中に偶然エッジが混じってもごく少数なのでノイズとして無視する」近似もよく使われます。
GNNを使わないシンプルな代替として、グラフの構造的な統計量から直接スコアを計算するヒューリスティックスコアがあります。代表的なものが共通近傍数（Common Neighbors）、Adamic-Adar指数、Resource Allocation指数の3つです。
$$ \text{CN}(u,v) = |N(u) \cap N(v)|, \qquad \text{AA}(u,v) = \sum_{w \in N(u) \cap N(v)} \frac{1}{\log |N(w)|}, \qquad \text{RA}(u,v) = \sum_{w \in N(u) \cap N(v)} \frac{1}{|N(w)|} $$
共通近傍数は単純に2つのノードの共通隣人の数です。Adamic-Adar は共通隣人 $w$ の次数が小さいほど（希少なハブを共有しているほど）大きく重み付けします。Resource Allocation はさらに強く次数で割り引きます。
3つのヒストグラムがいずれも「正例（実エッジ、緑）は高スコア、負例（非エッジ、赤）は低スコア」に分離していることが確認できます。SBMグラフでは、コミュニティ内ノードが多くの共通近傍を持つため、3手法ともある程度有効に機能します。AUC値はすべて0.8を超えており、GNNを使わなくてもグラフ構造だけでかなりの予測精度が得られることがわかります。ただし、ノード属性やグローバルな構造を活用できないため、GNNに比べて表現力に限界があります。
サンプリングには発展形もあります。skip-gram に倣い、ノードの次数の $3/4$ 乗に比例した確率でサンプリングすると、高次数ノードを適度に重視しつつ低次数ノードも拾えることが知られています。
$$ P_{\text{neg}}(v) \propto \deg(v)^{3/4} $$
また、「学習が進んだモデルが間違えやすい難しい負例（埋め込みが近いのにエッジでないペア）」を優先的に選ぶハードネガティブサンプリングもあり、収束を速めますが、実装が複雑になります。本記事では基本の一様サンプリングを使います。
左の図はノード数が増えるほどエッジの割合が急激に小さくなることを対数スケールで示しています。N=10,000 では全ペアの 0.006% 未満しかエッジがなく、全非エッジを負例にすることがいかに非現実的かがわかります。右の図では、ネガティブサンプリングを使うことで負例数を正例数と揃えられ（1:1）、損失が自明解に支配されるのを防げることが一目瞭然です。計算量の問題とクラス不均衡を同時に解決する、シンプルながら強力な工夫です。
ネガティブサンプリングで負例を用意できました。しかしここで、リンク予測特有の最大の落とし穴が待っています。それは「どのエッジを訓練に使い、どのエッジで評価するか」というデータ分割です。やり方を間違えると、評価が信用できない数字になってしまいます。次節で正しい手順を押さえましょう。
エッジ分割とデータリーク回避
通常の教師あり学習では、データ点（行）をランダムに train/val/test に分けます。しかしリンク予測では、データ点が「エッジ」であり、しかもそのエッジ自体がエンコーダ（GNN）の入力であるグラフ構造を構成しているという、二重の役割を持ちます。ここにデータリークの罠があります。
具体的に考えましょう。GNN は、ノード $v$ の埋め込みを「$v$ の近傍ノードの特徴を集約」して作ります。いま、エッジ $(u,v)$ をテスト用の正解として隠したいとします。ところが、もしこのエッジ $(u,v)$ をグラフのメッセージパッシングに使ってしまうと、$u$ の埋め込みは $v$ の情報を、$v$ の埋め込みは $u$ の情報を直接受け取ります。すると内積 $\bm{z}_u^\top \bm{z}_v$ は「答えを見て」高い値を出すようになり、テストAUCが不当に高く出ます。これがリンク予測のデータリークです。
これを防ぐ鉄則は次の通りです。
テスト・検証用に予測したいエッジは、エンコーダのメッセージパッシング（グラフの隣接構造）からも除外しなければならない。
そこで、エッジを次の3つの役割に分けて管理します。
| 用語 | 役割 |
|---|---|
| メッセージパッシング用エッジ | GNNが埋め込みを計算するときに使う隣接構造。グラフの「骨格」 |
| 教師（supervision）用エッジ | 損失計算の正例として使うエッジ（ラベル $y=1$） |
| 評価用エッジ（val/test） | AUC等の評価でだけ使い、訓練のどこにも漏らさないエッジ |
標準的な手順（トランスダクティブ設定）は次の通りです。
- 全エッジ $E$ をランダムに分割する。例：80% を訓練、10% を検証、10% をテスト。
- 訓練グラフ $G_{\text{train}}$ は、訓練エッジ「だけ」を隣接構造として持つ。検証・テストエッジは取り除く。
- エンコーダは常に $G_{\text{train}}$ の隣接構造でメッセージパッシングする。
- 訓練の損失計算では、訓練エッジを正例、訓練グラフ上でサンプリングした非エッジを負例とする。
- 検証・テストでは、隠しておいた検証・テストエッジを正例、別途サンプリングした非エッジを負例として、AUC等を測る。この評価用エッジはステップ3のメッセージパッシングには絶対に含めない。
さらに細かいリークにも注意が必要です。負例をサンプリングするとき、「テストの正例エッジ」をうっかり訓練の負例として選んでしまうと、それも軽微なリークになります（テストで正解になるエッジを訓練で「負」と教えてしまう）。厳密には、負例サンプリング時に全エッジ集合 $E$（train/val/test すべて）を除外するのが安全です。実用的な実装では、PyTorch Geometric の train_test_split_edges や RandomLinkSplit がこれらの分割を一括で正しく行ってくれます。
ノードに特徴ベクトルがあり、訓練時に存在しなかった新しいノードのリンクも予測したい場合は、インダクティブ設定になります。この場合は GraphSAGE のような帰納的GNNを使い、未知ノードでも近傍集約で埋め込みを作れるようにします。本記事のエンコーダに GraphSAGE を選ぶのは、この拡張性を見据えてのことです。
この図が「どのエッジを何に使うか」の全体像を整理しています。全エッジを訓練80%・検証10%・テスト10%に分けた後、訓練エッジは「GNNのメッセージパッシング（隣接行列）」と「損失計算の正例」の2役を担います。一方、検証・テストエッジは「評価専用」として切り離されており、メッセージパッシングには絶対に使いません。この分離がリンク予測の最重要ルールで、守られていないとテストAUCが不当に高く見えてしまいます。
正しい分割が用意できれば、あとは学習の良し悪しをどう測るかです。リンク予測はクラス不均衡なランキング問題なので、単純な正解率（accuracy）は不適切です。次節で AUC と AP という適切な指標を導入します。
評価指標：ROC-AUC と Average Precision
なぜ正解率（accuracy）ではダメなのでしょうか。リンク予測は本質的にクラス不均衡で、しかも「閾値をどこに置くか」を決め打ちしにくい問題です。極端な話、すべてのペアを「エッジなし」と予測すれば、疎なグラフでは正解率はほぼ100%になりますが、何の役にも立ちません。必要なのは「正例に高いスコア、負例に低いスコアを付けられているか」という順位付けの良さを測る指標です。
ROC-AUC
ROC曲線は、判定閾値を $+\infty$ から $-\infty$ まで動かしたときの、偽陽性率（FPR）を横軸、真陽性率（TPR）を縦軸にプロットした曲線です。
$$ \text{TPR} = \frac{TP}{TP + FN}, \qquad \text{FPR} = \frac{FP}{FP + TN} $$
その曲線下の面積が AUC（Area Under the Curve）です。AUCには非常に直感的な確率的解釈があります。
$$ \begin{equation} \text{AUC} = P\big(\, s(\text{正例}) > s(\text{負例}) \,\big) \end{equation} $$
つまり「正例を1つ、負例を1つランダムに選んだとき、正例のスコアの方が高い確率」です。AUC = 1.0 は完璧な順位付け、AUC = 0.5 はランダム（コイン投げと同じ）を意味します。閾値に依存せず、クラス不均衡にも比較的頑健なので、リンク予測の標準指標になっています。
この確率的解釈から、AUCを直接計算する素朴な方法も見えます。正例スコア集合 $S^+$ と負例スコア集合 $S^-$ の全ペアを比べ、正例が勝った割合を数えればよいのです。
$$ \text{AUC} = \frac{1}{|S^+|\,|S^-|}\sum_{s^+ \in S^+}\sum_{s^- \in S^-}\Big[\mathbb{1}(s^+ > s^-) + \tfrac{1}{2}\mathbb{1}(s^+ = s^-)\Big] $$
同点のときに $1/2$ を加えるのは、ROC曲線上の同点による「斜め」の寄与を正しく数えるためです。
Average Precision（AP）
もう一つの重要指標が Average Precision（PR曲線下の面積）です。適合率（precision）を縦軸、再現率（recall）を横軸に取ったPR曲線の下の面積で、
$$ \text{Precision} = \frac{TP}{TP+FP}, \qquad \text{Recall} = \frac{TP}{TP+FN} $$
と定義されます。APは「上位に正例をどれだけ集められたか」を測るので、負例が圧倒的に多い極端な不均衡のとき、AUCより厳しく性能を映し出します。AUCは負例が多くてもFPRの分母が大きいため高く出やすいのに対し、APはFP（誤って正と予測した負例）の混入にずっと敏感です。創薬や推薦のように「上位数件だけが重要」な応用では、APの方が実務に即した指標になります。
実務では両方を併記するのが定石です。AUCで全体の順位付け能力を、APで上位の精度を確認します。理論が出そろったので、いよいよ GraphSAGE エンコーダと内積デコーダを実装して、これらの指標で評価していきましょう。
Python実装
ここからは、これまでの理論を PyTorch で実装します。グラフは PyTorch Geometric を使わず、できるだけスクラッチに近い形で組み、内部で何が起きているかが見えるようにします。流れは次の通りです。
- 合成グラフ（コミュニティ構造を持つ確率的ブロックモデル）を生成する。
- エッジを train/val/test に分割する（リーク回避）。
- GraphSAGE 層を実装してエンコーダを作る。
- 内積デコーダ＋BCE損失で学習する。
- ROC-AUC と AP で評価し、隣接行列の再構成をヒートマップで可視化する。
まずは必要なライブラリと、コミュニティ構造を持つグラフを作るところからです。確率的ブロックモデル（SBM）は「同じコミュニティ内は高確率で、異なるコミュニティ間は低確率でエッジを張る」モデルで、リンク予測がうまくいくべき構造（コミュニティ）を意図的に埋め込めます。
import numpy as np
import torch
import torch.nn as nn
import torch.nn.functional as F
import matplotlib.pyplot as plt
torch.manual_seed(0)
np.random.seed(0)
# --- 確率的ブロックモデル(SBM)で合成グラフを生成 ---
def make_sbm(sizes, p_in, p_out):
"""sizes: 各コミュニティのノード数, p_in: 同コミュニティ内エッジ確率, p_out: 異コミュニティ間"""
N = sum(sizes)
# 各ノードのコミュニティラベルを作る
comm = np.concatenate([np.full(s, i) for i, s in enumerate(sizes)])
edges = []
for i in range(N):
for j in range(i + 1, N):
p = p_in if comm[i] == comm[j] else p_out
if np.random.rand() < p:
edges.append((i, j))
return N, comm, np.array(edges)
# 3コミュニティ、各40ノード
N, comm, edges = make_sbm([40, 40, 40], p_in=0.15, p_out=0.01)
print(f"ノード数: {N}, エッジ数: {len(edges)}")
print(f"エッジ密度: {2*len(edges)/(N*(N-1)):.4f}")
このコードは3つのコミュニティ（各40ノード、計120ノード）からなる無向グラフを生成します。コミュニティ内のエッジ確率を0.15、コミュニティ間を0.01に設定しているので、出力されるエッジの大半は同じコミュニティ内に集中します。エッジ密度が数%と低い、現実的に疎なグラフになっていることが出力から確認できます。この「コミュニティ内は密、コミュニティ間は疎」という構造こそ、内積デコーダが学習で捉えるべきパターンです。
3色のコミュニティが円弧状に配置されており、同色ノード間（同じコミュニティ内）は青・橙・緑のエッジで密につながり、異色ノード間（コミュニティ間）はほとんどエッジがないことが見て取れます。リンク予測はこのコミュニティ構造を「教師なし」で発見する問題です。ノードの色ラベルを損失に使わず、エッジの有無だけから学習することに注目してください。
次に、リーク回避の核心であるエッジ分割を行います。前節で述べた通り、検証・テストエッジは訓練グラフの隣接構造から完全に取り除きます。
# --- エッジを train/val/test に分割 ---
def split_edges(edges, val_ratio=0.1, test_ratio=0.1):
perm = np.random.permutation(len(edges))
n_val = int(len(edges) * val_ratio)
n_test = int(len(edges) * test_ratio)
val_e = edges[perm[:n_val]]
test_e = edges[perm[n_val:n_val + n_test]]
train_e = edges[perm[n_val + n_test:]]
return train_e, val_e, test_e
train_e, val_e, test_e = split_edges(edges)
print(f"train: {len(train_e)}, val: {len(val_e)}, test: {len(test_e)}")
# 訓練グラフの隣接構造(メッセージパッシング用)は train_e のみで作る
def build_adj(N, edges):
A = torch.zeros(N, N)
for u, v in edges:
A[u, v] = 1.0
A[v, u] = 1.0 # 無向グラフなので対称化
return A
A_train = build_adj(N, train_e) # これだけをGNNに渡す
ここがデータリーク回避の要です。A_train は訓練エッジ「だけ」で構成された隣接行列であり、検証・テストエッジは一切含まれていません。後で作る GNN はこの A_train の上でのみメッセージパッシングを行うため、テストで予測したいエッジの情報が埋め込みに漏れることはありません。検証・テストエッジは「正解ラベル」としてのみ使われます。
続いて、メッセージパッシングのための正規化隣接行列を準備します。GraphSAGE の mean 集約は、近傍特徴の平均を取るので、次数で割る正規化が必要です。自己ループを加えて「自分自身の特徴」も集約に含めるのが一般的です。
# --- GraphSAGE(mean集約)用の正規化隣接行列 ---
def normalize_adj_mean(A):
N = A.size(0)
A_hat = A + torch.eye(N) # 自己ループを追加
deg = A_hat.sum(dim=1, keepdim=True) # 各ノードの次数(自己ループ込み)
A_norm = A_hat / deg # 行ごとに次数で割る = 近傍平均
return A_norm
A_norm = normalize_adj_mean(A_train)
# ノード初期特徴: ここでは単位行列(各ノードを区別するone-hot)を使う
X = torch.eye(N)
A_norm は各行の和が1になるように正規化された行列で、A_norm @ H を計算すると各ノードについて「自分と近傍の特徴の平均」が得られます。これがGraphSAGEのmean集約の正体です。ノード初期特徴 X には、属性データがない設定を想定して単位行列（各ノードを区別するone-hotベクトル）を使っています。属性がある実データでは、ここに実際の特徴量を入れます。
いよいよGraphSAGEエンコーダを定義します。1層のGraphSAGEは「自分の特徴」と「近傍の集約特徴」を結合（または足し合わせ）して線形変換し、非線形活性化を通します。ここでは結合方式で実装します。
# --- GraphSAGE層 ---
class SAGELayer(nn.Module):
def __init__(self, in_dim, out_dim):
super().__init__()
# 自分の特徴と近傍集約特徴を結合(2*in_dim)してから線形変換
self.lin = nn.Linear(2 * in_dim, out_dim)
def forward(self, H, A_norm):
neigh = A_norm @ H # 近傍(+自己)の平均集約
out = torch.cat([H, neigh], dim=1) # 自分の特徴と結合
return self.lin(out)
# --- エンコーダ(2層GraphSAGE) ---
class Encoder(nn.Module):
def __init__(self, in_dim, hid_dim, out_dim):
super().__init__()
self.sage1 = SAGELayer(in_dim, hid_dim)
self.sage2 = SAGELayer(hid_dim, out_dim)
def forward(self, X, A_norm):
h = F.relu(self.sage1(X, A_norm)) # 1層目+ReLU
z = self.sage2(h, A_norm) # 2層目: ノード埋め込み z
return z
このエンコーダは2層構成です。1層目で近傍1ホップ、2層目でさらにその近傍（2ホップ）の情報まで集約されるため、各ノードの埋め込みには周囲2ホップの構造が反映されます。最終出力 z が各ノードの埋め込み $\bm{z}_v$ で、これを内積デコーダに渡します。GraphSAGEを使っているので、原理的には訓練時に見ていない新規ノードでも近傍さえあれば埋め込みを作れます（インダクティブ性）。
中央の青いノード $v$ に対して、5つの隣接ノード $u_1 \sim u_5$ からオレンジの矢印で情報が集まってきます。GraphSAGE は「自分の特徴ベクトル $h_v$」と「近傍特徴の平均 $\mathrm{mean}_{u \in N(v)} h_u$」を横に結合（concat）してから線形変換する、という操作を繰り返します。各ノードが2ホップ先までの構造情報を取り込んだ埋め込みになる仕組みです。
次に、内積デコーダとネガティブサンプリング、そしてBCE損失を実装します。前節で導出した損失 $\mathcal{L} = -\sum_{E}\log\sigma(\bm{z}_u^\top\bm{z}_v) – \sum_{E^-}\log\sigma(-\bm{z}_u^\top\bm{z}_v)$ をそのままコードに落とします。
# --- 内積デコーダ: エッジリストのスコアを計算 ---
def decode(z, edge_index):
# edge_index: (E,2) のノードペア。各ペアの内積を取る
src, dst = edge_index[:, 0], edge_index[:, 1]
return (z[src] * z[dst]).sum(dim=1) # s(u,v) = z_u . z_v
# --- 一様ネガティブサンプリング ---
def sample_neg(N, num, edge_set):
negs = []
while len(negs) < num:
u, v = np.random.randint(N), np.random.randint(N)
if u != v and (u, v) not in edge_set and (v, u) not in edge_set:
negs.append((u, v))
return torch.tensor(negs, dtype=torch.long)
# 全エッジ集合(分割前)を負例除外に使う = リークの完全回避
edge_set = set(map(tuple, edges))
train_pos = torch.tensor(train_e, dtype=torch.long)
decode 関数は埋め込み行列 z とノードペアのリストを受け取り、各ペアの内積スコアをベクトルで一括計算します。sample_neg は一様ネガティブサンプリングで、u != v かつ既存エッジでないペアだけを採用しています。負例除外には分割前の全エッジ集合 edge_set を使っており、テスト正例を訓練負例に取り込む軽微なリークまで防いでいます。
学習ループを実装します。各エポックで訓練エッジ（正例）と同数の負例をサンプリングし、BCE損失を最小化します。
# --- モデルと最適化器 ---
model = Encoder(in_dim=N, hid_dim=64, out_dim=32)
opt = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)
bce = nn.BCEWithLogitsLoss() # 内部でsigmoid+BCEを安定計算
# --- 学習ループ ---
for epoch in range(1, 201):
model.train()
opt.zero_grad()
z = model(X, A_norm) # エンコーダで全ノード埋め込み
# 正例と同数の負例をサンプリング
neg = sample_neg(N, len(train_pos), edge_set)
pos_score = decode(z, train_pos) # 正例スコア
neg_score = decode(z, neg) # 負例スコア
# ラベル: 正例=1, 負例=0
scores = torch.cat([pos_score, neg_score])
labels = torch.cat([torch.ones(len(pos_score)),
torch.zeros(len(neg_score))])
loss = bce(scores, labels) # BCE(=導出したロジスティック損失)
loss.backward()
opt.step()
if epoch % 40 == 0:
print(f"epoch {epoch:3d} loss {loss.item():.4f}")
BCEWithLogitsLoss は内部でシグモイドとBCEを数値的に安定な形で同時に計算してくれるので、decode の出力（ロジット＝シグモイド前のスコア）をそのまま渡します。これは前節で導出した交差エントロピー損失そのものです。エポックが進むにつれて損失が減っていけば、埋め込みが「正例の内積を大きく、負例の内積を小さく」する方向に学習できている証拠です。
左のグラフで、訓練損失（青）がエポックとともに減少し、それに連動して検証AUC（橙の点線）が上昇していることが確認できます。右のグラフは最終的なテストセットの評価で、ROC-AUC 0.8000、Average Precision 0.7839 を達成しました（どちらもランダムの 0.5 を大きく上回っています）。SBMグラフのコミュニティ構造が、コミュニティラベルを与えなくてもエッジの有無だけから学習できている証拠です。
学習が終わったら、テストエッジで ROC-AUC と AP を評価します。指標は scikit-learn を使います（理論で確認した確率的解釈と一致します）。
from sklearn.metrics import roc_auc_score, average_precision_score
# --- 評価: テストエッジ(正例)とサンプリング負例で測る ---
model.eval()
with torch.no_grad():
z = model(X, A_norm) # 訓練グラフ上の埋め込み(テストエッジは隣接に含まない)
test_pos = torch.tensor(test_e, dtype=torch.long)
test_neg = sample_neg(N, len(test_pos), edge_set)
pos_s = torch.sigmoid(decode(z, test_pos)).numpy()
neg_s = torch.sigmoid(decode(z, test_neg)).numpy()
y_true = np.concatenate([np.ones(len(pos_s)), np.zeros(len(neg_s))])
y_score = np.concatenate([pos_s, neg_s])
auc = roc_auc_score(y_true, y_score)
ap = average_precision_score(y_true, y_score)
print(f"Test ROC-AUC: {auc:.4f}")
print(f"Test AP: {ap:.4f}")
評価時のポイントは、埋め込み z を計算するのに使う A_norm が訓練グラフ由来である点です。テストエッジは隣接構造に含まれていないので、内積スコアは「答えを見ずに」予測した値になります。コミュニティ構造のあるSBMでは、AUC・APともに0.8前後の値が得られます（seed・グラフ構造により変動します）。AUCが0.5を大きく上回ることが、埋め込みがコミュニティ構造を捉えてリンクを正しく順位付けできている証拠です。
左のROC曲線は点線（ランダム = 対角線）から大きく上に離れており、AUC = 0.8000 は「正例と負例をランダムに1つずつ選んだとき、正例のスコアの方が高い確率が80%」を意味します。右のPR曲線は適合率と再現率のトレードオフを示しており、AP = 0.7839 は「上位に正例をまとめて取れている」ことを表します。両指標を見比べることで、単純なAUCでは見えない「上位候補の精度」まで評価できます。
最後に、学習した埋め込みから全ペアのスコアを計算し、隣接行列の再構成をヒートマップで可視化します。理論で述べたように、全ペアのスコアは行列積 $\sigma(\bm{Z}\bm{Z}^\top)$ で一括計算できます。
# --- 隣接行列の再構成スコアを可視化 ---
with torch.no_grad():
z = model(X, A_norm)
score_mat = torch.sigmoid(z @ z.t()).numpy() # σ(Z Z^T): 全ペアの確率
# 真の隣接行列(全エッジ)も作る
A_true = build_adj(N, edges).numpy()
fig, axes = plt.subplots(1, 2, figsize=(12, 5))
im0 = axes[0].imshow(A_true, cmap='Greys', aspect='auto')
axes[0].set_title('True adjacency matrix')
axes[0].set_xlabel('node'); axes[0].set_ylabel('node')
fig.colorbar(im0, ax=axes[0], fraction=0.046)
im1 = axes[1].imshow(score_mat, cmap='viridis', aspect='auto')
axes[1].set_title('Reconstructed link scores σ(Z Zᵀ)')
axes[1].set_xlabel('node'); axes[1].set_ylabel('node')
fig.colorbar(im1, ax=axes[1], fraction=0.046)
plt.tight_layout()
plt.savefig('link_prediction_heatmap.png', dpi=150, bbox_inches='tight')
plt.show()
左の真の隣接行列を見ると、ノードがコミュニティ順に並んでいるため、対角線上に3つのブロック（コミュニティ内エッジの密な領域）が現れます。右の再構成スコアでは、同じ3つのブロック領域が明るく（高スコアに）浮かび上がり、ブロック外（コミュニティ間）が暗く（低スコアに）なっているはずです。つまりモデルは、明示的にコミュニティを教えていないのに、エッジの予測を通じて自動的にブロック構造を学び取ったことになります。さらに、真の隣接行列では0だったブロック内のペアにも高いスコアが付いていれば、それこそが「まだ存在しないが存在しそうなエッジ」＝リンク予測が当てたい候補です。
左の真の隣接行列（白黒）には、ノード0〜39（コミュニティ1）・40〜79（コミュニティ2）・80〜119（コミュニティ3）に対応する3つの対角ブロックが見えます。右の再構成スコアマップでは、同じ位置に3つの明るい（確率が高い）ブロックが浮かび上がっており、コミュニティ内のノードが似た埋め込みを持つことを示しています。赤い点線がコミュニティ境界で、境界を越えた領域（コミュニティ間）のスコアは低く抑えられています。
実装を通して、エンコーダ・デコーダ・損失・評価・可視化がひとつのパイプラインとして動くことを確認できました。最後に全体を振り返ってまとめましょう。
まとめ
本記事では、グラフのリンク予測を二値分類問題として定式化し、理論から実装まで通して解説しました。
- 問題設定 — リンク予測は「観測エッジから未観測ペアのエッジ存在確率を推定する」問題で、エンコーダ（埋め込み生成）とデコーダ（スコア化）の2段構成で解く。
- 内積デコーダ — スコア $s(u,v) = \bm{z}_u^\top \bm{z}_v$ にシグモイドを通して確率 $\hat{p} = \sigma(s)$ を得る。「似たノードはつながりやすい」をベクトルの向きの一致で表現したもの。
- ロジスティック損失 — ベルヌーイ尤度の最尤推定（負の対数尤度）として交差エントロピー $\mathcal{L} = -\sum_E \log\sigma(s) – \sum_{E^-}\log\sigma(-s)$ を導出した。
- ネガティブサンプリング — 疎グラフのクラス不均衡と $O(N^2)$ の計算量を、正例と同数の負例を一様サンプリングすることで同時に解決する。
- データリーク回避 — 検証・テストエッジは GNN のメッセージパッシング（隣接構造）から必ず除外する。これがリンク予測特有の最重要の作法。
- 評価指標 — クラス不均衡なランキング問題なので、正解率ではなく ROC-AUC（順位付け能力）と Average Precision（上位の精度）で評価する。
- 実装 — GraphSAGE エンコーダ＋内積デコーダを PyTorch で組み、SBMグラフで高いAUC・APを達成し、隣接行列の再構成でコミュニティ構造の学習を可視化した。
リンク予測は「埋め込みを作って内積でスコア化する」という単純な枠組みながら、データ分割と負例サンプリングの作法を間違えると簡単に評価が壊れる、奥の深いタスクです。ここを正しく押さえれば、推薦・創薬・知識グラフ補完など多くの応用に直結します。
次のステップとして、以下の記事も参考にしてください。
- グラフニューラルネットワーク（GNN）とは — エンコーダの基礎となるメッセージパッシングの仕組み
- GraphSAGEの理論 — 本記事で使った帰納的GNNの近傍サンプリングと集約の詳細
- グラフラプラシアン — グラフの構造を行列で表す基礎、スペクトル的な見方
