GraphDB 入門
TinkerPop の使い方

Shoshi Tamaki
Nobuyasu Oshiro
08 Sep 2012

もくじ

GraphDB とは？

Graph構造を保存するためのデータベース．

Graph構造とは，たとえばこんなもの

GraphDB とは？

このような構造をしたGraphはPropertyGraphと呼ばれる．

PropertyGraphとは，

PropertyGraph

関係・人物・名前・特徴はVertex・Edge・Label・Propertyと呼ばれる．

GraphDBとは？

GraphDBは，保存されたGraphのVertex,Edgeを渡り歩き，目的のデータを取得するようなデータベースである．

渡り歩くことをTraverseという．

TinkerPop

TinkerPopはGraphDBを利用するためのツール群である．

Blueprints

Blueprintsは，PropertyGraphのJavaのinterfaceを提供する．

GraphDBの世界のJDBCの立場を目指している．

Gremlin

GraphをTraverseするための言語．Groovyがベースである．GraphDBに対してQueryを発行することが出来る．コンソールも利用できる．

gremlin> graph.v(1).out.name
==>vadas
==>lop
==>josh

GremlinはPipesを利用して，GraphをTraverseする．.out.nameがPipeである．．

Pipes

PipesはGraphを処理するためのフレームワークである．Pipeという処理の単位を複数連結し，複雑なTraverseを実現する．

graph.v(1)はGraphからIDか1のVertexを取得する，.out .name がぞれぞれPipeに値する．

Pipes

この例題の動作は・・・

gremlin> g.v(1).out.name
==>vadas
==>lop
==>josh

ストライクウィッチーズの相関図を解析するには？

1. BlueprintsでTinkerGraphにストライクウィッチーズの相関図を入力する．
2. 作成したTinkerGraphを，
• Gremlinのコンソールから解析してみる．
• JavaからGremlinを使って解析してみる．

まずは，TinkerGraphにストライクウィッチーズの相関図を入力する．

この発表のサンプルコードについて

hg clone https://bitbucket.org/suikwasha/graphdb_javakuche

ビルド方法・解凍したディレクトリに移動して
$ mvn compile

ストライクウィッチーズの相関図を解析するには？

Blueprintsは，GraphDBへのインターフェイスを提供する．TinkerGraphはBlueprintsを用いて利用できる．

// 相関図（Graph）の作成，データを保存するディレクトリを引数に取る
Graph g = new TinkerGraph();

// 人物（Vertex）の作成，設定したいIDを引数に取る
Vertex character = g.addVertex(ID);

// 関係（Edge）の作成，設定したいIDを引数に取る
Edge relation = g.addEdge(ID,From,To,Label);

// 特徴（Property）の作成 , Vertex・Edgeともに同様のメソッド
character.setProperty(PropertyName,PropertyValue);

ストライクウィッチーズの相関図を解析するには？

これを入力します．

ストライクウィッチーズの相関図を解析するには？

画像を見ながらコードに書き起こすと・・・

Graph g = new TinkerGraph("./strikewitches"); // 保存ディレクトリ
Vertex strikeWitches = g.addVertex("StrikeWitches");
Vertex yoshika = g.addVertex("yoshika");
yoshika.setProperty(propName,"宮藤芳佳");
yoshika.setProperty(propRank,"軍曹");
yoshika.setProperty(propAge,14);
yoshika.setProperty(propCV,"福圓美里");
yoshika.setProperty(propUnit,"扶桑皇国海軍遣欧艦隊");
yoshika.setProperty(propPersonality,"明るく前向きで一生懸命");
Vertex lynett = g.addVertex("lynett");
lynett.setProperty(propName,"リネット・ビショップ");
lynett.setProperty(propRank,"軍曹");
lynett.setProperty(propAge, 15);
lynett.setProperty(propCV,"名塚佳織");
lynett.setProperty(propUnit,"ブリタニア空軍");
lynett.setProperty(propPersonality,"家庭的で戦闘は苦手");
g.addEdge(null,yoshika,lynett,"仲良し新人コンビ");
g.addEdge(null,lynett,yoshika,"仲良し新人コンビ");

CreateStrikeWitchesGraph

