読者です 読者をやめる 読者になる 読者になる

Neo4jではてなブックマークグラフをつくってみた

最近Neo4jというデータベースに触れる機会がありました。

Neo4jはグラフ構造を扱えるデータベースシステムで、人間関係のネットワークやWebページ間のリンク関係などを扱うのに適しています。 グラフデータベースでは「友達の友達の友達」や「10以上リンクされているページ同士の相互リンク」といった情報を簡単に引き出すことができます。

これらをRDBMSで実現しようとすると何段ものJOINが必要となり、クエリが複雑になって計算量も増えてしまいがちです。 グラフデータベースを使えば、クエリを簡潔に保ち、計算量も抑えることができます。

今回は日頃から利用しているはてなブックマークのデータを使い、Neo4j上にはてブグラフを構築していろいろなクエリを試してみました。

はてなブックマークWebおよび公開APIから取得できるデータのみを使用しています。

グラフとは

ここでいう「グラフ」はExcelで描けるようなグラフとは異なり、「ノードとそれらの間の関係によって構成されるデータ構造」のことを意味します。

グラフ (データ構造) - Wikipedia

グラフ構造はとても興味深い性質をもっており、グラフ理論という数学の一分野で扱われます。

グラフ理論 - Wikipedia

はてブグラフとは

「ユーザがエントリをブックマークしている」ことは、「ユーザとエントリの間にブックマークという関係が存在する」こととみなせます。

f:id:yubessy:20150914135452p:plain

はてなブックマークでは、たくさんのユーザが各々たくさんのエントリをブックマークしているので、次のようなグラフが生じます。

f:id:yubessy:20150914135514p:plain

このようなグラフを はてブグラフ と呼ぶことにします。

はてブグラフを見れば、エントリの被ブックマーク数はもちろん、「どのユーザ同士が同じページをブックマークしているか」といったこともすぐにわかります。

ちなみに、このような2種類のノード(ユーザ・エントリ)をもち、なおかつ異なる種類のノード間にしか関係が存在しないようなグラフを「2部グラフ(bipartite graph)」と呼びます。 ユーザ間のお気に入り・入られや、エントリ間のリンクなどを考えない場合、はてブグラフは典型的な2部グラフとなります。

Neo4jのインストール

やっとNeo4jの登場です。

Neo4jはMySQL等と同様に、デーモンプロセスとして動作します。 インストールは、ダウンロード→展開→startで済みます。 Homebrewを使っていれば、以下を実行するだけでインストールと起動ができます。

$ brew install neo4j
$ neo4j start

Neo4jにはデフォルトでWebインタフェースが用意されており、プロセスを起動した状態で http://localhost:7474/ にアクセスすることですぐに利用できます。 データベースは基本的に1プロセスにつき1つです。RDBMSではないのでテーブルはなく、全てのオブジェクトはノードか関係のいずれかです。

Cypher: Neo4jのためのデータベース操作言語

RDBMSSQLを使うのと同様に、Neo4jではCypherというデータベース操作言語を使います。

以下のCypherプログラムは、ユーザとエントリのノードを作成し、その間にブックマーク関係を付与します。

CREATE
  (u:User {name: "yubessy"}),
  (e:Entry {url: "http://b.hatena.ne.jp/"}),
  (u)-[:BOOKMARK]->(e);

ノードは (<変数名>:<ラベル> {<属性名1>: <属性値1>, ...}) で表します。 ノードXからY間への関係は (<ノードX>)-[<変数名>:<ラベル> {<属性名1>: <属性値1>, ...}]->(<ノードY>) で表します。関係を作成する際には必ず向きを指定しないといけません。 ノード・関係のいずれに対しても0個以上の属性を指定することができます。 変数名は後方参照で使わない場合は不要です。

CypherはWebインタフェースや各言語用のライブラリから実行できます。

Cypherによるクエリ

Cypherの利点は、パターンマッチによって柔軟なクエリが発行できることです。

以下は最も簡単なクエリの構文です。

MATCH <変数を含むパターン> RETURN <変数>;

このクエリを実行すると、 MATCH 句で <変数を含むパターン> にマッチする構造を探してオブジェクトを変数に束縛し、 RETURN 句で変数に束縛されたオブジェクトを返します。

以下ではグラフ中のパターンにマッチする構造を 部分グラフ と呼びます。

例えば「ユーザyubessyがブックマークしているエントリの一覧」は以下のクエリで取得できます。

MATCH (:User {name: "yubessy"})-[:BOOKMARK]->(e:Entry) RETURN e;

このクエリを実行すると、「yubessyというnameのユーザがエントリeをブックマークしている」ことを示す部分グラフを探し、見つかったそれぞれの部分グラフに含まれるエントリを変数に束縛し、束縛されたエントリを全て返す、という処理が行われます。

Cypherを使う際には、 () がノード、 ()-[]->() がノード間の関係とだけ覚えておけば、あとは直感的にクエリを書くことができます。 クエリ中には ()-[]-() のように関係の向きを指定しないパターンも使用できます。

はてブグラフの構築

今回はローカルで起動しているNeo4jに、はてなブックマークから取得した以下のようなデータを投入してみました。

  • エントリ: 2015年8月のとある日の「テクノロジー」カテゴリのホットエントリ上位200件
  • ユーザ: 同日時点で上記のエントリを1つ以上公開ブックマークしているユーザ 全4086名
  • ブックマーク: 上記のエントリ・ユーザ間に存在するブックマーク全9301件

