Tech Sketch Bucket of Technical Chips by TIS Inc.

Neo4jでグラフ問題を効果的に取り扱おう

Pocket

世の中の課題を解決するに際しては、その対象をグラフとして表現することが広く行われます。このグラフ問題を効率的に解決するソリューションとして、グラフ構造に特化したアーキテクチャのデータベース Neo4j を紹介します。


グラフ問題

具体例

グラフ問題とはどのようなものでしょうか? ご存知でない方でも、グラフ問題を活用したシステムを日常的に使用しています。例えば、鉄道の経路検索システムです。鉄道の路線をグラフ化するには、駅をグラフのノードとして、駅のつながりをエッジとして表現します。
このグラフ問題は、Single Source Shortest Path(SSSP)問題を解決することになります。SSSP問題とは、図1のように駅と駅間の行き来できる経路およびその所要時間が与えられた場合に、ある駅を始点とし、他の駅へ行くための最短時間の経路を求めるものです。
neo4j_01_graph.jpg
    図1 SSSP問題

ソリューション

このグラフ問題を解決するソリューションは古くから研究されています。その1つは筆者が@ITの グラフ問題とバルク同期並列の常識をGiraphで体得 で紹介したGiraphで、汎用的なプラットフォームHadoop上で稼働するバルク同期並列のアルゴリズムでグラフ問題を解決するソリューションです。
今回は稼働プラットフォーム自体をグラフ問題に特化させたものに着目し、グラフ構造に特化したデータベースNeo4Jでグラフ問題をどのように取り扱えるかを見ていきます。

Neo4jとは

Neo4jの入手

今回評価するNeo4jはGPLv3のもとで使用できるCommunity editionのVer1.8を対象とします。その他にAGPLのもとで使用できるHA機能を持ったEnterprise editionもあります。
Neo4jの稼働はJAVA言語で埋め込み型で使用する場合と、Neo4jのサーバを起動しREST APIでアクセスする場合の2つの使い方があります。
埋め込み型の場合は、mavenを使用すると

のように、dependencyでNeo4jのライブラリに依存することを指定します。
サーバを起動する場合は、 ダウンロードサイト からモジュールを入手します。

Neo4jのアーキテクチャ

Neo4jのアーキテクチャは、グラフの構成要素を保持する"グラフ"、およびグラフを検索するための情報を保持する"インデックス"で構成されます。SSSP問題を例に、駅(グラフのノード)、駅間の経路(グラフのエッジ)がこのアーキテクチャにどのように格納されるかを図2に示します。
neo4j_02_struct.jpg
    図2 Neo4jのアーキテクチャ

グラフの構成要素は、駅(例として東京)はノードに格納され、Id(この場合は1)を持ちます。駅名はプロパティにName:東京として格納されます。駅間の経路(例として東京から大阪)はリレーションシップに格納され、その種類(この場合は経路という意味付けでLinkというものを定義)と対象のノードがId:1からId:2という情報を持ちます。この経路の所要時間はプロパティにLength:2として格納されます。
また、グラフを検索するための情報は、"駅名が東京のノードはId:1"のようにインデックスに格納します。

埋め込み型での使用

Neo4jをJava言語で埋め込み型で使用するプログラムの概要を示します。

1.データを格納するディレクトリ(例:"sssp")を指定し、データベースを作成します(存在すればオープンします)。

2.ノードとなる駅を2つ("東京"と"大阪")作成し、駅名をプロパティ"Name"に設定します(実際にはトランザクション処理が必要ですが説明を簡単にするため省略します)。

3.駅間の経路をリレーションシップLinkとして定義します。"東京"と"大阪"のLinkを作成し、その所要時間をプロパティ"Length"に設定します。

4.東京から大阪への最短経路をダイクストラのアルゴリズムで見つけます。ポイントとして、駅の指定は"東京"というプロパティではなくデータベース内に格納されたノードのIdを用いることです。

Neo4jの活用に際してのポイント

インデックスの使用

実際の使用局面では、前述プログラムの1〜4が連続して1つのアプリケーションで実行されるのではなく、1〜3の処理で作成したデータベースに対して、4の検索処理が単独のアプリケーションで繰り返し実行されることになるでしょう。この検索アプリケーションには駅名を検索条件として引き渡しますが、検索処理ではデータベース内のノードのIdを用いますので、駅名からIdを特定する必要があります。このための検索機能としてインデックスが必要となります。

まずデータベース構築時にインデックス領域を作成します。下記では"nodes"という名前のインデックスを作成しています。ノードを作成し駅名のプロパティを設定した際には、駅名からノードのIdを検索できるようにインデックスに登録します。

検索処理においてはインデックスを使用して駅名からノードのIdを特定します。

検索処理のバリエーション

最短経路以外の検索処理の例を示します。例えば隣接する駅をすべて列挙するのは下記のような処理になります。

