PyTorch : DGL Tutorials : Basics : DGL メッセージパッシングによるページランク (翻訳/解説)
翻訳 : (株)クラスキャット セールスインフォメーション
作成日時 : 06/04/2019
* 本ページは、DGL のドキュメント “PageRank with DGL Message Passing” を翻訳した上で適宜、補足説明したものです：
* サンプルコードの動作確認はしておりますが、必要な場合には適宜、追加改変しています。
* ご自由にリンクを張って頂いてかまいませんが、sales-info@classcat.com までご一報いただけると嬉しいです。
DGL Tutorials : Basics : DGL メッセージパッシングによるページランク
このセクションでは小さいグラフ上のページランクでメッセージパッシング API の異なるレベルの使用方法を示します。DGL では、メッセージパッシングと特徴変形は総てユーザ定義関数 (UDF) です。
このチュートリアルの目標は: DGL メッセージパッシング・インターフェイスを使用してページランクを実装することです。
ページランク・アルゴリズム
ページランクの各反復 (= iteration) で、総てのノード (web ページ) は最初にそのページランク値をその下流ノードに一様に散布します。各ノードの新しいページランク値はその近傍から受け取ったページランク値を収集することにより計算され、それからそれはダンピング因子で調整されます。
\[
PV(u) = \frac{1-d}{N} + d \times \sum_{v \in \mathcal{N}(u)}
\frac{PV(v)}{D(v)}
\]
ここで $N$ はグラフのノードの数です ; $D(v)$ はノード $v$ の出次数です ; そして $\mathcal{N}(u)$ は近傍ノードです。
naive 実装
最初に 100 ノードを持つグラフを NetworkX で作成してそれを DGLGraph に変換しましょう :
import networkx as nx import matplotlib.pyplot as plt import torch import dgl N = 100 # number of nodes DAMP = 0.85 # damping factor K = 10 # number of iterations g = nx.nx.erdos_renyi_graph(N, 0.1) g = dgl.DGLGraph(g) nx.draw(g.to_networkx(), node_size=50, node_color=[[.5, .5, .5,]]) plt.show()
アルゴリズムに従えば、ページランクは典型的な scatter-gather パターンの 2 つの段階から成ります。最初に各ノードのページランク値を $\frac{1}{N}$ に初期化して各ノードの出次数をノード特徴としてストアします :
g.ndata['pv'] = torch.ones(N) / N g.ndata['deg'] = g.out_degrees(g.nodes()).float()
それからメッセージ関数を定義します、これは総てのノードのページランク値をその出次数で除算して結果をメッセージとしてその近傍に渡します :
def pagerank_message_func(edges):
return {'pv' : edges.src['pv'] / edges.src['deg']}
DGL では、メッセージ関数は エッジ UDF として表わされます。エッジ UDF は単一の引数 edges を取ります。それは送信元ノード特徴、送信先ノード特徴とエッジ特徴のそれぞれにアクセスするために 3 つのメンバー src, dst と data を持ちます。ここで、この関数は送信元特徴だけからのメッセージを計算します。
次に、reduce 関数を定義します、これはその mailbox からのメッセージを除去して収集して、そしてその新しいページランク値を計算します :
def pagerank_reduce_func(nodes):
msgs = torch.sum(nodes.mailbox['pv'], dim=1)
pv = (1 - DAMP) / N + DAMP * msgs
return {'pv' : pv}
reduce 関数は ノード UDF です。ノード UDF は単一の引数 nodes を持ち、これは 2 つのメンバー data と mailbox を持ちます。data はノード特徴を含む一方で mailbox は総ての incoming メッセージ特徴を含みます、これは 2 番目の次元に沿ってスタックされます (従って dim=1 引数)。
message UDF はエッジのバッチ上で動作します、その一方で reduce UDF はエッジのバッチ上で動作しますがノードのバッチを出力します。それらの関係は次のようなものです :
message 関数と reduce 関数を登録します、これらは後で DGL により呼び出されます。
g.register_message_func(pagerank_message_func) g.register_reduce_func(pagerank_reduce_func)
そしてアルゴリズムは非常に率直です。ここに一つの PageRank iteration のためのコードがあります :
def pagerank_naive(g):
# Phase #1: send out messages along all edges.
for u, v in zip(*g.edges()):
g.send((u, v))
# Phase #2: receive messages to compute new PageRank values.
for v in g.nodes():
g.recv(v)
バッチ処理セマンティクスによる改良
上のコードは巨大なグラフにスケールしません、何故ならばそれは総てのノードに渡り iterate するからです。DGL はユーザにノードやエッジのバッチ上で計算させることでこれを解決します。例えば、次のコードは複数ノードとエッジ上で message と reduce 関数を一度に起動します。
def pagerank_batch(g):
g.send(g.edges())
g.recv(g.nodes())
私達は依然として同じ reduce 関数 pagerank_reduce_func を使用していることに注意してください、そこでは nodes.mailbox[‘pv’] は単一の tensor で、incoming メッセージを 2 番目の次元に沿ってスタックします。
自然に、総てのノードで並列に reduce を遂行することさえも可能であるか疑問に思うでしょう、何故ならば各ノードは異なる数の incoming メッセージを持つかもしれず、そして異なる長さの tensor を実際には一緒に「スタック」できないからです。一般に、DGL は incoming メッセージの数によりノードをグループ分けして各グループに対して reduce 関数を呼び出すことにより問題を解決します。
高位 API による更なる改良
基本的な send と recv を様々な方法で結合する多くのルーチンを提供します。それらは レベル-2 API と呼称されます。例えば、ページランク・サンプルは次のように更に単純化されます :
def pagerank_level2(g):
g.update_all()
update_all の他にも、このレベル-2 カテゴリーで pull, push と send_and_recv もまた持ちます。より詳細については API リファレンス を参照してください。
DGL 組み込み関数でより多くの改良
message と reduce 関数の幾つかは非常に共通に使用されますので、DGL はまた組み込み関数も提供します。例えば、2 つの組み込み関数がページランク・サンプルで使用できます。
- dgl.function.copy_src(src, out) はエッジ UDF で送信元ノード特徴データを使用して出力を計算します。ユーザは送信元特徴データの名前 (src) と出力名 (out) を指定する必要があります。
- dgl.function.sum(msg, out) はノード UDF でノードの mailbox のメッセージを合計します。ユーザはメッセージ名 (msg) と出力名 (out) を指定する必要があります。
例えば、ページランク・サンプルは次のように書き換えることができます :
import dgl.function as fn
def pagerank_builtin(g):
g.ndata['pv'] = g.ndata['pv'] / g.ndata['deg']
g.update_all(message_func=fn.copy_src(src='pv', out='m'),
reduce_func=fn.sum(msg='m',out='m_sum'))
g.ndata['pv'] = (1 - DAMP) / N + DAMP * g.ndata['m_sum']
ここでは、update_all にその引数として UDF を提供します。これは前に登録された UDF を override します。
よりきれいなコードに加えて、組み込み関数の使用はまた DGL に演算を一緒に融合するための機会も与え、より高速な実行という結果になります。例えば、DGL は copy_src message 関数と sum reduce 関数を一つのスパース行列ベクトル (spMV) 乗算に融合します。
次のセクションは spMV がページランクの scatter-gather 段階を何故高速化できるのかを説明します。DGL の組み込み関数についてのより詳細については、API リファレンス を読んでください。
貴方はまた違いを感じるためにコードをダウンロードして実行することもできます。
for k in range(K):
# Uncomment the corresponding line to select different version.
# pagerank_naive(g)
# pagerank_batch(g)
# pagerank_level2(g)
pagerank_builtin(g)
print(g.ndata['pv'])
tensor([0.0114, 0.0085, 0.0112, 0.0069, 0.0050, 0.0119, 0.0104, 0.0085, 0.0104,
0.0122, 0.0085, 0.0085, 0.0111, 0.0071, 0.0121, 0.0130, 0.0060, 0.0087,
0.0068, 0.0095, 0.0104, 0.0129, 0.0098, 0.0077, 0.0112, 0.0111, 0.0129,
0.0058, 0.0094, 0.0156, 0.0103, 0.0105, 0.0109, 0.0085, 0.0077, 0.0089,
0.0112, 0.0086, 0.0094, 0.0092, 0.0051, 0.0104, 0.0093, 0.0107, 0.0140,
0.0095, 0.0132, 0.0111, 0.0060, 0.0142, 0.0104, 0.0050, 0.0110, 0.0094,
0.0122, 0.0093, 0.0070, 0.0165, 0.0068, 0.0113, 0.0075, 0.0101, 0.0119,
0.0130, 0.0106, 0.0059, 0.0085, 0.0101, 0.0094, 0.0111, 0.0103, 0.0114,
0.0113, 0.0128, 0.0093, 0.0110, 0.0042, 0.0086, 0.0095, 0.0105, 0.0110,
0.0086, 0.0067, 0.0105, 0.0137, 0.0103, 0.0078, 0.0099, 0.0093, 0.0102,
0.0147, 0.0093, 0.0067, 0.0147, 0.0113, 0.0121, 0.0094, 0.0106, 0.0121,
0.0118])
ページランクのために spMV を使用する
組み込み関数の使用は DGL に UDF のセマンティクスを理解することを可能にしてそのため貴方のためにより効率的な実装を可能にします。例えば、ページランクの場合、それを高速化するための一つの一般的なトリックはその線形代数形式を使用することです。
\[
\mathbf{R}^{k} = \frac{1-d}{N} \mathbf{1} + d \mathbf{A}*\mathbf{R}^{k-1}
\]
ここで、$\mathbf{R}^k$ は iteration $k$ における総てのノードのページランク値のベクトルです ; $\mathbf{A}$ はグラフのスパース隣接行列です。この等式を計算することは非常に効率的です、何故ならばスパース行列ベクトル乗算 (spMV) のための効率的な GPU カーネルがあるからです。DGL は組み込み関数を通してそのような最適化が利用可能であるかを検出します。もし組み込みの特定の組み合わせが spMV カーネル にマップできるのであれば (e.g. ページランク・サンプル)、DGL は自動的にそれを使用するでしょう。結果として、可能なときはいつでも組み込み関数を使用することを推奨します。
以上