PageRank with DGL message passing①｜DGL(Deep Graph Library)を動かす #4
当シリーズでは、DGL(Deep Graph Library)について確認していきます。
Overview of DGL — DGL 0.4.2 documentation
#1ではDGLのドキュメントを元にインストールと動作事例の確認について、#2では#1の題材における重要ポイントの詳細の確認について、#3では"DGL Basics"について確認しました。
https://lib-arts.hatenablog.com/entry/dgl1
https://lib-arts.hatenablog.com/entry/dgl2
https://lib-arts.hatenablog.com/entry/dgl3
#4以降ではドキュメントより、"PageRank with DGL message passing"を読み進めていきます。
PageRank with DGL message passing — DGL 0.4.2 documentation
上記が冒頭部の記載ですが、「小さいグラフにおけるPageRankを用いたmessage passingAPIの異なるレベルについて学ぶことができ、DGLではmessage passingとfeature transformationsはユーザー定義(UDFs; user-defined functions)の関数である」とされています。詳しくは下記で確認していきます。
以下、目次になります。（チュートリアルの目次に準じています）
1. The PageRank algorithmについて
2. A naive implementationについて
3. まとめ
1. The PageRank algorithmについて
1節ではPageRankのアルゴリズムについて確認します。
上記のようにPageRankは解説されています。まずそれぞれのノードに一様に値を割り振り、更新式に基づいてをアップデートしていくとされています。
更新式において、はグラフにおけるノードの数、
はノード
から出ていく向きの次数（out-degree、有向グラフのため次数は入ってくる向きと出ていく向きがある）、
や
はノード
や
のページランクの値(PageRank value)であるとされています。また、
はダンピングファクター(damping factor)とされており、Wikipediaの記載によると「通常0.85に設定されるが、作為的にページランクを上げようとする者に対しては、より小さい値に設定される。（常に 0 ≤ d ≤ 1）」とされています。
PageRankの大枠のアルゴリズムについては確認できたので1節はここまでとします。
2. A naive implementationについて
2節では"A naive implementation"について確認していきます。
上記では、100個のノードからなるグラフをNetworkXで作成し、DGLGraphの形式に変換したとあります。
記載のコードの実行結果は上記になります。有向グラフがmatplotlibによって描画がされています。ここで、erdos_renyi_graphはランダムなグラフのことですが、第一引数はノードの数でここでは100、第二引数はエッジが存在する確率でここでは0.1、また結果の再現性を担保するために上記ではseedを固定しています（元のチュートリアルではseedを固定していませんでしたが、混乱を防ぐためにもseedを固定することにしました）。
次に、PageRankのアルゴリズムに沿って初期値の設定を行っています。g.ndata['pv']にPageRankのスコア、g.ndata['deg']にノードから出ていく向きの次数の値を代入しています。
0〜4までのノードの持つ値を出力すると上記のようになります。g.ndata['pv']はどの要素も1を100で割った数が入力されるので全て0.01の値を持ち、g.ndata['deg']はエッジの生成確率が0.1のため、大体10前後の次数を持つようになっています。
以降では上記のような関数の定義が行われています。詳しくは使用時に確認するとしてここでは省略します。
3. まとめ
#4では"PageRank with DGL message passing"のページより、"A naive implementation"までを読み進めました。
#5では"Batching semantics for a large graph"以降について取り扱っていければと思います。
