DEIM Forum 2019 D7-3

グラフモデルを用いた音楽推薦におけるグラフデータベースと関係データベースを併用した計算手法について
山口航†

欅惇志††

宮崎純††

† 東京工業大学情報工学科 〒 152–8550 東京都目黒区大岡山二丁目 12–1†† 東京工業大学情報理工学院 〒 152–8550 東京都目黒区大岡山二丁目 12–1
E-mail: †{yamaguchi,keyaki}@lsc.cs.titech.ac.jp, ††miyazaki@cs.titech.ac.jp
あらまし音楽グラフデータは、ユーザーが過去に作ったプレイリストの情報をグラフ構造で表したデータである。

本研究では、この音楽グラフデータに対しグラフデータベースと関係データベースを組み合わせることでクエリを効率よく処理する手法を提案する。グラフデータベースはグラフ探索に適していて、関係データベースは集合演算に適している。これらの利点を組み合わせることで、クエリ処理の効率化を実現し、その評価を行った。
キーワード グラフデータ，グラフデータベース，関係データベース
関係データベース単体、ネイティブグラフデータベース単体、1 はじめに近年データ量が増えると同時に、そのデータ構造が複雑になっている。その中でグラフ構造のデータを処理する必要性が高まっている。しかし、関係データベースを用いてグラフ構造をモデリングした場合、グラフ探索のクエリ処理時に結合演算をグラフ探索の木の内部のノード数分行うため処理のコストが多大にかかってしまう。

そして提案手法であるネイティブグラフデータベースと関係データベースの複合手法の三つを比べることによって提案手法の有効性を示す。

2 関連研究2. 1 RDB と KVS を利用した集約演算の効率化
渡らは、分散ストレージ上に蓄積された多次元のデータに対一方、従来の関係モデルでは扱うことが困難なデータを処理して、平均値などの集約演算値を求める範囲クエリをリレーする NoSQL データーベースが近年注目を浴びている。NoSQL

ショナルデータベース (RDB) と分散キーバリューストア (分散にはキーバーリューストアやドキュメント指向データベースなKVS) を組み合わせて効率的に処理する手法を提案した [1]。

どがあるが、その一種にグラフ構造を処理することを前提にRDB は多次元データを効率的に扱うことができ、集約関数設計されたネイティブグラフデータベースがある [2] [3]。ネイも標準で用意されているが、大規模データに対してスケールティブグラフデータベースでは、グラフのノード自体に隣接すアウトしづらいという問題が存在する。また、分散 KVS はスるノードのダイレクトなポインタが格納されている [4]。このケールアウトしやすく設計されているが、多次元データへのア性質により、グラフ全体のデータ量が増えたとしても一定のコクセスはしばしばデータの全スキャンを伴い非効率的である。

ストで隣接ノードの情報を取得することができる。よって、グRDB と分散 KVS を相互に活用することで，多次元データに対ラフ探索において関係モデルよりも処理のコストが低いといえする集約演算を効率化した。

る。しかし、ネイティブグラフデータベースはノード全体に対実験結果によると，KVS を単体で用いた場合に比べ 5.4〜する処理には適していない。例えば、各ノードの次数を数え上36.3 倍，RDB に対しても 2.9〜13.8 倍の高いクエリスループッ

げるなどの集合指向のクエリ処理には計算にコストがかかってトを実現している。

しまう。
グラフ構造のクエリ処理では、グラフ探索と集合指向が組み合わさったクエリが考えられる。SNS の友人同士の関係を表し

2. 2 関係データベースとネイティブグラフデータベースの性能比較

たグラフデータにおいて、ある友達の三次の友達が何人いるか

Hölsch らは、関係データベースとネイティブグラフデータというクエリは一つの例として挙げることができる。このクエベースの性能を関係データベースである PostgreSQL とネイリでは二次の友人をグラフ上で探索したうえで、それらのノーティブグラフデータベースである neo4j を用いて比較していドから出ているエッジを数え上げる必要がある。このようなクる [5] [6] [7]。彼らが使用したデータセットは LUBM ベンチー

