私はグラフ理論やグラフ構造、グラフニューラルネットワークといったものに、学生時代から取り憑かれてしまっている。アドベントカレンダーの記事を書くにあたって、得意領域の「検索」周りで何か書こうかと考えていたら、頭の中で「一年の終わりに際してグラフ構造を無視して年を越すつもりか！？」というグラフの囁きが聞こえてきたような気がしたので、「検索」と「グラフ」両者にゆかりのある「PageRankアルゴリズム」とその一般化である「グラフニューラルネットワーク」に関する内容で記事を書くことにした。
Googleの検索エンジンを支えたと言われるPageRankアルゴリズムと、グラフ機械学習の中核を担うGraph Neural Network（GNN）。一見すると異なる時代に生まれた別々の技術に見えるが、実は両者には深い数学的関係がある。本記事では、PageRankがGNNの特殊ケースであることを数式で示し、実際のWikipediaリンクデータを用いた実験を通じて、両者の違いを明らかにする。さらに、PageRankでは発見できないがGNNでは発見できる「隠れた重要ノード」の存在を示そうと思う。
前提知識
この章はあくまでPageRankとGNNを数式の側面から述べ、PageRankがGNNの特殊ケースであることを説明しているに過ぎないので、理解できずとも本記事のメインテーマの理解には影響しない。ただ、いきなり「GNNでもノードの重要度を捉えることができる」と言われても、「なんで？」という疑問が生じる方もいると考えたので、一応、簡単にではあるがその辺りの知識の整理はしておくべきだと思いこの章を用意した。興味のない方は読み飛ばしてもらっても全然構わない。
本記事のメインテーマから逸れるため、内容はかなりサラッと説明してしまっているため、深く理解したい方は「グラフ構造」や「GNN」について追加で調べてもらうことになってしまうのが心苦しい。一応、私の過去の記事でグラフやGNNについて解説しているものがあるので載せておく（ただネットを探せばもっとわかりやすい情報や体系だった記事はいくらでも見つかるかもしれない）。
- グラフについて：グラフニューラルネットワークって何？①グラフ概要
- GNNについて：グラフニューラルネットワークって何？②GNNと他の深層学習モデル：Transformer
PageRankとは何か
PageRankは1998年にLarry PageとSergey Brinによって提案された、Webページの重要度を計算するアルゴリズムである。基本的なアイデアは単純で、Webページとその間のリンクをグラフとして捉え、「多くの重要なページからリンクされているページは重要である」という仮説のもと再帰的な定義を行っているに過ぎない。数式で表すとノード(Webページ)iのPageRankスコアは以下のように定義される。
ここで、
- α：ダンピングファクター（通常0.85）
- N：全ノード数
- N_in(i)：ノードiにリンクを張っているノードの集合
- d_j^out：ノードjの出次数
この式は反復計算により収束し、最終的に各ノードの重要度スコアが得られる。覚えておきたい点は、PageRankはグラフの構造（リンク関係）のみを使用し、ノードの内容（特徴量）は一切考慮しないことである。
GNN（Graph Neural Network）とは何か
GNNは、グラフ構造を持つデータに対してニューラルネットワークを適用する手法である。代表的なモデルであるGCN（Graph Convolutional Network）の更新式は以下のようになる。
ここで、
- H^(l)：l層目のノード特徴量行列
- A~ = A + I：自己ループを加えた隣接行列
- D~：A~の次数行列
- W^(l)：学習可能な重み行列
- σ：活性化関数
この式の本質は「近所のノードから情報を平均してくる」ことに過ぎない。GNNの本質は「メッセージパッシング」である。各ノードは隣接ノードから情報（メッセージ）を受け取り、自身の表現を更新する。この処理を複数層重ねることで、より広い範囲のグラフ構造を捉えることができる。
PageRankはGNNの特殊な例である
PageRankとGNNの更新式を比較すると、興味深い類似性が見えてくる。
PageRankの行列形式：
ここで、
- p：各ノードのPageRankスコアを並べたベクトル
- A：隣接行列（ノード間のリンク関係）
- D：次数行列（対角成分に各ノードの次数）
- α：ダンピングファクター
- 1：全要素が1のベクトル
GCNの1層分（簡略化）：
ここで、
- h：現在のノード特徴量ベクトル
- h'：更新後のノード特徴量ベクトル
- A~：自己ループを加えた隣接行列（A + I）
- D~：A~の次数行列
- w：学習可能な重みベクトル
両者を見比べると、どちらも「隣接行列を用いて隣接ノードの情報を集約する」という同じ構造を持っていることがわかる。違いは以下の点にある。
| 観点 | PageRank | GNN（GCN） |
|---|---|---|
| 入力特徴量 | 使用しない | 使用する |
| 集約の重み | 固定（出次数で正規化） | 学習可能なパラメータ |
| 非線形変換 | なし | 活性化関数あり |
つまり、PageRankはノード特徴量を使わず、重みも固定されたGNNの特殊ケースと見なすことができるのだ。
GNNでも重要なノードを発見できる？
PageRankがGNNの特殊な例に過ぎないなら、その一般化であるGNNでも工夫すればPageRankのように、もしくはさらに深く、ノードの重要度を捉えられるのではないだろうか？GNNはPageRankに比べて学習可能なパラメーターを持ち、各ノードの特徴量まで計算に含めることができ、より柔軟であるはずだ。そこで私は以下の仮説を立ててみた。
GNNはPageRankでは発見できない「隠れた重要ノード」を発見できる可能性がある。
具体的には、以下のようなノードである。
- リンク数は少ないが、内容的に重要なノード
- 局所的なコミュニティ内で中心的な役割を果たすノード
この仮説を検証するため、実際のWikipediaデータを用いた実験を行った。
実験
使用データセット
本実験ではWiki-CSデータセットを使用する。これはWikipediaのコンピュータサイエンス関連記事から構築されたグラフデータである。
| 項目 | 値 |
|---|---|
| ノード数 | 11,701 |
| エッジ数 | 216,123 |
| 特徴量次元 | 300 |
| クラス数 | 10 |
各ノードはWikipedia記事に対応し、エッジは記事間のハイパーリンクを表す。ノード特徴量は記事のテキストから抽出された300次元のベクトルである。
実験設計
ここではGNNを「PageRankの一般化モデル」として扱い、PageRankの予測性能ではなく、“PageRankが見落とす構造を拾えるかどうか”を観察する。
- PageRank計算：NetworkXを用いて全ノードのPageRankスコアを計算（α=0.85）
- GNNモデル：3層のGCNを構築し、PageRankスコアを予測するタスクで学習
- 比較分析：両手法のノード重要度ランキングをテストデータで比較し、不一致点を分析し、「隠れた重要ノード」を見つける
GNNモデルの構造は以下の通りである。
class PageRankGNN(torch.nn.Module):
def __init__(self, in_channels, hidden_channels=64):
super().__init__()
self.conv1 = GCNConv(in_channels, hidden_channels)
self.conv2 = GCNConv(hidden_channels, hidden_channels)
self.conv3 = GCNConv(hidden_channels, 1)
def forward(self, x, edge_index):
x = F.relu(self.conv1(x, edge_index))
x = F.dropout(x, p=0.5, training=self.training)
x = F.relu(self.conv2(x, edge_index))
x = self.conv3(x, edge_index)
return x.squeeze()
実験結果：相関
| 指標 | 値 |
|---|---|
| 順位相関（Spearman） | 0.80 |
| Top-10 一致率 | 80% |
| Top-50 一致率 | 90% |
| Top-100 一致率 | 89% |
上記の結果を見る限り、GNNの計算結果はPageRankの計算結果と高い相関を示していると言えそうである。これはGNNがグラフ構造を適切に学習し、PageRank同様、グラフにおける各ノードの重要度を計算できていることを示していると言える。
実験結果：不一致ノードの分析
Top-100内のノードを分析すると全体的に以下の点が明らかとなった。
- 高次数ノード：ランク差が0付近に収束 → PageRankとGNNは概ね一致
- 低次数ノード：大きくばらつく → 評価が分かれやすい
さらに一歩進んで、Top-100内で一致しなかったノードを詳細に分析すると、興味深い傾向が見えてきた。PageRankが高評価、GNNが低評価のノードは、平均次数が約300と多くのリンクを持つにもかかわらず、GNNはこれらを重要と見なさなかった。これは、リンク数は多いが記事内容（特徴量）が周囲のノードと異質であることを示唆している。一方、GNNが高評価、PageRankが低評価のノードは、平均次数が約170と比較的低いが、GNNはこれらを重要と判定した。これらは「隠れた重要ノード」であると考えられ、記事内容が周囲と強く関連している可能性が高い。
GNNが発見した「隠れた重要ノード」
上記の分析から、特に次数が低いノードにおいて、GNNはPageRankとは異なる「重要性」を発見していることが明らかとなった。そうした例をいくつか分析している中で、最も興味深かった結果は、PageRankでは686位だったノードがGNNでは86位に「大逆転」した事例である。
Node 1358: PageRank順位 686位 → GNN順位 86位
このノードは次数68と比較的少ないリンクしか持たないが、GNNは高く評価した。この「大逆転」ノードを詳しく調べると、GNNが何を見ているのかが明らかになった。
Node 1358は「Computer security」カテゴリに属する記事である。このノードの特徴的な点は、隣接する68ノードのうち82.4%が同じComputer securityカテゴリに属していることである。これはTop100ノードの平均（53.1%）と比較して非常に高い。
さらに、記事内容の類似度を測るコサイン類似度を計算すると、隣接ノードとの平均類似度は0.886であった。全ノード間の平均類似度0.783と比較すると、このノードは周囲と内容的に強く結びついていることがわかる。
つまり、Node 1358はセキュリティ分野の密なコミュニティの中心に位置している。リンク数は少ないためPageRankでは目立たないが、GNNはノード特徴量を通じてこの「意味的な中心性」を捉えたと考えられる。
まとめ
本記事では、PageRankとGNNの数学的関係を明らかにし、実験を通じて両者の違いを検証した。主な知見は以下の通りである。
- PageRankはGNNの特殊ケースである：両者とも隣接行列を用いたメッセージパッシングが本質だが、GNNはノード特徴量と学習可能な重みを持つ点で一般化されている。
- GNNはPageRankと約80%の相関を示す：これはGNNがグラフ構造を適切に学習し、PageRank同様に各ノードの重要度を捉えられている証拠であると言える。
- 残りの20%に「隠れた重要ノード」が存在する：GNNはリンク数が少なくても内容的に重要なノードを発見できる。
- 両手法は補完的である。PageRankはグローバルなリンク構造を、GNNはローカルな構造とノード内容を重視する。
PageRankが「どこからリンクされているか」を重視するのに対し、GNNは「何について書かれているか」も考慮する。この違いが、20年以上の時を経て生まれた二つの技術の本質的な差異なのかもしれない。グラフ好きの私としては、どちらの手法もグラフ構造を扱っているという点で魅力的である。だが、一方で、いつの日かランキングアルゴリズムに、現在主流であるPageRankだけではなくGNNも用いられるようになったらそれはそれで興味深いと感じる（まあそんな日は来ないのかもしれないが）。
Discussion