こんにちは。データサイエンスチームの t2sy です。
2019年11月27日に韓国ソウル特別市江南区で開催される NHN FORWARD に参加する予定です。今年の NHN FORWARD の招待講演は Sang-Wook Kim 氏による 「Recommendation Systems: Concepts, Techniques, and Research Results」です。

この記事では、Sang-Wook Kim 氏らのグループによる「RealGraph: A Graph Engine Leveraging the Power-Law Distribution of Real-World Graphs」という実世界の大規模グラフの性質に応じて、グラフを効率的に処理するための技法を提案した論文を簡単に紹介します。本論文は WWW’19 で採択されています。

大規模グラフの性質

グラフはオブジェクト間の関係性を表現するために広く使われているデータ構造です。グラフはノードの集合 とそれを結ぶエッジの集合 で構成され と表記されることが多くあります。
近年、Web やソーシャルネットワークなどの実世界のグラフは急速にサイズが拡大しています。このような大規模グラフを効率的に処理したいという需要から Giraph, TurboGraph, GridGraph など様々なグラフエンジンが開発されてきました。
プログラマにとって馴染みのあるグラフアルゴリズムと言えば、グラフ上の2点間の最短パスを求めるダイクストラのアルゴリズムが挙げられるかもしれません。上記のグラフエンジンは、プログラマがグラフアルゴリズムを実行するためのシンプルな API を提供しています。

実世界の多くの大規模グラフはべき乗分布に従います。べき乗分布に従う大規模グラフでは、ハブノードと呼ばれる非常に少ないノードが非常に高い次数を有しており、その他の多くのノードが低い次数を有しているという特徴があります。
以下は Yahoo データセットのノードの次数とノードの数の関係性を表した図 (x軸、y軸ともに対数スケール) で、概ねべき乗分布に従っていることがわかります。

大規模グラフ処理の課題

グラフエンジンは、特定のグラフアルゴリズムのみを実行対象とはせず、様々なグラフアルゴリズムを処理することを目的とした汎用のソフトウェアフレームワークです。

グラフエンジンは大きく以下の2ステップでグラフアルゴリズムを反復的に実行します。

1. インジケータをスキャンし処理するノードを識別
2. 識別したノードとそのエッジに対する処理の並列実行

本論文で提案されている RealGraph ではノードの識別を main thread、処理の実行を worker threads が担っています。

べき乗分布に従う大規模グラフに対して、既存のグラフエンジンでグラフアルゴリズムを実行すると以下の2つの現象が起きることを論文内で指摘しています。

• 前半の反復で多くのノードは処理され後半の反復では少数のノードのみが処理される
• ある反復ではハブノードと非ハブノードが一緒に処理される

上記2つの現象は、既存のグラフエンジンで性能低下を引き起こす可能性があります。
既存のグラフエンジンでみられる単一のフラットなインジケータ (Single Flat Indicator) による線形スキャンの場合、前半の反復で多くのノードは処理されるため、後半はインジケータが疎になり非効率となります。また、ノードベースのワークロード割当て (Node-based Workload Allocation) をグラフエンジンが採用している場合、ハブノードと非ハブノードを処理するスレッド間で処理完了までの時間に差が生まれ、大きな待機時間が発生してしまう問題があります。

RealGraph

本論文では、前述した課題を解決するためのシングルマシンベースのグラフエンジン RealGraph を提案しています。RealGraph の全体のアーキテクチャは以下です。

RealGraph は大きく以下の4つのレイヤで構成されています。オブジェクトはエッジを有するノードを指します。

• storage management layer: ストレージ空間を管理。グラフデータはブロック単位に分割され格納される。
• buffer management layer: メインメモリ空間を管理。メモリ上でブロックを保持する buffer と buffer への高速アクセスを補助する buffer index で構成され、これらは常にメモリ上にロードされる。
• object management layer: グラフデータのブロックとオブジェクトの位置を管理。object index はストレージ内のオブジェクトとブロックを示す役割を持ち、常にメモリ上にロードされる。
• thread management layer: グラフアルゴリズムを実行する worker threads とそれを管理する main thread で構成。また、attribute data はノードやエッジの中間的な計算結果を保持する。

本論文では、べき乗分布に従う大規模グラフの性質に応じて、グラフを効率的に処理するための技法が提案されています。

Hierarchical Indicator

べき乗分布に従う大規模グラフに対して、既存のグラフエンジンでグラフアルゴリズムを実行すると、前半の反復で多くのノードは処理され後半の反復では少数のノードのみが処理されるという特徴がありました。この場合、疎なフラットインジケータの線形スキャンは非効率となります。

本論文では、効率的なスキャンのために Hierarchical Indicator を提案しています。
Hierarchical Indicator は複数のビットベクトルで構成され、上位レベルのビットベクトルが下位レベルのビットベクトルのスキャン範囲を決定します。Hierarchical Indicator には範囲長 (range length) と高さの2つのパラメータがあり、範囲長が決まると高さも決定される関係にあります。
範囲長が 210 bits の場合、フラットインジケータよりも 0.1％ 多くメモリを消費する代わりに、スキャン時間を 1/100 に削減できるようです。