エリを効率よく処理するために本研究では、グラフ探索部分にマークデータジェネレーターを用いて作られている [8]。このグラフデータベースを利用し、集合指向のクエリ処理部分に関ジェネレーターを使うことによってある複数大学における学生係データベースを利用する複合クエリ処理モデルを提案する。と教員の関係をグラフ構造で作成することができる。このジェ本論文では植田らのグラフモデルによる音楽推薦方式を例にネレータにより生成されたデータセット (LUBM-1) を利用して、次数数えあげなどを用いた統計的なクエリを七種類、パ探索に特化したネイティブグラフデータベースが適しているとターンマッチングのグラフ探索クエリを四類類評価している。

いえる。QP4 の実行結果では、グラフ探索の深さが浅い場合その中で、グラフ探索処理と集合指向処理の性能の差がわかる

は、RDBMS の方がクエリ処理時間が短い。しかし、グラフ探三つのクエリを紹介する。

索の深さが深くなるにつれて neo4j と RDBMS の速度の差は縮まっている。

QA1 :Node Degree

これらの実験結果から、全体的な集合指向処理は関係データQA1 はそれぞれのノード v ∈ V について、出方向のエッジベースが適していて、グラフ探索はグラフ構造がサイクルをと入方向のエッジの数の合計である次数を数え上げるクエリで含むかなどの複雑さ及びグラフ探索クエリの深さによって関係ある。

データベースとネイティブグラフデータベースどちらが適しているか変わることが分かる。サイクルを含み探索クエリの深さが深いほどネイティブグラフデータベースに適している。

QP2 :Cycles
QP2 は全グラフの中から図 1のようなサイクルをグラフ構造

2. 3 グラフモデルを用いた音楽推薦の中から見つけ出すクエリである。ここで li (i = 1 · · · n) はノ

植田らは，プレイリストに付随する楽曲、アーティスト、ユーードラベルを表しており、クエリ時にラベルの種類と数は指定

ザのコンテキスト情報をグラフを用いて表現し、ランダムウォーしている。

クを用いて各楽曲の期待値を計算し、期待値に基づき音楽を推薦する手法を提案した [9]。
以降、植田らが考慮した四種類のグラフのうち一つを説明し、その後ランダムウォークを適用した際の遷移確率の設定とノードの初期値の設定ついて述べる。
図1

グラフ構造のサイクル

2. 3. 1 RW-hybrid
RW-hybrid はプレイリストデータの持つ全ての関係情報をQP4 :Paths filtering on node labels and edge types

統合したグラフを利用する。ユーザのプレイリストの生成情報と、プレイリストからアーティストを介した遷移をどちらも取QP4 は図 2に示すように、指定したラベルが付加されているり入れることで、ユーザの好む楽曲とプレイリストと関係性のノードと指定したタイプのエッジのみからなるグラフを抽出す高い楽曲の期待値を高めるとともに、全てのコンテキスト情報るクエリである。の統合を目的としている。図 3 にそのグラフ例を示す。

図 2 ラベル付きノードとタイプ付きエッジ

2. 2. 1 実 験 結 果
実験では、PostgreSQL においてグラフ構造を保持するときのスキーマの違いで RDBMS A と RDBMS B に分けている。

RDBMS A ではグラフのエッジをタイプごとにテーブルに保存してあり、かつ、グラフのエッジ全タイプを保持するビューが存在する。それに対し、RDBMS B ではグラフのエッジをすべて同一のテーブルに保存しあり、かつ、グラフのエッジのタイ

図 3 RW − hybrid のグラフ例

