グラフ構造データを扱うはなし

Yu Watanabe(@yuw27b)
2017.03.25 NDS 第51回勉強会

自己紹介

ECサイト運営
[東京] 非常勤エンジニア＋フリーランス
[新潟]

最近のお仕事

SPA＋API＋DBなWebサービスの制作
  • データからグラフを描画するサービス
  • データやファイルを送ってもらってデータベースを作るサービス
技術面
  • JavaScript[Backbone.js/React.js/Node.js]
  • Ruby、PHP
  • MySQL、Neo4j、RDF
その他

サービスのサーバ設定・管理

HTML＋CSS＋JavaScriptのコーディング

・・・などをやっています。

話すこと

  • グラフデータベースで扱えるもの
  • グラフデータベースで扱わないほうがいいもの
  • グラフデータベースってこんな感じ
  • オープンデータへのアクセス
  • ブラウザやデスクトップでの可視化

もくじ

  • グラフ構造データとは
  • グラフデータベース
  • オープンなグラフデータ・RDF
  • グラフデータの可視化

グラフ構造データ

データ構造の種類

  • 配列 [スタック/キュー]
  • 連想配列 [ハッシュテーブル/ルックアップテーブル]
  • 線形リスト
  • 木構造
  • グラフ

  グラフデータベースで扱えるのはグラフと木構造

https://ja.wikipedia.org/wiki/データ構造

身近にあるグラフ構造

  • 鉄道路線
  • コンピュータネットワーク
  • 家系図（木構造）
  • SNSのfollow/followingの関係

  何かのネットワークまたは何かの相関関係

グラフ理論を少しだけ

  • ノード（頂点）とエッジ（辺）
  • 有向グラフと無向グラフ
  • エッジには重み付けができる
  • 単純グラフと多重グラフ

グラフデータベース

データベース管理システムの種類

RDBMS

MySQL / PostgreSQL / SQLite /
Oracle Database / Microsoft SQL Server
etc...

NoSQL

  • キー・バリュー型・・・Redis / Memcached
  • ソート済みカラム指向・・・Apache Cassandra / Apache HBase
  • ドキュメント指向・・・MongoDB / Apache CouchDB
  • グラフ型・・・Neo4j

https://ja.wikipedia.org/wiki/データベース管理システム
https://ja.wikipedia.org/wiki/NoSQL

Neo4j

  • グラフデータベースの代表的なもの
  • https://neo4j.com/
  • 実装はJava
  • Cypher Queryというものでデータの検索・操作をする
  • 主要な言語のドライバが存在する
    公式ドライバ：JavaScript/Java/.NET/Python
    他はコミュニティでの開発

導入事例

  • ロジスティクス
  • レコメンデーションエンジン
  • SNS
  • 科学分野
  • パナマ文書

https://neo4j.com/customers/
https://medium.com/@c_z/「パナマ文書」解析の技術的側面-d10201bbe195#.8gbo4jc8n
https://neo4j.com/blog/analyzing-panama-papers-neo4j/

とりあえず動かしてみる

デモ - データの準備

CSVやTSVで、「Node1」「Node2」「Edge」のリストを用意する。

JSONやXMLでももちろんOKです。

FromTo$
AB30000
AC10000
AD10000
BD50000
DE100000
DF20000
CD30000
・
・
・

CSVであればロード用のコマンドラインツールも付属しています。
が、データサイズに比例してメモリ消費が増えたり、プロパティが多くなるとコマンドのオプションも複雑になるので、
何かしらの言語でパースしながらロードするほうがやりやすく感じます。

デモ - データのロード

Cypher query