これは、開始ノード"東京"から始めて、深いレベルにあるノードをたどる前に同じ深さにあるすべてのノードをたどり(Order.BREADTH_FIRST)、深さ1にあるノードをたどったら停止して(StopEvaluator.DEPTH_ONE)、開始ノード"東京"以外のすべてのノードを返すようにします(ReturnableEvaluator.ALL_BUT_START_NODE)。この際、方向が外向き(Direction.OUTGOING)でタイプがLinkのリレーションシップだけを対象としています。

また、本例では鉄道の駅間の経路のリレーションシップLinkの1種類だけですが、他の交通手段として飛行機も用いる場合、飛行機のリレーションシップを用意すれば、飛行機を使用した経路を検索するといったことが可能となります。

Neo4jのサーバの使用

サーバの準備

Neo4jをサーバとして使用するのはどのようにすればよいでしょうか?ここでは前述の埋め込み型で作成されたデータベースをサーバに読み込み、どのような検索処理が行えるかを紹介します。
データベースの読み込みは埋め込み型で作成されたデータベースのディレクトリを、Neo4jのモジュールを展開した中のディレクトリ"data/graph.db"にコピーすることで行えます。

ノードのURLの特定

サーバに対する検索処理はREST APIを用います。これには、まず先ほどの埋め込み型の場合と同様に、駅名からノードのIdを特定するため、次のHTTPリクエストを投げます(インデックスの領域nodesに対して東京のノードを問い合わせます)。

このレスポンスは下記のJSON形式で返され、"self"からノードのId(REST処理で使用するURL)が特定できます。

検索処理の実行

最短経路の検索処理は、得られたノードのIdより次のJSON形式のデータのHTTPリクエストを投げます(POSTのURLが始点のノードで、POSTデータに終点のURLを指定します)。

このレスポンスは下記のJSON形式で返され、"nodes"が最短経路の始点から終点までの駅のリスト、"weight"が所用時間になります。

データベースのメンテナンスは?

グラフデータのちょっとした構成変更時(駅の追加、名称変更など)にいちいちプログラムを作成して対応するのは現実的ではありません。Neo4jのグラフデータをメンテナンスするためのEclipseベースのGUIが neoclipse で提供されています。これは埋め込み型で作成したディレクトリ、あるいはNeo4jサーバに接続し、そのグラフ構造を表示します。
neo4j_03_gui.png
    図3 neoclipseでのグラフのメンテナンス

起動時はデータベース構築時に最初に作成された駅およびそれに隣接する1つの経路で到達できる駅が表示されていますので、編集したい駅を検索処理で探すか、リンクをたどっていくかで表示させ、プロパティの追加・変更、ノード・リンクの追加といったメンテナンスが行えます。

最後に

Neo4jの実力を見るため、SSSP問題を解く性能をGiraph(Hadoopは疑似クラスターで実行)と比較します。

  Neo4j Giraph
グラフ規模
総処理時間 523m秒 1138m秒 27000m秒 測定できず
1つ目の検索時間 170m秒 501m秒 5293m秒 測定できず
2つ目の検索時間 0m秒 74m秒

       注1:グラフ規模小:図1で東京ー>鹿児島の検索
          グラフ規模大:ノード数が242(始点、終点の経路に24のノードが存在)
       注2:Giraphの"測定できず"は整数のオーバフロー?のため処理結果が異常
       注3:Neo4Jの検索時間以外の所要時間はデータベースの読み込み時間です。
       注4:Giraphの検索時間以外の所要時間はHadoopのJobの起動時間です。

Giraphはグラフ構造を処理する専用のアルゴリズムですが、Hadoopのジョブを起動するコストが大きく、実際の検索時間だけ見てもNeo4jの30倍以上要し、検索処理を続けて実行する際はHadoopのジョブを再度起動するため同じオーダーの処理時間がかかります。
これに対し、Neo4jは一度検索処理を行うとデータがキャッシュに乗る模様で2回目以降の処理は非常に短時間で行われ、またグラフが大規模になっても大きな性能劣化は見られません(使用したダイクストラのアルゴリズムの計算量のオーダーはノード数の自乗です)。

またメンテナンスの観点では、GiraphにはデータをGUIでメンテナンスする方法が提供されず、データ量が大規模になれば現実的にはメンテナンスが不可能になってきます。さらにGiraphでは駅名が文字列ではなく数値で指定するため、データの分かりにくさに拍車をかけています。
このようにグラフ問題を解く上ではグラフ構造に特化したアーキテクチャのデータベースNeo4jが遥かに優れています。

近年のソーシャルネットワークなどのグラフ問題で取り扱うデータサイズが劇的に大きくなるなかで、Neo4jが魅力的なソリューションになるでしょう。

エンジニア採用中!私たちと一緒に働いてみませんか?