プごとのビューが存在する。
次数数え上げの集合指向クエリである QA1 では、neo4j に比べ RDBMS B が 12 倍処理が速いという結果になっている 。こ2. 3. 2 ランダムウォークの遷移確率とノードの初期値
音楽グラフのランダムウォークにおける、各ノード (コンテのことにより、ネイティブグラフデータベースは関係データーキスト情報) から、連結するノード (異なる種類のコンテキスベースに比べて、ノード全体に対する集合指向処理は適していト情報) へのエッジの重み (遷移確率) の設定方法と各ノードのないことがわかる。QP2 の実行結果では、サイクルの大きさが小さい場合 neo4j が RDBMS B に比べ 1.9 倍処理が早い結果になっており、サイクルの大きさが大きい場合には最大で 1054倍処理が早くなっている。サイクルを含む複雑なグラフ探索の場合ネイティブグラフデータベースの方が処理が早く、グラフ初期値の設定について述べる。
あるノードから連結するノードへの遷移確率の合計値を 1 と設定する。コンテキスト情報の組合せごとの、遷移確率の設定方法を表 1 に掲載する。なお，あるコンテキスト情報のノードから複数種類のコンテキスト情報のノードに遷移を行う場合、

表 1 遷移確率の計算方法
遷移遷移確率楽曲⇒プレイリスト1楽曲が含まれるプレイリストの数
1
プレイリスト内の楽曲数

プレイリスト⇒楽曲
楽曲⇒アーティスト

1

アーティスト⇒楽曲楽曲の出現回数
アーティストの全楽曲の出現回数1
ユーザが生成したプレイリストの数

ユーザ⇒プレイリスト
プレイリスト⇒ユーザ

1

プレイリスト⇒アーティスト

プレイリスト内のアーティストの楽曲の数
プレイリストの楽曲数
1
アーティストが含まれるプレイリストの数

アーティスト⇒プレイリスト

利用する。提案手法概要を図 4 に示す。

あるノードからの遷移確率は 1 を超えることになる。具体的には、図 3 に示す通り、楽曲ノードからはプレイリストノードとアーティストノードへの遷移を行うため、遷移確率の合計値は2 となる。そこで、今回用いたグラフでは、ノードからの遷移
図 4 提案手法概要

確率の合計を 1 とするために、表 1 で計算した遷移スコアの値を接続するコンテキスト情報の種類数で割った値で補正する。
図 3 の楽曲ノードから他のノードへの遷移確率は表 1 に基づいて計算した値を 2 で割った値になる。

部分グラフ抽出GDB 上でユーザーの指定した条件を満たすノードとそれら次に、各ノードの初期値の設定方法について述べる．Hit rateにつながるノードから構成される部分グラフを抽出する。例えを用いたプレイリスト生成問題では、複数の楽曲を含んだ楽曲

ば、図 3 の音楽グラフにおいて、artist A に関する部分グラフ

リスト L を基に、L と関連すると考えられる楽曲の推薦を行っがクエリの条件だった場合、図 5 のような部分グラフが抽出さている [10]。そこで、グラフには楽曲リスト L 内の各楽曲のれ、表形式に変換して RDB に挿入する。

ノードに対して初期値 1 を与え、L の楽曲に基づいて関連する楽曲の探索を行う。
また、楽曲リスト L を生成したユーザのノードに対しても初期値として 1 を与えることで、同一ユーザの別のプレイリストの情報も考慮し、ユーザーの嗜好を取り入れた遷移を行うことを目指す。さらに、協調フィルタリングを利用してプレイリス
ト同士の類似度から楽曲の推薦を行う考え方を基に、楽曲リス
ト L と類似するプレイリストノードに対しても初期値として、類似度を与えている。これにより、プレイリストとアーティスト間の遷移によってプレイリストから関連すると考えられる楽曲への遷移の取り入れが期待できる。なお、その他のコンテキスト情報のノード、すなわち、アーティストノードには初期値として 0 を設定する。

3 提案手法3. 1 概要

先述の植田らのグラフモデルによる音楽推薦方式に対しユーザーが与える条件により部分グラフを抽出し、そのうえで音楽

図 5 ユーザーの条件により抽出した部分グラフ

