f:id:kur0cky:20201023211747j:plain

こんにちは． DSOC 研究開発部の黒木裕鷹です．膝が痛いです．

やってしまいました．なまじ走れるようになってきたのが楽しく，まだ脚ができてないにも関わらず走りすぎてしまいました．．．調べてみたところ，膝の外側の靭帯（腸脛靭帯）と前十字靭帯を交互に痛めてしまったようです．ストレッチや筋トレに取り組み衝撃を吸収できる脚作りをすることはもちろんですが，靭帯をより強靭にするために研究を追ったりしているので，機会があればそのうち共有したいと思います．

さて，この連載では，自分の勉強・復習も兼ねて，ネットワークデータにまつわる（統計）解析を気の向くままに紹介しています．前回の記事では，外部の勉強会で取り上げたグラフ機械学習に関する論文を2本紹介しました．今回は，少し古典的なネットワークの分析に話題を戻していこうと思い，かの有名な PageRank と，そのあまり知られてない（と個人的に思っている）応用についていくつか紹介したいと思います．しばしお付き合いください

そもそも PageRank ってなに？
- いくつかの中心性指標のモチベーション
- PageRank
PageRank の応用
- Personalized PageRank
- Personalized PageRank の GNN への利用
おわりに
参考文献

そもそも PageRank ってなに？

さてまずは，PageRank とはそもそもなんであったかを復習したいと思います． PageRank とは，World Wide Web (WWW) を対象とした検索エンジンでの問題を解決するためにGoogleが開発した指標です (Brin and Page, 1998; Page et al., 1999)．ユーザがクエリを入力すると，キーワードとほぼ同じ単語を含む膨大な数のウェブページがすぐにみつかりますが，どのページがユーザの意図していた情報を持っているかを特定することは容易ではありませんでした．そこで Google は，WWW のハイパーリンク構造を利用してウェブページの重要性をスコアリングする，PageRank というアルゴリズムを考案したのです．

PageRank は，検索用のアルゴリズムとしてだけでなく，ネットワーク中心性指標としても非常に有名です．また，その他の有名な中心性とも密接に関わりがあります．そのため，任意のドメインのネットワークデータに適用され，分野を問わず盛んに利用される技術となっています．驚くべきことに，Brin and Page (1998) や Page et al. (1999) には "centrality"（中心性）というワードすら出てこないにも関わらずです．この連載はネットワーク分析に関するですので，元論文の文脈（グラフ上のランダムウォーク）ではなく，中心性指標の側から PageRank を導入してみようと思います．

いくつかの中心性指標のモチベーション

個々のノードがネットワークの中でどの程度中心的であるか，その数値化を測る指標を中心性指標といいます．ネットワークの中で中心的な役割を果たすノードを特定することは，SNS におけるインフルエンサーや交通網における要所の特定など，様々なタスクに応用することができます．最も単純な中心性指標としては，次数中心性 (degree centrality) が真っ先にあげられるでしょう．次数中心性はそのノード $i$ に接続するエッジの数として定義され，次式で表されます．ここで， $A$ は $n\times n$ の隣接行列です．

$\displaystyle k _ i ^ {(degree)} = \sum _ {j = 1} ^ {n} A _ {i, j}.$

ここで，中心性指標を考える元々のモチベーションに立ち返り，中心性として次数を用いることはどのようなことを意味するかを考えてみます．定義より，次数中心性はノードに張られるエッジをシンプルに数えあげている指標ですので，次数を中心性として用いることは，多くのエッジを持つノードを重要視する，ということに相当します．つまり，全てのエッジは同等であるとみなされ，隣接するノードの性質は考慮されません．

隣接ノードの影響も考慮する中心性で有名なのは，固有ベクトル中心性 (Bonacich, 1987) です．固有ベクトル中心性の立場は，重要なノードと接続するノードもまた重要であるとし，中心性のスコアは近傍に伝播する，というものです．このシンプルなアイデアを数式で表すと，次のような漸化式になります．ここで， $\lambda$ は正規化のための定数です．

$\displaystyle k _ i ^ {(eigen)} = \frac{1}{\lambda} \sum _ {j = 1} ^ {n} A _ {i, j} k _ j ^ {(eigen)}.$

また，全ノードをまとめて行列の形で表すと次式のようになります

$\displaystyle \begin{align} &\mathbf{k} ^ {(eigen)} = \frac{1}{\lambda} A \mathbf{k} ^ {(eigen)} \\\ \Leftrightarrow & \lambda \mathbf{k} ^ {(eigen)} = A \mathbf{k} ^ {(eigen)}. \end{align}$

これはちょうど固有値・固有ベクトルの式になっており， $\mathbf{k} ^ {(eigen)}$ は隣接行列 $A$ の第 1 固有ベクトルに収束することが知られています．ただ，固有ベクトル中心性にはひとつ問題点があります．それは，ネットワークが有向グラフで，入次数が 0 のノードが存在するとき，そのノードに伝播してくる中心性のスコアも 0 であるため，そのノードから伝播していくスコアもまた 0 になってしまうことです．

この問題を解消し，固有ベクトル中心性を有向グラフにも適用可能にしたものとして，たとえば Katz 中心性 (Katz, 1953) があります． Katz 中心性は，ノードの入次数に関わらない最低限のスコアを与え，次式を解くことで与えられます．ここで， $\alpha~(0 \lt \alpha \lt 1)$ は最低限のスコアと伝播するスコアのバランスを与えるパラメータです．