エントリのデータはホットエントリRSS、ユーザとブックマークのデータはエントリー情報取得APIを用いて取得しました。 データ取得の際はサービスに負荷をかけないよう、アクセスは直列に行い、10秒以上のインターバルを設定しました。

Neo4j上でのデータ表現は次のようにしました。

  • ユーザ: (:User {name: <ユーザ名>})
  • エントリ: (:Entry {url: <URL>, title: <タイトル>})
  • ブックマーク: (<ユーザ>)-[:BOOKMARK {comment: <コメント>, timestamp: <ブックマークした日時>, tags: <タグ一覧>}]->(<エントリ>)

はてブグラフに様々なクエリを発行してみる

以下では構築したはてブグラフに対し、Cypherを使って様々なクエリを発行してみます。

Neo4jのWebインタフェースは非常に優秀で、実行結果をグラフ図として出力してくれます。クエリと合わせてこのグラフ図も載せています。

あるユーザのブックマーク一覧

先程と同様のクエリですが、ラベルと変数が少し異なっています。

今回のデータベースに存在する関係は BOOKMARK のみであり、関係は必ずユーザからエントリに向けて張られるため、パターン中に関係とその向きが含まれていれば、ラベルは省略できます。

また、実行結果には RETURN 句で指定した変数に束縛されたオブジェクトしか含まれないため、Webインタフェースでグラフ図を描画するには、描画したいオブジェクトを変数に束縛するする必要があります。

MATCH (u {name:"yubessy"})-[b]->(e)
RETURN u, b, e

実行結果は以下のようになります。緑・青それぞれの丸がユーザ・エントリを示すノードです。

f:id:yubessy:20150914135520p:plain

タイトルに"JavaScript"を含むエントリに対する、"JavaScript"というタグの付いたブックマーク一覧

ノードや関係につけた属性値は WHERE 句による絞り込みに利用できます。

Cypherには豊富な種類の演算子が揃っており、正規表現も使えます。 また、属性値にリストを入れることもでき、それに対して IN 演算子を適用することもできます。

MATCH (u)-[b]->(e)
WHERE e.title =~ ".*JavaScript.*" AND "JavaScript" IN b.tags
RETURN u, e, b;

実行結果では、ユーザ名は適当な番号に置き換えています。 図がそれらしくなってきました。

f:id:yubessy:20150914135524p:plain

あるユーザの総ブックマーク数

SQLと同様に COUNT 等の集約関数を実行できます。

MATCH ({name:"yubessy"})-[]->(e) RETURN COUNT(e)

このクエリはノードや関係を返していないのでグラフ図は描画されません。

8

あるユーザがブックマークしているエントリのうち1つ以上をブックマークしているユーザ(name順上位10件)

このクエリは言葉で表現すると少し複雑ですが、パターン記法のおかげで何を求めているかが直感的にわかります。

上位10件としているのはそのままだと非常に多くのユーザが返ってしまうため、 またユーザname順としているのはなるべく異なるエントリがグラフ上に描画されるようにするためで、深い意味はありません。

MATCH (u {name:"yubessy"})-[b1]->(e)<-[b2]-(o)
RETURN u, b1, e, b2, o ORDER BY o.name LIMIT 10

真ん中の「831」となっているのが私(id:yubessy)です。

f:id:yubessy:20150914135530p:plain

あるユーザがブックマークしているエントリのうち7つ以上をブックマークしているユーザ一覧

最後の例は少し複雑です。

今回は新しい構文、 WITH 句を使います。 クエリを句ごとに説明すると、

  1. MATCH (u {name:"yubessy"})-[]->()<-[]-(o)
    • パターン「yubessyがブックマークしているエントリをユーザoがブックマークしている」にマッチする部分グラフを取得
  2. WITH u, o, COUNT(*) as c
    • 得られた部分グラフを (u, o) の組み合わせ毎にグルーピングし、各グループに含まれる部分グラフ数をcとする
  3. WHERE c >= 7
    • 部分グラフ数が7以上のグループのみを選択する
  4. MATCH (u)-[b1]->(e)<-[b2]-(o)
    • u, oに束縛されたオブジェクトの集合に対し、改めてパターン「uがブックマークしているエントリeをoがブックマークしている」にマッチする部分グラフを取得
  5. RETURN u, b1, e, b2, o
    • 部分グラフ中の各変数に束縛されたオブジェクトを返す

という感じでしょうか。厳密にはちょっと説明が怪しいかもしれません。

7という数はグラフ図がいい感じになる値を選んだだけで、深い意味はありません。

MATCH (u {name:"yubessy"})-[]->()<-[]-(o)
WITH u, o, COUNT(*) AS c
WHERE c >= 7
MATCH (u)-[b1]->(e)<-[b2]-(o)
RETURN u, b1, e, b2, o

実行結果中のノードの配置はわかりやすいように編集しました。 左側の緑丸の集合が取得したかったユーザの一覧です。 ブックマークを示す矢印が壮観ですね。

f:id:yubessy:20150914135536p:plain

まとめ

Neo4jにはてなブックマークのデータを入れて簡単なクエリを試してみた、という話でした。

グラフ構造は身の回りの至る所に存在しますが、グラフデータベース自体はあまり普及していないようです。これから使う人が増えて、情報がどんどん出てきたらいいなと思います。