初期値付与

RDB に保存された部分グラフテーブルとユーザーが作成した楽曲リスト L を利用して、植田らの初期値付与の手法に従いそれぞれのノードに初期値を与える。

推薦を行う場合の効率的な処理方法を提案する。ユーザーの与える条件より 2000 年代の女性の曲に関わる部分グラフを抽出し、そのうえで音楽推薦を実行するのは今回実行する処理の一例として挙げることができる。
この音楽推薦手法では、部分グラフ抽出、初期値付与、エッジ数カウント、期待値伝搬の 4 ステップに分けることができる。

エッジ数カウント

RDB に保存された部分グラフテーブルを利用して、それぞれのノードに対して出方向のエッジをエッジのタイプごとにカウントしてその値を保持する。これらの値は、期待値を計算するときに利用する。

ここで、部分グラフ抽出はグラフ探索処理であり、それ以外のステップはグラフ全体に対する集合指向処理であるため、部分グラフ抽出時のみにネイティブグラフデータベース (GDB) を利用し、それ以外のステップでは関係データベース (RDB) を期待値伝搬以上のステップで計算した値を利用し、植田らの手法に従い、各ノードの期待値を更新する。

3. 2 実装

エッジ数カウント

GDB に neo4j を RDB に PostgreSQL を用いることを仮定する。また、GDB の各ノードには固有の id が与えられているものとする。それぞれのステップにおいて生成されるテーブルとクエリの詳細を、抽出された部分グラフが図 6 となる場合を例にして述べる。図 6 におけるノードの数字はノードの id をエッジを数え上げた結果を新たなテーブルとして保存する。
例として、ユーザーがいくつプレイリストを作ったかを保持する user count playlist を表 5 に示す。
表5

ユーザーカウントプレイリストテーブル

user id playlist count示している。

12期待値伝搬以上で作ったテーブルを利用してノードテーブルの期待値を更新する。

4 評価実験
本節では、音楽グラフを用いた音楽推薦手法について、関係データベース単体、ネイティブグラフデータベース単体、提案手法の三つを実行した際の比較を行う。なお、実験に使ったマシンの構成を表 6 に示す。
図 6 抽出した部分グラフ

表 6 実験に使用したマシンの構成

CPUIntel Core i7-6700K (4.0GHz, 4 コア)

RAM 32GB部分グラフ抽出
部分グラフ抽出において、GDB 上で抽出した部分グラフをHDD

SEAGATE ST3000DM001(3TB)

OS

Ubuntu18.04

RDB に転送するときに、外部データラッパーを用いる方法が考えられるが、抽出した部分グラフを 1 行ずつ挿入していくとコストが大きいため、抽出した部分グラフは CSV ファイルを経由して COPY コマンドにより RDB にバルクロードした。
部分グラフは表 2 の形式で表現されている。

次に実験に使用したデータセットについて述べる。データセット作成は 30music [11] を参考にし、ノード数を 50 倍にすることで大規模な音楽グラフを作成した。表 7 にデータセットの詳細を示す。

表 2 部分グラフテーブル

user id playlist id track id artist id

表 7 データセットの詳細

1247

ユーザー数

5502001257

プレイリスト数1256950

1357

トラック数7547850

1367

アーティスト数

1491700

初期値付与
まず、はじめに部分グラフテーブルを用いることで、各ノード毎のテーブルと各隣接ノード間テーブルを作成する。その後、各ノードに植田らの手法に従い初期値を与える。

ユーザ当たりのプレイリスト数

3.28

プレイリスト当たりの楽曲数

18.5

アーティスト当たりの楽曲数

11.1

プレイリスト当たりのアーティスト数
総エッジ数40.492387791

ユーザーノードテーブルとユーザー-プレイリストテーブル
を例として表 3 と表 4 にそれぞれ示す。なお、user score old