CREATE (n:Person { name: 'A' })
CREATE (n:Person { name: 'B' })
CREATE (n:Person { name: 'C' })
CREATE (n:Person { name: 'D' })
CREATE (n:Person { name: 'E' })
CREATE (n:Person { name: 'F' })
CREATE (n:Person { name: 'G' })
CREATE (n:Person { name: 'H' })
CREATE (n:Person { name: 'I' })
CREATE (n:Person { name: 'J' })
MATCH (a:Person),(b:Person) WHERE a.name = 'A' AND b.name = 'B' CREATE (a)-[r:rel {price: 30000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'A' AND b.name = 'C' CREATE (a)-[r:rel {price: 10000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'A' AND b.name = 'D' CREATE (a)-[r:rel {price: 10000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'B' AND b.name = 'D' CREATE (a)-[r:rel {price: 50000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'D' AND b.name = 'E' CREATE (a)-[r:rel {price: 100000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'D' AND b.name = 'F' CREATE (a)-[r:rel {price: 20000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'C' AND b.name = 'D' CREATE (a)-[r:rel {price: 30000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'D' AND b.name = 'B' CREATE (a)-[r:rel {price: 10000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'F' AND b.name = 'G' CREATE (a)-[r:rel {price: 50000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'F' AND b.name = 'H' CREATE (a)-[r:rel {price: 10000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'C' AND b.name = 'I' CREATE (a)-[r:rel {price: 20000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'I' AND b.name = 'J' CREATE (a)-[r:rel {price: 30000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'F' AND b.name = 'J' CREATE (a)-[r:rel {price: 20000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'I' AND b.name = 'F' CREATE (a)-[r:rel {price: 10000}]->(b)
MATCH (a:Person),(b:Person) WHERE a.name = 'G' AND b.name = 'J' CREATE (a)-[r:rel {price: 10000}]->(b)

Ruby driver経由


require 'neo4j-core'

tsv_file = ARGV[0]
neo4jpwd = ARGV[1]

Neo4j::Session.open(:server_db, "http://neo4j:#{neo4jpwd}@localhost:7474")

nodes = []
relations = []
File.open(tsv_file).each_line do |l|
  person_from, person_to, price = l.chomp.split("\t")
  relations.push([person_from, person_to, price.to_i])
  nodes.push(person_from, person_to)
end


nodes.uniq.each do |node|
  Neo4j::Node.create({name: node})
end

relations.uniq.each do |rel|
  nodeFrom = Neo4j::Label.find_nodes(:node, :name, rel[0])
  nodeTo = Neo4j::Label.find_nodes(:node, :name, rel[1])
  nodeFrom.each do |n1|
    nodeTo.each do |n2|
      n1.create_rel(:rel, n2, price: rel[2])
    end
  end
end

Webコンソールで確認してみる

http://localhost:7474

検索してみる

$30,000以上のやりとり

MATCH n=()-[r:rel]->() WHERE r.price >= 30000 RETURN n
Aからお金を受け取った人のリスト

MATCH (a{name: 'A'})-[]->(b) RETURN b
Aからのお金がたどった経路(*)

MATCH n=({name: 'A'})-[:rel*..10]->() RETURN n
AとEにつながりはある？

MATCH n = (a{name: 'A'})-[:rel*]->(b{name: 'E'}) RETURN COUNT(n)

*グラフなので、かなり容易に組み合わせ爆発が起こります。
そのため、あまり長い探索は現実的な時間内では終わりません。
10ステップくらいでLIMITをかけておくのが無難です。

RDF

RDFとは何か

W3Cが標準化したWeb上のリソースの記述方式

トリプルで表現する



  
    NY

つまりグラフ

同じくW3Cが標準化したSPARQLという言語で検索できる

https://ja.wikipedia.org/wiki/Resource_Description_Framework

Web上のリソースがつながる

RDFをデータベースに入れる

  • データベースはトリプルストアとも呼ばれる
  • Virtuoso / Oracle / Apache Jena Fuseki / etc...
  • 検索APIはSPARQLエンドポイントと呼んだりする

オープンなSPARQLエンドポイント

https://www.w3.org/wiki/SparqlEndpoints
http://ja.dbpedia.org/

ブラウザAPIから入力してみてもいいし、POSTでリクエストを投げてJSONやXMLを受け取ってもいい。

SPARQLをちょっとだけ紹介

形に当てはめるようなクエリ


SELECT DISTINCT *
WHERE {
  <http://ja.dbpedia.org/resource/新潟県> ?p ?o .
}


SELECT DISTINCT *
WHERE {
  ?s ?p <http://ja.dbpedia.org/resource/新潟県> .
}

RDFのもやもやするところ

  • エンドポイントを横断する検索はできない
  • 述語を知らないと検索しにくい
  • オントロジーの分散
  • トリプルを作るのが手間
  • やっぱりRESTfulAPIでラップしたくなる・・・

グラフの可視化

可視化アルゴリズム

Force directed

Circular

他にもありますが、だいたいこのへんに落ち着くことが多いです。

可視化のためのツール

JavaScriptライブラリ

アプリケーション

これも他にもたくさんありますが、使ったことがあって紹介したいものはこんなところです。

まとめ

  • グラフ構造のデータはNeo4jに入れてみよう
  • ※目的によってはメリットが少ないこともある
  • RDFとSPARQLとオープンデータ
  • グラフの可視化 - ブラウザ上でインタラクティブに動かすこともできる

END