実際にコードを動作させてTinkerGraphに入力する．

プロジェクトのディレクトリにstrikwitchesが作成される．

ストライクウィッチーズの相関図を解析するには？

Blueprintsを用いてTinkerGraphに相関図を書き込むことが出来た．

今回は，Graph探索のサンプルのため"StrikeWitches"というキャラクター全員が所属する頂点を追加してある．

1. BlueprintsでTinkerGraphにストライクウィッチーズの相関図を入力する．
2. Gremlinを使って，TinkerGraphを読み込み，
• Gremlinのコンソールから解析してみる．
• JavaからGremlinを使って解析してみる．

では，Gremlinを利用して相関図を解析してみる．

ストライクウィッチーズの相関図を解析するには？

Gremlinのセットアップ

• github tinkerpop/gremlin > Wiki のdownloadsからgremlin-groovy-2.1.0.zipを利用する．
• 解凍して展開する．
• bin/gremlin.shを実行

% ./gremlin.sh                                                                                                              [~/Downloads/gremlin-groovy-2.1.0/bin]
         \,,,/
         (o o)
-----oOOo-(_)-oOOo-----
gremlin>

こんなの表示される．

ストライクウィッチーズの相関図を解析するには？

Gremlin に相関図を食べさせて，解析開始．

gremlin> g = new TinkerGraph("path_to_graph");
==>tinkergraph[vertices:12 edges:32 directory:path_to_graph]
gremlin> 

Vertexの一覧を取得してみる．

gremlin> g.V // GraphのVertex一覧
==>v[mio]
...
==>v[minna]
==>v[lynett]
...
==>v[gertrud]
==>v[francesca]

ストライクウィッチーズの相関図を解析するには？

宮藤芳佳の年齢を取得．

gremlin> g.v("yoshika").age
==>14

宮藤芳佳を指導しているのは誰？

gremlin> g.v("yoshika").in("指導").name
==>坂本美緒

宮藤芳佳のことをきっー！なんなんですのアナタは！？と思っている人が勤務態度に不満を持っている人たち

gremlin> g.v("yoshika").in("きっー！なんなんですのアナタは！？")
      .out("勤務態度に不満").name
==>シャーロット・E・イエーガー
==>フランチェスカ・ルッキーニ

ストライクウィッチーズの相関図を解析するには？

宮藤芳佳のことをきっー！なんなんですのアナタは！？と思っている人が勤務態度に不満を持っている人たち

gremlin> g.v("yoshika").in("きっー！なんなんですのアナタは！？")
      .out("勤務態度に不満").name
==>シャーロット・E・イエーガー
==>フランチェスカ・ルッキーニ

ストライクウィッチーズの相関図を解析するには？

16歳以下のウィッチ一覧

gremlin> g.v("StrikeWitches").out.filter{it.age < 16}.name
==>宮藤芳佳
==>エイラ・イルマタル・ユーティライネン
==>サーニャ・V・リトヴャク
==>リネット・ビショップ
==>ペリーヌ・クロステルマン
==>フランチェスカ・ルッキーニ

ストライクウィッチーズの相関図を解析するには？

GremlinをJavaから使うためには，Mavenを利用するのが簡単である．

Mavenはプロジェクト管理ツールであり，他のプロジェクトのライブラリを簡単に取り込むことができる．

pom.xmlにGremlinを取り込むように記述する．

<dependency>
  <groupId>com.tinkerpop.gremlin</groupId>
  <artifactId>gremlin-java</artifactId>
  <version>2.1.0</version>
</dependency>

"Using Gremlin through Java" よりtinkerpop/gremlin wiki

ストライクウィッチーズの相関図を解析するには？

TinkerGraphで作った，相関図を読み込む

Graph g = new TinkerGraph("path_to_graph");

GremlinPipeline の作成

GremlinPipeline<Vertex,String> pipe
 = new GremlinPipeline<Vertex,String>();
pipe.start(g.getVertex("yoshika"))....

GremlinはGraphに対して処理をするPipeをつなげて，複雑な探索を可能にする．Gremlin コンソールでは見えないが，JavaではPipesを利用しているのが確認できる．

ストライクウィッチーズの相関図を解析するには？

