グラフニューラルネットワークのしくみ：メッセージパッシングから GCN・GAT まで
世の中には、「点と線」で表すと分かりやすいデータがたくさんあります。SNS の利用者とフォローの関係、論文と引用の関係、駅と路線、原子と化学結合などです。このような点（ノード）と線（エッジ）の集まりを グラフと呼びます。
画像はます目に並んだ画素、文章は一列に並んだ単語なので、畳み込みニューラルネットワーク や Transformer で扱えます。しかしグラフは、点ごとにつながっている数がばらばらで、決まった並び順もありません。このようなデータを学習するのが グラフニューラルネットワーク（GNN）です。
結論を先に書くと、GNN は次の考え方でできています。
- 隣の点から情報を集めて、自分の表し方を更新する（メッセージパッシング）。k 回くり返すと、k 歩先までの点の情報が届く
- つながっている点どうしは似ていることが多いので、隣の情報を混ぜると、少しの正解からでも残りの点をよく分類できる
- 集める回数を増やしすぎると、どの点も同じ表し方になってしまう（過平滑化）
- 隣どうしが似ていないグラフでは、隣と混ぜると逆に悪くなる。自分の情報と隣の情報を分けて扱う、隣ごとに重みを変える（GAT）などの工夫がある
説明の途中に出てくる計算例は、Python と NumPy で実際に動かした結果です。
環境
計算例を動かした環境です。
| 項目 | バージョン |
|---|---|
| Python | 3.13 |
| NumPy | 2.5 |
グラフを数で表す
グラフは、隣接行列という表で表せます。点が n 個なら n × n の表で、点 i と点 j がつながっていれば (i, j) のます目を 1、つながっていなければ 0 にします。SNS の友達関係のように向きのないつながりなら、表は対角線を挟んで対称になります。それぞれの点には、年齢や興味のような 特徴のベクトルも付いています。
グラフを使った機械学習の問題には、次のような種類があります。
| 問題 | 例 |
|---|---|
| 点の分類 | SNS の利用者のうち、どの人が業者のアカウントかを当てる。論文の分野を当てる |
| つながりの予測 | まだ友達になっていない 2 人が、友達になりそうかを当てる（推薦） |
| グラフ全体の分類・回帰 | 分子の形から、薬として効くか、毒性があるかを当てる |
メッセージパッシング：隣から情報を集める
自分と隣の平均を取る
GNN の基本の操作は、それぞれの点が、自分と隣の点の表し方を集めて、自分の表し方を更新することです。隣から「メッセージ」を受け取るように見えるので、メッセージパッシングと呼ばれます。
いちばん簡単な例として、5 人が一列につながったグラフで、0 番の人だけが値 1 の情報を持っているとします。各人が「自分と隣の人の値の平均」を自分の新しい値にする操作を、4 回くり返します。
import numpy as np
# 5 人が一列につながったグラフ：0 - 1 - 2 - 3 - 4
A = np.zeros((5, 5))
for i in range(4):
A[i, i + 1] = A[i + 1, i] = 1
A_hat = A + np.eye(5) # 自分自身ともつなぐ
S = A_hat / A_hat.sum(axis=1, keepdims=True) # 自分と隣の値の平均を取る行列
h = np.array([1.0, 0, 0, 0, 0]) # 0 番の人だけが情報を持っている
for k in range(1, 5):
h = S @ h
print(k, np.round(h, 3))実行結果:
1 [0.5 0.333 0. 0. 0. ]
2 [0.417 0.278 0.111 0. 0. ]
3 [0.347 0.269 0.13 0.037 0. ]
4 [0.308 0.248 0.145 0.056 0.019]1 回目では、0 番の隣の 1 番にだけ情報が届きます。2 回目で 2 番、3 回目で 3 番、4 回目で 4 番に届きました。k 回くり返すと、k 歩先までの点の情報が混ざるわけです。行列で書けば、「平均を取る」は隣接行列から作った行列を掛けるだけなので、何千・何万の点があっても、一度に計算できます。
GCN の 1 層
2017 年に発表された GCN（グラフ畳み込みネットワーク）の 1 層は、この平均の操作に、ふつうのニューラルネットワークの計算を組み合わせたものです。
次の層の表し方 = 活性化関数( 正規化した隣接行列 × 今の表し方 × 重み )正規化した隣接行列を掛ける部分が「隣から集める」、重みを掛ける部分が「集めた情報を変換する」部分です。重みはすべての点で共通なので、点の数がいくつでも、同じモデルを使えます。画像の畳み込みが「周りの画素から集める」操作を、決まった形のます目からグラフに広げたものと考えられます。
GCN では、隣の数が多い点の値が大きくなりすぎないように、自分と相手の隣の数（次数）の平方根で割って正規化します。
少しの正解から残りの点を分類する
3 つのグループからなる人間関係
GNN がよく使われるのは、一部の点にしか正解がないときです。3 つのグループからなる 300 人の人間関係を作ります。同じグループの人どうしは 8%、違うグループの人どうしは 1% の確率でつながります。各人には 16 個の特徴（プロフィールのようなもの）がありますが、グループの手がかりは雑音に埋もれていて、少ししか含まれていません。グループが分かっているのは、各グループ 5 人、合わせて 15 人だけです。
隣から集める操作を k 回くり返してできた表し方を使って、15 人の正解だけでロジスティック回帰を学習し、残りの 285 人のグループを当てます。重みの学習を 1 回にまとめた、この単純な GCN は SGC と呼ばれ、2019 年に、多くの問題でふつうの GCN と同じくらいの精度が出ることが示されました。
import numpy as np
# 3 つのグループからなる 300 人の人間関係。同じグループ内でつながりやすい
rng = np.random.default_rng(0)
n, n_class = 300, 3
label = np.repeat(np.arange(n_class), n // n_class)
def make_graph(p_in, p_out):
p = np.where(label[:, None] == label[None], p_in, p_out)
A = np.triu(rng.random((n, n)) < p, 1)
return (A | A.T).astype(float)
# 各人の特徴（プロフィールなど）は、グループの手がかりを少しだけ含む
centers = rng.standard_normal((n_class, 16))
X = 0.4 * centers[label] + rng.standard_normal((n, 16))
# 正解が分かっているのは各グループ 5 人だけ
train = np.concatenate([rng.choice(np.flatnonzero(label == c), 5, replace=False) for c in range(n_class)])
test = np.setdiff1d(np.arange(n), train)
def propagate(A, X, k):
# 自分自身も含めた隣の人の特徴の平均を取る（GCN と同じく次数で正規化）を k 回くり返す
A_hat = A + np.eye(n)
d = A_hat.sum(axis=1)
S = A_hat / np.sqrt(d[:, None] * d[None])
H = X
for _ in range(k):
H = S @ H
return H
def train_eval(H):
# 15 人の正解だけでロジスティック回帰（ソフトマックス回帰）を学習し、残りを分類する
H = (H - H.mean(axis=0)) / (H.std(axis=0) + 1e-9)
W = np.zeros((H.shape[1], n_class))
Y = np.eye(n_class)[label[train]]
for _ in range(500):
Z = H[train] @ W
P = np.exp(Z - Z.max(axis=1, keepdims=True)); P /= P.sum(axis=1, keepdims=True)
W -= 0.1 * (H[train].T @ (P - Y) / len(train) + 0.01 * W)
return round(float(((H[test] @ W).argmax(axis=1) == label[test]).mean()), 3)
def mean_cos(H):
U = H / np.linalg.norm(H, axis=1, keepdims=True)
return round(float((U @ U.T).mean()), 3)
A = make_graph(0.08, 0.01)
print(int(A.sum() / 2), round(float(A.sum(axis=1).mean()), 1), round(float((label[np.nonzero(A)[0]] == label[np.nonzero(A)[1]]).mean()), 2))
for k in [0, 1, 2, 4, 16, 64]:
H = propagate(A, X, k)
print(k, train_eval(H), mean_cos(H))実行結果:
1501 10.0 0.79
0 0.596 0.024
1 0.93 0.165
2 0.989 0.371
4 0.989 0.685
16 0.972 0.999
64 0.316 1.01 行目は、つながりの数（1,501 本）、1 人あたりの平均のつながりの数（10 人）、つながっている 2 人が同じグループである割合（79%）です。2 行目からは、左から、集める回数 k、残り 285 人の正解率、全員の表し方の向きのそろい具合（コサイン類似度の平均）です。
- k=0（グラフを使わず、自分の特徴だけ）では、正解率は 59.6% です。特徴に含まれる手がかりが少なく、15 人の正解だけでは十分に学習できません
- k=1 で 93.0%、k=2 で 98.9% と大きく上がりました。同じグループの人どうしがつながりやすいので、隣の特徴を混ぜると、雑音が打ち消し合い、グループの手がかりが強まるのです
このように、正解の分かっている点が少なくても、グラフのつながりを使って残りの点を分類する問題を 半教師あり学習と呼びます。2017 年の GCN の論文も、論文の引用関係のグラフで、少しの論文の分野から残りの論文の分野を当てる問題で成果を示しました。
集めすぎると、どの点も同じになる
一方、集める回数を増やしすぎると、正解率は下がります。k=16 で 97.2%、k=64 では 31.6% と、3 択の当てずっぽう（33%）と変わらなくなりました。右の列のとおり、k=16 で全員の表し方の向きのそろい具合が 0.999、k=64 で 1.0 になっています。平均を取る操作をくり返すうちに、情報がグラフ全体に広がりきって、どの点も同じ表し方になってしまったのです。これを 過平滑化と呼びます。
そのため、GNN の層の数は、ふつう 2〜3 層と、画像や文章のモデルに比べてずっと少なくします。深くしたいときは、ニューラルネットワークの学習のしくみ で出てくるような、前の層の表し方をそのまま足し戻す（残差接続）などの工夫をします。
隣どうしが似ていないグラフ
混ぜると逆に悪くなる
GNN がうまくいくのは、「つながっている点どうしは似ている」（同類性）という前提が成り立つときです。しかし、世の中には、違うものどうしがつながりやすいグラフもあります。売り手と買い手の取引、異なる種類の原子の結合、業者のアカウントが一般の利用者ばかりをフォローする場合などです。
上の続きで、同じグループどうしは 0.5%、違うグループどうしは 4% の確率でつながるグラフを作り、同じことを試します。
# 隣の人が別のグループであることが多いグラフ（異なる者どうしがつながる）
A2 = make_graph(0.005, 0.04)
print(round(float((label[np.nonzero(A2)[0]] == label[np.nonzero(A2)[1]]).mean()), 2))
for k in [0, 1, 2]:
print(k, train_eval(propagate(A2, X, k)))
# 自分の特徴と、隣の平均を別々に並べて使う（GraphSAGE のような分け方）
print("自分と隣を分ける", train_eval(np.c_[X, (A2 @ X) / A2.sum(axis=1, keepdims=True).clip(1)]))実行結果:
0.06
0 0.596
1 0.491
2 0.481自分と隣を分ける 0.639つながっている 2 人が同じグループである割合は 6% だけです。このグラフで自分と隣の平均を取ると、正解率は 59.6% から 49.1% に下がりました。自分の特徴に、違うグループの人の特徴を混ぜてしまうので、手がかりが薄まるのです。
最後の行は、自分の特徴と隣の特徴の平均を 混ぜずに横に並べて使った結果で、63.9% と、自分の特徴だけの 59.6% を上回りました。混ぜずに並べれば、モデルは「隣の人とは違うグループだろう」という関係も、重みとして学習できます。2017 年の GraphSAGE は、このように自分の表し方と隣から集めた表し方を分けて扱う方法の 1 つです。
GAT：隣ごとに重みを変える
GCN は、隣の点をすべて（次数で決まる重みで）平等に扱います。2018 年に発表された GAT（グラフアテンションネットワーク）は、アテンション を使って、隣の点ごとに、どれだけ情報を受け取るかの重みを学習します。自分と隣の表し方から重みのスコアを計算し、隣の点についてソフトマックスを取ります。関係の深い友達の情報は多く、たまたまつながっただけの相手の情報は少なく受け取れるわけです。
見方を変えると、Transformer のアテンションは「文中のすべての単語がつながったグラフ」の上の GAT のようなものです。GAT は、つながっている点の間だけでアテンションを計算します。
グラフ全体を分類する
分子の毒性の予測のように、グラフ全体について答える問題では、メッセージパッシングで各点の表し方を作ったあと、全部の点の表し方の平均や合計を取って（読み出し）、グラフ全体のベクトルにします。原子が点、結合が線の分子のグラフでは、点の並び順に意味がないので、並び順によらない平均や合計がちょうどよいのです。2017 年には、このような方法をまとめた MPNN（メッセージパッシングニューラルネットワーク）が、分子の性質の予測で成果を上げました。
GNN は、ほかにも次のようなところで使われています。
- 推薦：利用者と商品をつないだグラフで、買いそうな商品を当てる（2018 年の Pinterest の PinSage など。推薦システムのしくみ も参考になります）
- 交通：道路のつながりと渋滞の伝わり方から、到着時間を予測する
- 天気予報：地球の表面を細かい点のつながりで表し、気象の変化を予測する（2023 年の GraphCast）
グラフニューラルネットワークの手法の流れ
この記事で紹介した手法を年代順に並べます。
| 年 | 手法・出来事 | ポイント |
|---|---|---|
| 1998 | PageRank | リンクのつながりをくり返したどって、ページの重要度を計算する |
| 2009 | グラフニューラルネットワーク（スカルセリら） | 隣の点との情報のやり取りを、安定するまでくり返すモデル |
| 2014 | DeepWalk | グラフ上をランダムに歩いた道を文章とみなし、word2vec で点のベクトルを作る |
| 2017 | GCN・GraphSAGE・MPNN | 隣から集める操作を層にする。自分と隣を分ける。メッセージパッシングとしてまとめる |
| 2018 | GAT・過平滑化の分析・PinSage | 隣ごとの重みをアテンションで学ぶ。層を重ねると表し方がそろうことを示す。大規模な推薦に使う |
| 2019 | SGC | 非線形をなくした単純な GCN でも、多くの問題で同じくらいの精度が出る |
| 2020 | 異なる者どうしがつながるグラフの研究 | 同類性の低いグラフで GNN が苦手になる理由と対策 |
| 2023 | GraphCast | GNN による全球の天気予報 |
まとめ
- グラフは隣接行列と点の特徴で表せる。点の数やつながりの数がばらばらなので、専用のモデルが必要になる
- GNN は、隣の点から情報を集めて自分の表し方を更新する（メッセージパッシング）。k 回くり返すと k 歩先までの情報が届く
- つながっている点どうしが似ているグラフでは、隣の情報を混ぜると、少しの正解からでも残りの点をよく分類できる
- 集める回数を増やしすぎると、どの点も同じ表し方になる（過平滑化）ので、層は 2〜3 層と少なくする
- 隣どうしが似ていないグラフでは、混ぜると逆に悪くなる。自分と隣を分けて扱う、隣ごとに重みを変える（GAT）などの工夫がある
- グラフ全体の問題では、点の表し方の平均や合計でグラフ全体のベクトルを作る
参考
- S. Brin and L. Page, "The Anatomy of a Large-Scale Hypertextual Web Search Engine", WWW 1998
- F. Scarselli et al., "The Graph Neural Network Model", IEEE Transactions on Neural Networks 2009
- B. Perozzi, R. Al-Rfou and S. Skiena, "DeepWalk: Online Learning of Social Representations", KDD 2014（arXiv:1403.6652）
- T. N. Kipf and M. Welling, "Semi-Supervised Classification with Graph Convolutional Networks", ICLR 2017（arXiv:1609.02907）
- W. L. Hamilton, R. Ying and J. Leskovec, "Inductive Representation Learning on Large Graphs", NeurIPS 2017（arXiv:1706.02216）
- J. Gilmer et al., "Neural Message Passing for Quantum Chemistry", ICML 2017（arXiv:1704.01212）
- P. Veličković et al., "Graph Attention Networks", ICLR 2018（arXiv:1710.10903）
- Q. Li, Z. Han and X.-M. Wu, "Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning", AAAI 2018（arXiv:1801.07606）
- R. Ying et al., "Graph Convolutional Neural Networks for Web-Scale Recommender Systems", KDD 2018（arXiv:1806.01973）
- F. Wu et al., "Simplifying Graph Convolutional Networks", ICML 2019（arXiv:1902.07153）
- J. Zhu et al., "Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs", NeurIPS 2020（arXiv:2006.11468）
- R. Lam et al., "Learning skillful medium-range global weather forecasting", Science 2023（arXiv:2212.12794）