$\displaystyle \mathbf{k} ^ {(katz)} = \alpha A \mathbf{k} ^ {(katz)} + (1-\alpha)\mathbf{1}.$

PageRank

Katz 中心性にもまた，想定されてなかったであろう問題を挙げることができます．それは，高い Katz 中心性をもつノードからたくさんのノードにエッジ出ているとき，それらのノードには全て等しく大きなスコアの伝播があるということです．この現象は，現実の問題に取り組む上で適切でない場合があります．たとえば，Youtube のような巨大プラットフォームサイトの中心性は非常に大きくなることが想定されます．また，Youtube には膨大な外部サイトへのリンクがあります．このとき，非常に高いスコアが等しく全ての外部サイトに伝播していくことは適切といえるでしょうか．おそらく，Youtube がリンクする個々のページへの伝播は薄められるのが自然と考える人が多いでしょう．出次数 $k _ i ^ {(out~degree)}$ で割引くのがシンプルで良さそうですが，今度は出次数が 0 である場合に定義できなくなってしまいます．そこで， $\max(1, k _ i ^ {(out~degree)})$ で割り引いたものが，いわゆる PageRank と呼ばれるものになります．

$\displaystyle k _ i ^ {(PageRank)}= \alpha \sum _ {j=1} ^ {n} A _ {i, j} \frac{k _ j ^ {(PageRank)}}{\max(1, k _ j ^ {(out~degree)})} + (1-\alpha).$

複雑ネットワークの有名な教科書の一つである Newman(2018) では，ここまで出てきた 3 つの中心性を以下の2つの観点で整理しています．何かの分析に中心性指標を考えるときには，これらの整理を意識すると良いかもしれません．

定数項をもち，有向グラフにも適用できるかどうか
- ある：PageRank，Katz 中心性，
- ない：固有ベクトル中心性
出次数で割り引かれるかどうか
- 割り引かれる：PageRank
- 割り引かれない：Katz 中心性，固有ベクトル中心性

PageRank の応用

Personalized PageRank

ここまでで見てきたように，PageRank はネットワーク全体の情報（隣接行列）を使って算出される中心性指標です．そのため，Youtube や Amazon のような巨大なプラットフォームが，他のコンテンツに比べ常に高くスコアリングされることは想像に易いでしょう．個々の検索状況に合わせ，ユーザの興味のある部分を的確に反映するために， Page et al.(1999) では，全てのノードに与えていた最低限のスコアをいくつかのノードに限定する Personalized PageRankも提案しています．これは，初期の伝播の元となるソースノードを限定することに相当し，たとえばブックマークやホームページなどを指定することができるでしょう．全てのノードに考慮していた定数項 $\mathbf{1}$ を，特定のノードに限定することで達成されます．

Personalized PageRank の GNN への利用

盛り上がりを見せているグラフデータの深層学習 (GNN) に Personalized PageRank を利用しよう，という研究 Klicpera et al.(2018) があるので，紹介しようと思います．

GNN で基本となっている GCN フィルタは，近傍ノードの特徴量と自身の特徴量とを平均するものです．よって，より遠くにあるが関連しているノードの影響を考慮するためには，最短距離分の GCN フィルタを積み重ねなければなりませんし，数ステップ先の重要なノードをメインで考慮することは難しくなります．この問題は，誤差逆伝播を考える深層学習では特に，一部のノードにのみ正解ラベルが与えられる semi-supervised graph learning の文脈や，グラフがスパースな場合でより顕著になります． Klicpera et al.(2018) ではこの問題を解決するために，Personalized PageRank を利用した伝播アルゴリズムを提案しています． Personalized PageRank を利用することで，グラフ構造的に関連はありそうだが近傍にはないラベル付きノードを考慮したい，ということです．面白いですね．

おわりに

今回の記事では，ウェブページの重要度を推定するアルゴリズム，または主要な中心性指標のひとつとして知られる PageRank の基本的な導入からはじめ，そのいくつかの応用について紹介しました．もちろん，この記事で扱った内容にとどまらず，PageRankについてはかなりの研究がなされています．特に，より軽量な計算アルゴリズムや近似については膨大な蓄積があるようです．気になられた方は，Berkhin(2005) などを参照されると良いかもしれません．

次回の記事でも，また古典的な内容を扱いたいと思っております．最近はなぜか，（良い意味で）枯れた技術を復習し，地に足をつけたい欲が強いです．老いでしょうか．

年内の記事はこれで最後になるかもしれませんが，来年もまたお付き合いいただければ幸いです．ごきげんよう．

参考文献

Berkhin, P. (2005). A survey on PageRank computing. Internet mathematics, 2(1), 73-120.
Bonacich, P. (1987). Power and centrality: A family of measures. American journal of sociology, 92(5), 1170-1182.
Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1-7), 107-117.
Katz, L. (1953). A new status index derived from sociometric analysis. Psychometrika, 18(1), 39-43.
Klicpera, J., Bojchevski, A., & Günnemann, S. (2018). Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997.
Newman, M. (2018). Networks. Oxford university press.
Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab.

▼執筆者による連載記事はこちら buildersbox.corp-sansan.com