宮藤芳佳を指導しているのは誰？

pipe.start(g.getVertex("yoshika")).in("指導").property("name");
for(String name : pipe){
 System.out.println("name")
}

宮藤芳佳のことをきっー！なんなんですのアナタは！？と思っている人が勤務態度に不満を持っている人たちの年齢

pipe.start(g.getVertex("yoshika")).in("きっー！なんなんですのアナタは！？")
 .out("勤務態度に不満").property("age");
for(Integer age : pipe){
 System.out.println(age);
}

ストライクウィッチーズの相関図を解析するには？

15歳以上のウィッチーズの名前

pipe.start(g.getVertex("StrikeWitches")).out("member")
 .filter(new PipeFunction<Vertex,Boolean>(){
  public Boolean compute(Vertex _argument){
   return (Integer)_argument.getProperty("age") >= 15;
  }
 }).name;
for(String name : pipe){
 System.out.println(name);
}

書き方としては，Gremlin コンソールでのほうが簡潔．

gremlin> g.v("StrikeWitches").out.filter{it.age > 15}.name

ストライクウィッチーズの相関図を解析するには？

Gremlin コンソールでの書き方を Java で利用することができる．

Pipe pipe = Gremlin.compile("_().out.filter{it.age > 15}.name");
pipe.setStarts(
 new SingleIterator<Vertex>(g.getVertex("StrikeWitches"));
for(Object name : pipe){
 System.out.println(name);
}

_()はGremlinePipelineに定義されている何もしないPipe

JavaでPipeを直接構築するより，こっちのほうが簡単である．

まとめ

これまでに，ストライクウィッチーズの相関図を利用してGraphDBの概要とTinkerPopの簡単な使い方を見てきた．

この発表で大体のイメージが掴めてもらえれば幸いです．

• GraphDBは，GraphのEdgeをTraverseして，目的のデータを取得するデータベース
• GraphDBは，PropertyGraphを格納する．

• TinkerPopは，GraphDBを利用するためのツールの集合

次に，具体的な利用例としてPageRankのGraphDBでの表現について発表する．

TinkerPopによるPageRankの実装

• PageRankアルゴリズム
• PageとPageRankのGraphDBによる表現
• TinkerPopによるPageRankの計算
• Pipesによる走査
• PageRankの計算にかかる時間

GoogleのPageRankアルゴリズム

• GoogleのWebページ検索エンジンに使われているアルゴリズム。
• あるページの『重要度』を示す値で、各ページ毎に持っている。
• PageRankが高いほど検索結果の上位に表示される。
• 『多くの良質なページからリンクされているページは、やはり良質なページである』という考えのアルゴリズム
  
• GraphDBはPageRankの計算に向いている。

PageとPageRankのGraphDBによる表現

• アンサイクロペディアの各ページをGraphDBで表す。
• 1Vertexが1つのページを表す。
• 各VertexはPageTitleとPageRankをPropertyとして持つ。
• リンクは "HAS_LINK" という関係で表される。
• PageRankはdoubleで初期値は 0.15 , 最大値はページ数*0.15
• アンサイクロペディアではURIはページタイトルと同じ。
• URIに対してユニークなVertexID を割り振る。

TinkerPopによるPageRankの計算

• ○はVertexを、→ はEdgeを表す。



例：アンサイクロペディア内のページ『琉球大学』のリンクの関係

PageRankアルゴリズム

• PageRankは次の計算式で求めることができる。

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

• PR(A) は A というページのPageRankを表す。
• d は定数で 0.85
• C(T1) は T1 というページがリンクを張っている数を表す。
• T1...Tn は A をリンクしているページなので、C(T1)...C(Tn) は 0 にならない。
• GoogleのPageRankはこれを改良したものである。
• 今回はこのアルゴリズムを使ってPageRankを求める。

PageRankの取得

• TinkerGraph上でPageRankの値を出すために以下の2つの値が必要
• リンク("HasLink")の関係を張ってくるVertexの取得
• リンクしてくるVertexがどれだけリンクを張っているかを取得

*各ページの情報はXMLから取り出しBlueprintsを用いてTinkerGraphに書き込み済み。

Pipesによる走査

• あるページへとリンクを張るページ(Vertex)の取得

「id」はVertexのIDを表す。

Graph graph = ...
GremlinPipeline pipe = new GremlinPipeline();
pipe.start(graph.getVertex(id));
pipe.in("HasLink");
for (Object inVerObj : pipe) {
 VertexinVer = (Vertex)inVerObj;
  :
}	  

Pipesによる走査

• あるページが張っているリンクの数の取得

Graph graph = ...
GremlinPipeline pipe = new GremlinPipeline();
pipe.start(graph.getVertex(id));
pipe.out("HasLink");
long linkNum = pipe.count();
	

TinkerPopによるPageRankの計算

final double weight = 0.85;
double sum = 0.0;
double pageRank = 0.0;
Vertexv = graph.getVertex(id);
GremlinPipeline pipe = new GremlinPipeline();
pipe.start(graph.getVertex(id)).in("HasLink");
for (Object inVerObj : pipe) {
 VertexinVer = (Vertex) inVerObj;
  Object inVerId = inVer.getId();
  GremlinPipeline inPipe = new GremlinPipeline();
  inPipe.start(graph.getVertex(inVerId)).out("HasLink");
  long linkNum = inPipe.count();
  double pr = (Double) inVer.getProperty(PAGE_RANK);
  sum += (double) pr / linkNum;
}
pageRank = (double) 1 - weight + (double) sum * weight;
v.setProperty(PAGE_RANK, pageRank);

計算結果

• アンサイクロペディア内でPageRankの高いページ
• 総ページ数: 242014 ページ

ページ名	リンク数	PageRank
ユーモア枯渇症	7162	71.120
日本	3537	54.584
アンサイクロペディア	3887	54.164
ウィキペディア	2414	44.617
ニンジャスター	177	36.167

PageRankの計算にかかる時間

• PageRankは 10 回かからずの計算でほぼ収束した。
• PageRankの計算は10回行うとして、ページ数に対してかかる時間を測ってみた。

PageRankの計算にかかる時間

• 各ページ数で行う10回計算をそれぞれ10回ずつタイムを測り平均をとった。

ページ数	10回の計算にかかった時間(単位:ms)
100	21
1000	67
10000	976
50000	7140
100000	26150
200000	74130
242014	93512

PageRankの計算にかかる時間

まとめ

• 今回、TinkerPopを用いてアンサイクロペディアの各ページのPageRankを求めた。
• 各ページとVertex, リンクの関係をEdgeで表すことで各ページ間の関係をTinkerPop上で表した。
• Gremlin を用いて各Vertexを渡り歩ことでPageRankの計算を行った。
• 全Vertexに対しての計算量はVertexの数に比例していることが確認できた。

今日の勉強会で覚えておきたいこと

• Graph の関係を表すようなデータはGraphDBで表現しやすい。
• GraphDBではVertex間を渡り歩く(Traverse)ことでデータの取得を行う。
• GraphDBは局所性のあるデータを高速に計算することができる。

参考文献・サイト

• [1]Googleの秘密 -PageRank徹底解説
  http://homepage2.nifty.com/baba_hajime/wais/pagerank.html
• [2] LawrencePage, Sergey Brin, Rajeev Motwani, Terry Winograd, 'ThePageRankCitation Ranking: Bringing Order to the Web', 1998,
  http://www-db.stanford.edu/~backrub/pageranksub.ps
• [3] ThePageRankAlgorithm
  http://pr.efactory.de/e-pagerank-algorithm.shtml
• [4] グラフデータベースを用いたPageRank実装の試み：スケーラブルなグラフ処理系に向けて
  http://live-e.naist.jp/sensor_overlay/5/doc/hanai.pdf

なぜPageRankなのか

• PageRankはPageとPageのリンクの有無を利用して計算できる。
• GraphDBはVertexとVertexを結ぶEdgeを走査(Traverse)することで、 目的のデータを得るようなデータベースである。
• また、GraphDBは局所性のあるデータを高速に計算することができる。
• PageRankのPageの関係はGraphDBのVertexとEdgeで表すことができる
• また、Pageの数が増えても局所的な計算ができるためGraphDBはPageRank を求める DB に向いている。