PageRank with DGL message passing①|DGL(Deep Graph Library)を動かす #4

f:id:lib-arts:20200314234929p:plain

当シリーズでは、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"を読み進めていきます。

f:id:lib-arts:20200314235006p:plain

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アルゴリズムについて確認します。

f:id:lib-arts:20200314235527p:plain

上記のようにPageRankは解説されています。まずそれぞれのノードに一様に値を割り振り、更新式に基づいてPV(v)をアップデートしていくとされています。
更新式において、Nはグラフにおけるノードの数、D(v)はノードvから出ていく向きの次数(out-degree、有向グラフのため次数は入ってくる向きと出ていく向きがある)、PV(v)PV(u)はノードvuページランクの値(PageRank value)であるとされています。また、dダンピングファクター(damping factor)とされており、Wikipediaの記載によると「通常0.85に設定されるが、作為的にページランクを上げようとする者に対しては、より小さい値に設定される。(常に 0 ≤ d ≤ 1)」とされています。

ページランク - Wikipedia

PageRankの大枠のアルゴリズムについては確認できたので1節はここまでとします。


2. A naive implementationについて
2節では"A naive implementation"について確認していきます。

f:id:lib-arts:20200317190633p:plain
上記では、100個のノードからなるグラフをNetworkXで作成し、DGLGraphの形式に変換したとあります。

f:id:lib-arts:20200317191526p:plain

記載のコードの実行結果は上記になります。有向グラフがmatplotlibによって描画がされています。ここで、erdos_renyi_graphはランダムなグラフのことですが、第一引数はノードの数でここでは100、第二引数はエッジが存在する確率でここでは0.1、また結果の再現性を担保するために上記ではseedを固定しています(元のチュートリアルではseedを固定していませんでしたが、混乱を防ぐためにもseedを固定することにしました)。

f:id:lib-arts:20200317191827p:plain

次に、PageRankアルゴリズムに沿って初期値の設定を行っています。g.ndata['pv']にPageRankのスコア、g.ndata['deg']にノードから出ていく向きの次数の値を代入しています。

f:id:lib-arts:20200317193239p:plain
0〜4までのノードの持つ値を出力すると上記のようになります。g.ndata['pv']はどの要素も1を100で割った数が入力されるので全て0.01の値を持ち、g.ndata['deg']はエッジの生成確率が0.1のため、大体10前後の次数を持つようになっています。

f:id:lib-arts:20200317193719p:plain
以降では上記のような関数の定義が行われています。詳しくは使用時に確認するとしてここでは省略します。


3. まとめ
#4では"PageRank with DGL message passing"のページより、"A naive implementation"までを読み進めました。
#5では"Batching semantics for a large graph"以降について取り扱っていければと思います。