上記のデータセットに対し、あるアーティスト群に限定しては推薦実行中における 1 つ前の期待値の状態を表しており、楽曲推薦を行う想定で部分グラフを抽出し、そのうえで推薦処

user score new は最新の期待値を表している。

理を実行する。このときアーティスト数を変えることによって抽出される部分グラフの大きさを調節することができる。抽出

表 3 ユーザーノードテーブル

された部分グラフの大きさに応じて、5 つのクエリを用意した。

user id user score10

表 8 にクエリの詳細を示す。

表 4 ユーザー-プレイリストテーブル
user id playlist id user score old user score new playlist score old playlist score new
1200001

30000表 8 クエリ詳細クエリ 4クエリ 5

選択ユーザー数

クエリ 1 クエリ 2 クエリ 35004505

46203

304457544422

選択プレイリスト数3463199

33404

295634 1150463

選択トラック数1131053

11032109846 1044194

選択アーティスト数

10100100010000100000

部分グラフファイルサイズ (MB)

0.02

0.15

1.60

17.0174

エッジ数130611975

126859 1214469 9382003

それぞれのクエリを 5 回ずつ実行し、クエリの実行時間の平均を算出した。また、それぞれのクエリの初めに PostgreSQLのキャッシュ、neo4j のキャッシュ、OS のファイルシステムの図 8 音楽推薦実行時間 (選択アーティスト数 10000〜10000)キャッシュはクリアした。その後、neo4j ではプラグインである

APOC を用いてキャッシュをウォームアップし、PostgreSQL

図 9 はグラフ探索処理である部分グラフ抽出ステップの実行

では pg prewarm を用いてキャッシュをウォームアップした。

時間について、RDB と GDB を比較して示している。また、同

図 7 と図 8 に音楽推薦処理に要した時間を示す。RDB+GDB

様に図 10 は集合指向処理であるエッジ数のカウント処理の実は提案手法を指し、RDB と GDB はそれぞれ単体での処理手行時間について示している。

法である。また、グラフのエラーバーは信頼区間 95%を示して

図 9 よりアーティスト選択数が 25000 を超えてから RDB にいる。アーティスト選択数が 10 の小規模な部分グラフの場合、おける実行時間が GDB における実行時間と比べて速くなって提案手法が関係データべース単体よりも 2 倍早く、ネイティブいることが分かる。アーティスト選択数が増えることで部分ググラフデータベース単体よりも 1.8 倍早くなっていることが分

ラフの大きさが大きくなり、部分グラフ抽出処理が集合指向処かる。アーティスト選択数が 1000 を超えるとネイティブグラ理に近くなる。そのため、部分グラフが大きい場合 GDB によフデータベースはエッジの数え上げのコストが原因で処理速度る部分グラフ抽出に大きなコストがかかってしまう。それに対が著しく低下する。そのため、アーティスト選択数が 1000 のし、RDB の実行時間は緩やかに上昇しているため、部分ぐフ

とき提案手法はネイティブグラフデータベース単体よりも 3.7

ラの大きさがより大きくなる場合は RDB の方が GDB と比べ倍早くなっている。また、アーティスト選択数が 1000 を超えてグラフ探索に適している。

るまでは関係データベース単体よりも提案手法の方が 1.7 倍以

図 10 よりアーティスト選択数が増えるにつれ、GDB にお上処理速度が速くなっているが、選択アーティスト数が 10000ける実行時間は急激に増加しているのが分かる。また、経路選のときには速度の差がほとんどなくなり、選択アーティスト数択数の大きさに関わらずエッジ数カウント処理においては常にが 100000 になると RDB の方が処理速度が速くなっているこ

RDB の方が実行時間が速いという結果になった。集合指向処とが分かる。これは抽出する部分グラフの大きさがが大きくな

理の場合は部分グラフの大きさに関わらず RDB を用いる方がるにつれて部分グラフ抽出において GDB よりも RDB の方が処理のコストは小さくなる。

優れていることを示している。