以下の図は、範囲長を 3 とした場合の Hierarchical Indicator の例です。まず、最上位レベルのビットベクトルを左からスキャンし 2 番目のビットの 1 を識別します。次に、中間レベルのビットベクトルの 4 から 6 番目のビットをスキャンし、6 番目のビットの 1 を識別します。最後に、最下位レベルのビットベクトルの 16 から 18 番目のビットをスキャンし、17 番目のビットの 1 を処理対象のノードとして識別します。従って、最下位レベルのビットベクトルの全体の長さ 27 bits でなく 9 bits のスキャンで済みます。

Block-based Workload Allocation

べき乗分布の性質から、グラフアルゴリズムの実行時にハブノードと非ハブノードが一緒に処理される可能性があります。グラフエンジンがノードベースのワークロード割当てを採用している場合、大きな処理の遅延を招き、グラフエンジン全体の処理性能の低下に繋がります。
本論文では、ブロックベースのワークロード割当て (Block-based Workload Allocation) を提案しています。これにより worker threads には概ね均等なサイズのワークロードが与えられ、スレッド間での処理時間の不均衡さを軽減することができます。

以下は、各反復でのスレッドに対するワークロードの標準偏差を測定した結果で、ノードベースと比較しブロックベースは全体的に標準偏差が抑えられていることがわかります。

Yahoo データセットで PageRank を実行した実験した結果では適切なブロックサイズは 1024KiB であったと報告しています。

Efficient Data Layout

ストレージ内のオブジェクトを適切に配置することで、グラフエンジンの CPU と I/O 性能を改善することができます。 RealGraph では、著者のグループの以前の研究「Data Locality in Graph Engines: Implications and Preliminary Experimental Results」のコンセプトに倣い、一緒にアクセスされるデータが隣接するストレージ空間に配置されるようにデータレイアウトを工夫しています。

実験と評価

実験で用いられたデータセットは以下の 6 個です。

• Wiki: Wikipedia (English) のハイパーリンクのデータセット
• UK: uk ドメインを持つ Web ページの関係を含むデータセット
• Twitter: Twitter で収集されたツイートの関係を含むデータセット
• SK: sk ドメインを持つ Web ページの関係を含むデータセット
• Friend: オンラインゲームの SNS である Friendster のユーザ間のリンクのデータセット
• Yahoo: Yahoo! AltaVista のハイパーリンクのデータセット

各データセットのグラフの特徴は以下です。#Nodes はノードの数、#Edges はエッジの数、Size はデータセットのサイズです。

提案手法の評価

本論文で提案された Hierarchical Indicator や Block-based Workload Allocation, Efficient Data Layout の効果を実験した結果が以下です。Yahoo データセットを用いて、breadth first search (BFS) と PageRank の2つのグラフアルゴリズムで実験しています。
x 軸の Null は提案手法を用いず従来のフラットインジケータでノードベースのワークロード割当てを用いた場合、H は Hierarchical Indicator を適用した場合、B は Block-based Workload Allocation を適用した場合、D は efficient data layout を適用した場合、Ω は提案された手法を全て適用した場合を表しています。また、HB、HD、BD は H、B、D の組み合わせです。

BFS では Ω は Null と比較し、約1/60 に実行時間が短縮されています。特に HD の組み合わせが効果が大きい一方で、 BD の組み合わせは効果が大きくはないようです。また、PageRank では Ω は Null と比較し、約1/8.4に実行時間が短縮されています。

性能比較

先行研究である GraphChi、GridGraph、TurboGraph の3つのシングルマシンベースのグラフエンジンに対して、BFS、weakly connected component (WCC)、PageRank の3つのグラフアルゴリズムを実行し、実行時間の比較を行なった結果が以下です。

RealGraph は実験で用いられた全てのデータセット、グラフアルゴリズムに対して最も優れた性能であることが示されています。また、論文では分散システムベースのグラフエンジンとの性能比較も行われ、競争力のある結果が示されています。

おわりに

この記事では、実世界の大規模グラフの性質に応じて、グラフを効率的に処理するための技法を提案した論文「RealGraph: A Graph Engine Leveraging the Power-Law Distribution of Real-World Graphs」を紹介しました。
2019年11月27日に参加予定の NHN FORWARD の招待講演では RealGraph を情報推薦に応用した講演が予定されています。次回は、招待講演を含めた NHN FORWARD の参加レポートを紹介する予定です。

参考文献

[1] 『グラフ・ネットワークアルゴリズムの基礎: 数理とCプログラム』
[2] Martin Erwig. 1992. Graph algorithms= iteration+ data structures?. In International workshop on graph-theoretic concepts in computer science. 277–292.
[3] Wook-Shin, Sangyeon Lee, Kyungyeol Park, Jeong-Hoon Lee, Min-Soo Kim, Jinha Kim, and Hwanjo Yu. 2013. TurboGraph: A fast parallel graph engine handling billion-scale graphs in a single PC. In Proceedings of the ACM international conference on knowledge discovery and data mining (KDD). 77–85.
[4] Da Zheng, Disa Mhembere, Randal Burns, Joshua Vogelstein, Carey E Priebe, and Alexander S Szalay. 2015. FlashGraph: Processing billion-node graphs on an array of commodity SSDs. In Proceedings of the USENIX conference on file and storage technologies (FAST). 45–58.