図 9 部分グラフ抽出実行時間
図 7 音楽推薦実行時間 (選択アーティスト数 10〜1000)

グラフ処理には適していないため、全グラフを複数のネイティ
ブグラフデータべースに分散させて保持させることで 1 つのネイティブデータベースあたりのグラフの大きさを小さくする方法が考えられる。

謝辞

本 研 究 の 一 部 は 、JSPS 科 研 費 (18H03242、18H03342、16H02908、17K12684)、JST ACT-I の助成を受けたもので
図 10 エッジ数カウント実行時間

次に、提案手法における部分グラフ抽出ステップにおける、GDB において抽出した部分グラフファイルの RDB へのバルクロードの時間的影響について述べる。図 11 に部分グラフ抽出ステップにおけるバルクロード時間の割合を示した図を示す。
アーティスト選択数が 100 のときが最も割合が小さく 2.9%となり、アーティスト選択数が 100000 のとき最も割合が大きく8.6%という結果になった。

図 11 バルクロードが部分グラフ抽出時間に占める割合

5 おわりに
本論文では、関係データべースとネイティブグラフデータベースを相互に活用することによってグラフモデルを用いた音楽推薦手法を効率的に処理する方法を提案した。実際に音楽グラフを用いた実験では、部分グラフの大きさが小さい場合において提案手法が関係データベースのみを使う場合より最大で 2倍速くなり、ネイティブグラフデータベースのみを使う場合より最大で 3.7 倍速くなった。しかし、部分グラフの大きさが大きいとネイティブグラフデータベースにおいて部分グラフ抽出処理に時間がかかり結果として関係データベースのみを用いた場合が一番早くなった。このことから提案手法は小さい部分グラフの場合には良い結果を示すが、部分グラフの大きさが大きくなると GDB における部分グラフ抽出は集合指向処理に近づき、処理コストが大きくなるため全体としてクエリ処理に時間的コストがかかることが分かった。
今後の課題は、抽出する部分グラフの大きさが大きいクエリに対しても効率的に処理を行える手法を考案することである。
例えば、ネイティブグラフデータベースが大規模な集合指向のある。ここに記して謝意を表す。

文

献[1] 渡 佑也, 欅 惇志, 宮崎 純, 中村 匡秀, RDB と KVS を相互に利用した多次元データに対する集約演算の効率化, DEIM 2016 論
文集, 2016.
[2] Avinash Lakshman, Prashant Malik, Cassandra - A Decentralized Structured Storage System, ACM SIGOPS Operating Systems Review, Volume 44, Issue 2, pp. 35-40, 2010.
[3] https://www.mongodb.com/document-databases[4] Ian Robinson, Jim Webber and Emil Eifrem, Graph
Database, Chapter 6, pp. 149-152, O’Reilly Media, Inc.,
2015.
[5] Jürgen Hölsch, Tobias Schmidt, and Michael Grossniklaus,
On the Performance of Analytical and Pattern Matching
Graph Queries in Neo4j and a Relational Database, Proceedings of the Workshops of the EDBT/ICDT 2017, 2017.
[6] https://www.postgresql.org/[7] https://neo4j.com/[8] Y. Guo, Z. Pan, and J. He, LUBM, A Benchmark for OWL
Knowledge Base Systems, J. Web Sem., 3(2-3), pp. 158-182,2005.
[9] 植田 聖司, 欅 惇志, 宮崎 純, プレイリスト生成における遷移確率を用いたスコアリング手法の提案, DEIM 2017 論文集, 2017.
[10] Negar Hariri, Bamshad Mobasher, and Robin Burke,
Context-aware music recommendation based on latenttopic
sequential patterns, Proceedings of the sixth ACM conference on Recommender Systems, pp. 131-138, ACM, 2012.
[11] Roberto Turrin, Massimo Quadrana, Andrea Condorelli,
Roberto Pagano, and Paolo Cremonesi, 30music listening
and playlists dataset, Poster Proceeding of ACM RecSys2015, 2015.