DEIM Forum 2019 D2-3

グラフの構造情報を用いた ObjectRank の高速化
佐藤 朋紀†

塩川 浩昭††

北川博之††† 筑波大学大学院システム情報工学研究科 〒 305–8573 茨城県つくば市天王台 1–1–1†† 筑波大学計算科学研究センター 〒 305–8577 茨城県つくば市天王台 1–1–1
E-mail: †t.sato@kde.cs.tsukuba.ac.jp, ††{shiokawa,kitagawa}@cs.tsukuba.ac.jp
あらましObjectRank は，データベース内のオブジェクトをグラフのノードとみなすことでキーワード検索を実現するグラフ分析手法である．しかしながら，ObjectRank は重要度評価の際にノード数に等しいサイズの行列ベク
トル積を繰り返し計算する必要があるため，大規模なグラフへの適用が難しいという問題がある．そこで本稿では，

ObjectRank の Top-k 検索の高速化手法を提案する．提案手法は，繰り返し計算の過程で各ノードの重要度の上限値と下限値を計算することで，解になり得ないノードをグラフから逐次的に枝刈りする．このとき，提案手法はグラフの構造情報を用いることで，枝刈りのさらなる高速化を図る．本稿では実データを用いた評価実験を行い，ObjectRankに対する提案手法の有効性を検証する．
キーワード ObjectRank，グラフマイニング
ObjectRank の重要度評価の高速化手法として，様々な手法

1 序論

ソーシャルメディアやモバイル機器の普及に伴い日々大量のデータが生成されており，データから新たに知識を獲得する
データ分析の需要が増加している．特に，データ間の関係性を表現するグラフと呼ばれるデータ構造に着目したグラフ分析
は，データ間の関係性に隠れた知識を獲得できる分析技術であり，推薦システムや SNS(Social Networking Service) といっが提案されてきた [4], [15], [16]．これらの手法は，グラフから
一部のノードを取り除くことで計算対象のノード数を削減した
り，効率的なクエリ応答のために索引を事前計算することで高速な計算を実現した．しかしながら，(1) 事前計算に膨大な時間を要する，(2) 大規模なグラフを対象とした場合に依然として計算時間を要するといった問題が存在する．

1. 1 本研究の貢献たサービスで幅広く用いられている [1], [9], [17]．

本研究では，ObjectRank の Top-k 検索を高速化する手法

グラフ分析技術のひとつに，ObjectRank [2], [10] がある．

を提案する．提案手法では，繰返し計算の各イテレーションに

ObjectRank は，PageRank [3] を拡張することでデータベー

おいて重要度の上限値と下限値を推定し，Top-k 検索の結果

ス内のオブジェクトに対するキーワード検索を実現する手法でになり得ないノードをグラフから逐次的に枝刈りする．このある．ObjectRank はデータベース内のオブジェクトをグラフ手法により重要度評価の繰返し計算を進めるにつれて計算対に見立てることによってランダムウォークに基づくリンク解析

象のノードが減少するため，従来の ObjectRank と比較して手法を適用し，各オブジェクトの重要度を評価しランク付けす

Top-k 検索を高速に行うことができる．提案手法はグラフからる．PageRank とは異なり，ObjectRank は複数の種類のノーノードの枝刈りを行うが，得られる上位 k 件のノードは従来のドとエッジからなるグラフを扱うことができるため，多様なObjectRank により得られる結果と一致することが保証される．

データに対して適用可能である [5], [8], [11], [14], [24]．

また，我々が行った予備実験により，提案手法は繰返し計算

ObjectRank は多様なアプリケーションに対して適用可能の序盤では枝刈りの上限を満たすノードが極めて少なく，ノーである一方で，計算コストが膨大であるという問題がある．

ド全体と比較して約 1 % のノードに対してのみ枝刈りが行わ

ObjectRank はクエリが与えられると全てのノードの重要度がれ，繰返し計算の終盤の数回で残りの大部分のノードが枝刈り収束するまで反復計算を行う必要があるため，大規模なグラフ

されることが明らかとなった．そこで提案手法は，グラフの構を用いた際に実用的な時間でクエリ応答することは困難であ

造情報に基づいてグラフの各タイプごとの重要度の分布を事前る．また，実世界における ObjectRank のアプリケーションでに導出し，よりタイトな上限値を設定することでさらなる高速

は，上位 k 件のノードのランキングのみが必要となる場合が化を図る．これにより，提案手法は繰返し計算の序盤において大多数であるが，従来の解法では全てのノードの重要度を導出もより多くのノードの枝刈りが可能となる．

して初めて上位 k 件のノードが得られる．一般的に k の値は多くとも数百程度であるのに対し，近年では数億を超えるノード数をもつグラフも存在するため，下位 N − k 件のノードの重要度評価が大きなボトルネックとなってしまう．したがって，

ObjectRank の高速化は重要な研究課題となっている．

本研究の貢献は下記の通りである．

•

高速性: 提案手法は従来のべき乗法を用いた ObjectRankと比較して上位 k 件の結果を高速に計算することができる．
提案手法は 100 万のノードと 500 万のエッジを持つグラフに対し，約 2 秒で検索結果を得ることができる（ 4. 1 節）．

表 1 本稿が用いる記号の定義
記号
G
V
E
N
M
A
d
rt
qt
BS(t)

•

定義
計算対象のグラフ
G に含まれるノードの集合
G に含まれるエッジの集合
グラフのノード数
グラフのエッジ数
N × N の遷移行列
ダンピングファクタ
キーワード t に対する各ノードの重要度を並べた N × 1 のベクトル
キーワード t についてのクエリベクトル
キーワード t をもつノードの集合

図 1 文献データベースの Schema Graph

正確性: 提案手法は ObjectRank の上位 k 件の結果を正確に導出することができる（ 4. 2 節）．
上述の通り，ObjectRank はすべてのノードの重要度が収束するまで反復計算を行う必要があるため，大規模グラフに適用

図 2 図 1 に基づいて作成された Data Graph の例

することは難しい．しかし，提案手法は逐次的なノードの枝刈りを行うことで計算対象のノード数を削減し，上位 k 件の結果れる．各エッジの重みはそのエッジによって遷移する重要度のを高速に得ることができる．実データを用いた評価実験では，割合を示す．ただし，重みは 0 以上 1 以下の値をとり，一つの従来のべき乗法を用いた ObjectRank と比較して約 5 倍高速ノードから出るエッジの重みの総和は 1 以下に設定する必要がに計算できることを示した．

ある．図 1 に文献データベースを表現した Schema Graph の

本稿の構成は次の通りである．まず， 2 節で前提となる知識例を示す．図 1 の例では，“Conference” や “Year” といったについて説明し， 3 節で提案手法について述べる． 4 節で評ラベルが付与された 4 種類のノードと，それらをつなぐ 8 種

価実験について説明し， 5 節で関連研究を紹介する．そして最類のエッジが存在する．

後に 6 節でまとめを述べる．

次に，Schema Graph に基づいて対象の全データを実体化したグラフ Authority Transfer Data Graph を構築する（以降，

2 前提知識：ObjectRank
本章では，本研究に関する基本事項について説明する．表1 に本稿が用いる記号とその定義を示す．以降では，2. 1 節でObjectRank の概要について，2. 1. 1 節でグラフの構築方法について，2. 1. 2 節で重要度評価の方法についてそれぞれ述べる．

2. 1 ObjectRank の概要

Data Graph と呼ぶ）．Data Graph の各ノードはデータベース内の 1 つのオブジェクトに対応し，オブジェクトに含まれるキーワード集合を保持する．Data Graph の各エッジの重みは，Schema Graph で定義した重みをエッジの元ノードの出次数で割った値となる．ただし，出自数は同じ種類のエッジの本数のみを数えたものとする．図 2 に 図 1 に基づいて作成された文献
データベースの Data Graph の例を示す．図 2 では，“Balmin,

ObjectRank [2], [10] は，PageRank [3] を拡張することで複A.” ノードから “ObjectRank” ノードには重みが 0.1 である

数種類のノードとエッジからなるグラフに対するキーワード検

エッジが張られている．これは，Schema Graph の “Author”

索を実現する手法である．具体的には，まずはじめに分析対象から “Paper” へのエッジの重みである 0.2 を，“Balmin, A.”のデータをグラフを用いて表現し，その後ユーザからクエリの出次数 2 で割った値である．

として与えられたキーワードに対する各ノードの重要度を計

2. 1. 2 重要度の計算方法

算しランキングを導出する．グラフを構築する際に，あらかじ

ObjectRank は，上述の方法により構築された Data Graph

め分析対象のデータベースに基づいてグラフを構成するノーに対して重要度評価を行う．ノードとエッジの集合をそれぞれ

ドとエッジのタイプを定義し，エッジのタイプごとに重みを割

V ，E ，ノード数とエッジ数をそれぞれ N ，M とする．あるり当てる．このとき，各エッジにはタイプに応じて異なる重み

キーワード t と Data Graph G = (V, E) が与えられたとき，を付与することが可能であるため，重要度評価の際にノード

ObjectRank はキーワード t に対する各ノードの重要度を並べ間の関係の差異を十分に捉えることができる．それに加えて，たベクトル rt = [rt (v1 ), rt (v2 ), . . . , rt (vN )] をランダムウォー

ObjectRank はクエリで与えられたキーワードに基づいて一部

クモデル [3] に基づいて計算する．すなわち，キーワード t をのノードの集合に対して重み付けを行うことによって，クエリ持つノード集合を BS(t) とすると，ランダムサーファは BS(t)に応じた検索結果を得ることができる．

に含まれるランダムなノードを始点として (1) エッジの重みに2. 1. 1 グラフの構築方法

応じた確率で隣接ノードへと遷移，または (2) BS(t) のランダ

ObjectRank はデータベース内のオブジェクトをラベル付き

ムなノードへとジャンプする行動を繰り返す．ある時点でラン有向グラフとして表現する．まず，グラフのノードとエッジの種

ダムサーファが滞在している確率を，そのノードの重要度と見類，及びエッジの重みを定義した Authority Transfer Schema

なす．これらの処理は以下の式 (1) で定式化することができる．

Graph を作成する（以降，Schema Graph と呼ぶ）．各種ノードとエッジはラベルが付与され，ラベルによって種類が区別さ

rt = dArt + (1 − d)qt(1)

ただし，A は N × N の遷移行列であり，(i, j) 要素にはノー

以降では， 3. 2 節で重要度の上限値と下限値の性質について

ド vj から vi にエッジ eji が存在する場合は eji の重みを，そ述べ， 3. 3 節で上限値と下限値を用いた提案手法の基本的なアれ以外の場合は 0 を格納する．d (0 < d < 1) はダンピング

ルゴリズムを説明する．そして 3. 4 節で Schema Graph に対ファクタ，qt は n 次元のクエリベクトルであり，ノード v がする ObjectRank の実行とその性質の議論を行い， 3. 5 節でv ∈ BS(t) を満たすとき qt (v) = 1/|BS(t)|，それ以外の場合グラフの構造情報を用いた提案手法のアルゴリズムを説明する．

は qt (v) = 0 となる．

ObjectRank は，べき乗法を用いて式 (1) を解く．すなわち，

3. 2 上限値と下限値
2. 1. 2 節で説明した通り，ObjectRank の重要度は式（2）を任意の初期値を与えて以下の式を繰り返し計算する．

用いた繰り返し演算によって計算される．つまり，あるノード
(i+1)

rt
(i)

rt

(i)

= dArt + (1 − d)qt

(2)

は i 回目の繰返し計算によって求めた重要度のベクトル(i)である．rtが収束したとき，繰返し計算を終了する．

3 提案手法3. 1 提案手法の概要(0)v について注目したとき，ノード v の重要度は初期値 rt (v)が各反復において増減し，ある値 rt (v) へと収束する．上限
(i)

(i)

値 rt (v) と下限値 rt (v) は，この収束値 rt (v) に対して(i)(i)
rt (v) <= rt (v) の性質を満たす値である．
= rt (v) <3. 2. 1 上限値と下限値の定義とその性質(i)pt

を長さ i のランダムウォークの確率を表す N 次元ベク(i)トルとする．pt= Ai qt で計算し，i = 0 のとき pi = e で前章で述べた通り，ObjectRank はノード数に比例したサイある．ただし，e は各要素が 1 である N 次元ベクトルとする．

ズの行列ベクトル積を繰り返し計算する必要があるため，グラ

このとき，i 番目の繰り返し計算における ObjectRank スコア

フが大規模化した際に計算コストが爆発的に増大するという問の下限値 r t

題がある．また，実世界における ObjectRank のアプリケー
ションでは，上位 k 件のノードのランキングのみが必要となる

(i)

(i)

と上限値 r tを以下に定義する．

定義 31 (下限値). i 番目の繰り返し計算におけるノード v の下限値は次のように計算する．

場合が大多数であるが，従来の解法では全てのノードの重要度が収束するまで繰り返し計算をして初めて上位 k 件のノード

r(i)t (v) = (1 − d)が得られる．一般的に k の値は多くとも数百程度であるのに対し，近年では数億を超えるノード数をもつグラフも存在するた
め，下位 N − k 件のノードの重要度評価が大きなボトルネッ

i
∑

(j)

dj pt (v)

(3)

j=0

定義 32 (上限値). i 番目の繰り返し計算におけるノード v の上限値は次のように計算する．

クとなってしまう．
そこで本研究では，重要度評価の際に逐次的にノードを枝刈(i)

rt (v) =(1 − d)

りすることで ObjectRank の Top-k 検索の高速化を図る．我々(i)+ di+1 pt (v) +可能であるという性質を発見した．そこで本研究では，この性質を利用して逐次的に上位 k 件の検索結果になり得ないノード(j)

dj pt (v)j=0

は，各イテレーションにおいて重要度の上限値と下限値が導出を枝刈りする手法を提案する．提案手法は，グラフの全ノード

i
∑

(i)

また，∆t

ノード数を著しく削減できるため，高速な処理が可能となる．

(4)は次のように計算する．


1
(i)
∆t = ∑
の重要度を繰り返し計算する従来の手法と比較して計算対象の

di+1 (i)∆ A(v)
1−d t

また，我々が行った予備実験により，上述の手法は繰り返し(i = 1)(i)u∈V0 ∆t (u)(otherwise)

計算の序盤では枝刈りの条件を満たすノードが極めて少ないた

ただし，Gi を i 番目の繰り返し計算における部分グラフ，G0

め全体のノードと比較して約 1 % のノードに対してのみ枝刈りを元のグラフとし，V0 は G0 のノード集合を表す．∆t (v)が行われ，繰り返し計算の終盤において残りの大部分のノード

(i)
(i)
(i−1)
は ∆t (v) = max{pt (v) − pt(v), 0} により計算する．Aが枝刈りされることが明らかとなった．そこで提案手法は，上はエッジの最大の重みを格納した N 次元ベクトルであり，述の上限値と下限値を用いた逐次的な枝刈りを行う際に，グラA(v) = max{A(v, u) : u ∈ Gi } となる．

フの構造情報を利用してさらなる高速化を図る．後述の補題 36
より，Schema Graph は Data Graph のエッジの重みやエッジの接続関係を定義したグラフであり，Schema Graph に対して(i)

補題 31 (下限値の性質). i 番目の繰り返し計算において，下(i)

限値 rt (v) は次の性質を満たす．

<
r(i)t (v) = rt (v)ObjectRank を実行することでノードのタイプごとの重要度の分布を導出できることが明らかとなった．SchemaRank はこの性質を利用して，Data Graph に対して Top-k 検索を行う
前に Schema Graph に対して ObjectRank を実行することでノードのタイプごとの重要度の分布を導出し，逐次的なノードの枝刈りの際に用いることで高速化を図る．

証明. 式 (2) より，

(5)

(i)

(i−1)

rt = dArt+ (1 − d)qt

Algorithm 1 Our basic proposed algorithm
Input: G, given graph; t, keyword; k, # of answer vertices
Output: Top-k vertices from final subgraph Gi+1
1: i ← 0
2: Gi ← G
3: repeat4:
for each v ∈ Gi do(i−2)= d A2 rt+ (1 − d)(dAqt + qt )2

(0)

+ (1 − d){di−1 Ai−1 qt + · · · + qt }(0)

+ (1 − d)= di Ai rt= di Ai rt

i−1
∑

(j)

dj pt

j=0
(i)

最終的な ObjectRank のスコアベクトルは rt(∞)

るため，rt = rtの収束値であとなる．0 < d < 1 かつ A∞ の各要素は 0

以上 1 以下の値をとるため，

rt =d∞ A∞ rt +(1 − d)
(0)

∞
∑

(j)

dj pt =(1 − d)

j=0

∞
∑

(j)

dj pt

j=0

(6)

(i)

5:
6:
7:
8:

(i)

calculate r t (v) and r t (v) by equation (9) and (10)end forϵi ← the k-th largest lower bound in Gi(i)construct Gi+1 by pruning vertices s.t {v ∈ Vi : r t (v) < ϵi } from
Gi

9:
i←i+1
10: until |Vi+1 | = k
11: return Vi+1
qt (v)+ d A(v)(i = 0)(i)
1−drt (v)=
r(i−1) +di p(i) (v)+ di+1 ∆(i) A(v) (i =
| 0)
t

t

t

1−d

が成り立つ．したがって，

rt = (1 − d)

∞
∑

(10)
(j)

dj pt

>
= (1 − d)

j=0

i
∑

(i)

(j)

dj pt

(7)

j=0

(i)

d
また，定義 32 より rt (v) = (1−d)qt (v)+dqt (v)+ (1−d)A(v) =

が成り立つため，補題 31 の式 (5) が成立する．
補題 32 (上限値の性質). i 番目の繰り返し計算において，上(i)

限値 rt (v) は次の性質を満たす．

(i)

(8)

(i)

補題 33 (上限値と下限値の収束性). 上限値 rt(i)と下限値 rtは最終的に従来の ObjectRank によって得られる重要度の収束(∞)(v) = rt (v) = rt

(v) を

満たす．
(∞)

式 (31) より rt(v) = (1 − d)

(i)

(i−1)

(1 − d)di pt (v) となり，rt (v) = rt

(v) =
(i)

+ (1 − d)di pt (v)(i)

また，上限値と下限値は繰り返し計算を進めると最終的に重

証明.

(i−1)

(i−1)

が成り立つ．また，定義 31，32 より rt (v) − rt

要度の収束値に一致することが保証される．

(∞)

定数であるため，式 (9)，(10) は O(1) で計算可能である．
(i)

スペースの都合により省略する．

値 rt (v) に一致する．すなわち，rtdqt (v) + (1−d)A(v) が成り立つ．このとき，d，qt (v)，A(v) は次に，i =| 0 のとき，定義 31 より rt (v) − rt(i)rt (v) >= rt (v)証明.

証明. i = 0 の と き ，定 義 31 よ り rt (v) = (1 −
∑
(j)
(0)
d) ij=0 dj pt (v) = (1 − d)pt (v) = (1 − d)qt (v) が成り立つ．

(v) =

(i)
(i)
(i)
(i−1)
di+1
di pt (v) + (1−d)∆t A(v) と な り，rt (v) = rt
(v) +
(i)
(i−1)
i (i)
di+1
d pt (v) + (1−d) ∆t A(v) が成り立つ．rt(v) はあらかじめ(i)
計算されており，d，pt (v)，A(v) は定数であるため，式 (9)，(10) は O(1) で計算できる．
3. 3 基本的なアルゴリズム
上限値と下限値を用いた提案手法の基本的なアルゴリズムを

Algorithm 1 に示す．i (i = 0, 1, . . . ) 番目の繰り返し計算にお

∑∞

j (j)
j=0 d pt (v) となる(∞)
ため，明らかに rt (v) = rt (v) が成り立つ．式 (32) より
∑
(i)
(∞)
j (j)
∞ (∞)
d∞
rt (v) = (1 − d) ∞(v) + 1−d∆t A(v)
j=0 d pt (v) + d pt(∞)
となる．ここで，0 < d < 1 かつ 0 <= pt (v) <= 1 である(∞)∞ (∞)<
ため，d pt (v) = 0 となる．同様に，0 <∆= t= 1 かつ(∞)
d∞<<0 = A(v) = 1 であるため，1−d ∆t A(v) = 0 とある．ゆえに，
∑
(∞)
(∞)
j (j)
rt (v) = (1−d) ∞(v)
j=0 d pt (v) となるため，rt (v) = r t(∞)(∞)
が成り立つ．したがって，rt (v) = rt (v) = rt (v) が成り

(i)

(i)

いて，各ノードの重要度の上限値 rt (v)，下限値 rt (v) を計算する（5 行目）．閾値 ϵi を i 番目の繰り返し計算におけるk 番目に大きい下限値とする（7 行目）．このとき，上限値がϵi を下回ったノードをグラフ Gi から取り除き，新たな部分グ
ラフ Gi+1 を構築する（8 行目）．Gi+1 に含まれるノード数|Vi+1 | が k に達したとき計算を終了し，k 件のノードを返す．
Algorithm 1 が従来の ObjectRank と同様の結果が得られることを示すために，以下の補題を導入する．

立つ．
補題 35 (アルゴリズムの正確性). 提案手法は，従来の Objec(i)重要度評価の際の繰り返し計算において，下限値 r t
(i)

値 rt

と上限

は次のように逐次的に計算することができる．

tRank によって得られる上位 k 件のノードを正確に検索することができる．

補題 34 (下限値と上限値の逐次的な計算). i 番目の繰り返し証明. 従来の ObjectRank によって計算される重要度の収束(i)(i)
計算において，下限値 rt (v) と上限値 rt (v) は次式で計算す(i)る．また，次式は pt (v) が計算済みであるとき O(1) で計算

値の k 番目に大きな値を ϵ とする．すなわち，あるノード v

可能である．

は必ず ϵ <= rt (v) を満たす．i 番目の繰り返し計算における kr(i)t (v) =

(1 − d)qt (v)(i = 0)r(i−1) + (1 − d)di p(i) (v)
t

t

(i =
| 0)

が上位 k 件の検索結果に含まれるとき，重要度の収束値 rt (v)番目に大きな下限値を ϵi とすると，補題 31 より ϵi <
= ϵ が

(9)

(i)

成り立つ．提案手法は rt (u) < ϵi を満たすようなノード uをグラフから枝刈りするが，補題 32 よりノード u について

3. 4. 1 Schema Graph と Data Graph の重要度の分布

Algorithm 2 ObjectRank on Schema Graph
Input: GS , Schema Graph; t, keyword; τ , maximum # of iterations
Output: ObjectRank scores of all vertices in VS(0)
Initialize rS,t by Equation (11)Set query vector qS,t by Equation (12)1:2:
3: i ← 0
4: while i < τ do(i)
5:
Calculate rS,t by Equation (13)6:
if All of ObjectRank scores converges then7:
Stop algorithm
8:
end if
9:i←i+1
10: end while

Algorithm 2 によって得られた重要度 rS,t について，以下の補題が成り立つ．
補題 36 (Schema Graph と Data Graph の重要度の分布).

Algorithm 2 によって得られた重要度 rS,t と，この Schema
Graph から作成された Data Graph に ObjectRank を実行して得られる重要度 rt には，任意のタイプ λi ∈ Λ について以下の関係が成り立つ．

rS,t (vλi ) =(i)rt (u) <= rt (u) < ϵ が成り立つ．これは検索結果に含まれる場合の条件 ϵ <= rt (v) に矛盾するため，提案手法は上位 k 件になり得ないノードを必ず枝刈りする．

∑

rt (v).

(14)v∈V (λi )ただし，V (λi ) はタイプが λi である Data Graph のノードの集合である．

3. 4 Schema Graph に対する ObjectRank(0)

Algorithm 2 に Schema Graph GS = (VS , ES ) に対して
ObjectRank を実行する際のアルゴリズムを示す．Schema
Graph に対する ObjectRank は (1) 重要度のベクトル rS,t の証明. 3. 4 節で述べた通り，rS,t (vλi ) の初期値は rS,t (vλi ) =Nλi /N である．このとき，Data Graph の任意のノード v ∈ V(0)の初期値 rt (v) は 1/N であるため

(0)

(0)

rS,t (vλi ) = Nλi ×

初期値 rS,t の設定方法および (2) クエリベクトル qS,t の作成方法を除き，Data Graph に対する通常の ObjectRank と同様
に行う．

1
=
N

∑

(0)

rt (v)(15)v∈V (λi )が成り立ち，rS,t の初期値と rt の初期値について，式 (14) が重要度の初期値:

Schema Graph のノードタイプ λi の集合成り立つ．

を Λ = {λ1 , λ2 , . . . , λNS } とする．ただし，NS はノードのタ

以降のイテレーションでは (1) 隣接ノード間での重要度の遷

イプの総数，つまり，Schema Graph のノード数である．この移および (2) ランダムジャンプによる重要度の遷移によって各とき，タイプが λi である Schema Graph のノード vλi の重

ノードの重要度が増減するが，各イテレーションにおいて必ず要度の初期値は

式 (14) が成り立つことを証明する．
(0)

rS,t (vλi ) =

Nλi
N

(11)

Data Graph の任意のノード v ∈ V について，v の隣接ノードの集合を Out(v)，Out(v) においてタイプが λi であるノーとする．ただし，N および Nλi はそれぞれ Data Graph のドの集合を Outλi (v) とする．Schema Graph において，タイ

ノード数，タイプが λi である Data Graph のノードの総数でプ λ(v) のノードがエッジを張っているノードのタイプの集合∪を Λv とすると，Out(v) = λi ∈Λv Outλi (v) が成り立つ．Λv

ある．
クエリベクトルの作成:

タイプが λi である Schema Graphと張られるエッジの重みの総和は，Schema Graph におけるのノード vλi について，クエリベクトルの値は|BSλi (t)|qS,t (vλi ) =|BS(t)|の各タイプ λi ∈ Λv について，v から Outλi (v) のノードへ

λ(v) から λi へのエッジの重みに一致する．つまり，v から(12)とする．ただし，|BSλi (t)| はタイプが λi である Data Graphのノードのうち，キーワード t をもつノードの総数を表す．
上述の通り重要度の初期値とクエリベクトルを作成し た と き ，Schema Graph の 各 ノ ー ド の 重 要 度 rS,t =(rS,t (v1 ), rS,t (v2 ), . . . , rS,t (vNS )) は以下の式 (13) を重要度

Outλi (v) の各ノードへと重要度が遷移する確率の総和を α とすると，Schema Graph において λ(v) から λi へと重要度が遷移する確率は α に一致する．また，各イテレーションおいて Data Graph と Schema Graph のタイプごとの重要度の総∑和が一致しているため， v∈V (λ(v)) rt (v) = rS,t (λ(v)) が成り立つ．したがって，∑のベクトル rS,t が収束するまで繰り返し計算することで得ら

α × rt (v) = αv∈V (λ(v))

れる．
(i)

(i−1)

rS,t = dAS rS,t

+ (1 − d)qS,t .

∑rt (v) = α × rS,t (λ(v))

v∈Outλ(v)が成り立つ．すなわち，ある 2 つのタイプ λ1 , λ2 (∈ Λ) につい(13)て，Data Graph の V (λ1 ) のノードから V (λ2 ) のノードへとこのとき，AS は Schema Graph GS の遷移行列であり，(i, j)

遷移する重要度の総和は，Schema Graph においてノード vλ1

要素にはノード vj (∈ VS ) から vi (∈ VS ) にエッジ eji (∈ ES )から vλ2 へと遷移する重要度の値は一致する．

が存在する場合は eji の重み α(eij ) を，それ以外の場合は 0を格納する．

式 (12) より，Schema Graph に対する ObjectRank のクエリ
ベクトルは，qS,t (vλi ) =|BSλ (t)|i|BS(t)|

である．ただし，|BSλi (t)|はタイプが λi である Data Graph のノードのうち，キー
ワード t をもつノードの総数である．Data Graph の任意のAlgorithm 3 Proposed algorithm using schema information(i)(i)
更する．0 <
= pt <= 1 かつ pt は単調減少するため，以下の補Input: G, Data Graph; GS , Schema Graph; t, keyword; k, # of answer
vertices
Output: Top-k vertices from final subgraph Gi+1
1: // Running ObjectRank on Schema Graph GS
2: Run Algorithm 2 to get rS,t

題が成り立つ．

3:
4: i ← 0
5: Gi ← G
6: repeat7:
for each v ∈ Gi do
(i)
(i)
8:
Calculate r t (v) and r t (v) by Equation (9) and (10)9:end for10:ϵi ← the k-th largest lower bound in Gi(i)11:
Construct Gi+1 by pruning vertices s.t. {v ∈ Vi : r t (v) < ϵi }補題 38 (グラフの構造情報を用いた重要度の上限値). ノード(i)v のグラフの構造情報を用いた上限値 rS,t (v) は，グラフの構(i)

造情報を用いない上限値 rt (v) に対して以下の式が成り立つ．
(i)

(i)

rS,t (v) <= rt (v)(17)

証明. スペースの都合により省略する．

from Gi

Algorithm 3 にグラフの構造情報を用いた提案手法のアルゴ

12:
i←i+1
13: until |Vi+1 | = k
14: return Vi+1

リズムを示す．提案手法はまずはじめに Alrorithm 2 を呼び出し，Schema Graph の重要度のベクトル rS,t を取得する（2行目）．Schema Graph のノード数はたかだか数ノード程度でノード v について，ノード v が v ∈ BS(t) を満たすときあるので，非常に高速に動作する．以降の流れは Algorithm 1

qt (v) = 1/|BS(t)|，それ以外の場合は qt (v) = 0 であるため，と同様であるが，上限値の計算には Schema Graph の重要度

Λ の各タイプ λi ∈ Λ について

rS,t を用いる (8 行目）．上位 k 件のノードが得られたとき，∑

qt (v) = |BSλi (t)| ×v∈BSλ (t)|BSλi (t)|1=
= qS,t (vλi )|BS(t)||BS(t)|iが成り立つ．したがって，各イテレーションにおいて Data

計算を終了する．

4 評価実験

Graph のタイプごとのクエリベクトルの値の総和は，Schema

本節では，提案手法，従来の ObjectRank および既存手法のGraph のクエリベクトルの対応するタイプの値に一致する．

BinRank [15] を実行し，効率性と検索結果上位 k 件の近似精以上より，各イテレーションにおいて式 (14) が成り立つた度の観点で提案手法の有効性を検証する．

•

め，補題 36 は成り立つ．

提案手法: Algorithm 1 に示した上限値と下限値を用いた提案手法の基本的なアルゴリズム，および Algorithm 3 に

補題 36 より，Data Graph の重要度 rt について，以下の性示したグラフの構造情報を用いた提案手法．簡単のため，質が成り立つ．

図中ではそれぞれ “Basic”，“Schema” と表記する．

補題 37 (Schema Graph と Data Graph の重要度). Data•

ObjectRank: べき乗法を用いた従来の計算方法 [2]．

Graph の任意のノード v ∈ V について，v の重要度 rt (v)•BinRank: 全体のグラフと比較してノード数の少ない部分

は，タイプが λ(v) である Schema Graph のノードの重要度

グラフを構築することで高速化を図る手法 [15]．BinRankrS,t (λ(v) 以下の値をとる．したがって，以下の式が成り立つ．

は，データベースに含まれるキーワードをクラスタリング
し，クラスタに含まれるキーワードとの関連度が著しく低rt (v) <= rS,t (λ(v))(16)

いノードを取り除いた部分グラフを，クラスタごとに構築∑
証明. 補題 36 より， v∈V (λ(v)) rt (v) = rS,t (λ(v)) である

し索引に格納する．クエリ処理時には，クエリキーワードを含むクラスタから作成された部分グラフのみを対象に，ため，

rt (v) = rS,t (λ(v)) −∑べき乗法による重要度評価を行う．

rt (u)u∈V (λ(v))∧u=v|

データセットは以下の 2 種類のグラフを用いた．

•

MOVIE: Wikipedia に記載された情報を構造化したデーが成り立つ．このとき，rt (u) は 0 以上 1 以下の値をとるため，タベースである YAGO [18] から，映画とその主役，監督

式 (17) は成り立つ．

に関する情報を抽出したサブセット [12], [13]．ノード数とエッジ数はそれぞれ 173,158，799,322 である．

3. 5 グラフの構造情報を用いた提案手法のアルゴリズム•

DBLP: AMiner (http://aminer.org) が公開している，

補題 36， 38 に示した性質より，Data Graph のノード v の論文とその著者，発表年，学会といった文献に関するデータイプ λ(v) に応じて Schema Graph の重要度 rS,t (λ(v)) を

タベース [23], [20], [19]．ノード数とエッジ数はそれぞれ用いることで，よりタイトな上限値を設定することが可能とな

1,238,266，5,149,294 である．

る．提案手法は，この性質を利用することにより Alrorithm 1

MOVIE の Schema Graph は図 7 に示したものを使用する．

で示した基本的なアルゴリズムの繰り返し計算の序盤で枝刈り

DBLP の Schema Graph は図 1 に示した文献 [2] と同様のが行われにくいというボトルネックを解消する．

ものを使用した．ダンピングファクタ d は文献 [2] と同様提案手法では，上限値に用いられる長さ i の遷移確率のベク
(i)

トル pt

の初期値を Schema Graph の重要度 rS,t (λ(v)) に変に d = 0.85 とした．プログラムは C++ で実装し，計算機は3.5GHz CPU，メモリが 128GB の Linux サーバを用いた．

図 3 実行時間（DBLP）

図 4 実行時間（MOVIE）

図 5 BinRank の事前計算（DBLP）

図6 近似精度

結果を図 6 に示す．実験結果より，提案手法は ObjectRankと全く同一の結果が得られることが示された．提案手法は重要度の上限値と下限値を推定することで上位 k 件になり得ないノードを正確に発見することができるためである．一方，BinRank
図 7 YAGO データセットの Schema Graphは事前計算に膨大な時間を要するのにも関わらず，導出される結果は近似解となることが示された．

4. 1 効 率 性
上述の 4 つの手法をそれぞれ実行した際の実行時間を評価

5 関連研究する．ただし，提案手法は Algorithm 1 に示した上限値下限

PageRank や ObjectRank といったランダムウォークモデル

値を用いた基本的なアルゴリズム（“Basic” と表記する）とに基づくグラフ分析技術の研究が近年盛んに行われている．既

Algorithm 3 に示したグラフの構造情報を用いたアルゴリズ

存手法は (1) ノードの枝刈りに基づく手法と (2) 索引を用いた

ム（“Schema” と表記する）をそれぞれ実行した．図 3 と図 4

手法の 2 つに分けることができる．

に，DBLP と MOVIE データセットに対して実行した際の実ノードの枝刈りに基づく手法: これらの手法は，グラフから不行時間をそれぞれ示す．実験結果より，逐次枝刈りによる提案

必要なノードや他のノードの重要度に与える影響が少ないノー

手法（Basic）は従来のべき乗法を用いた ObjectRank と比較ドを推定し，枝刈りすることで高速化を図る．Sakakura [16] らして，約 5 倍程度高速であることが示された．ObjectRank はは，グラフ全体ではなく局所的なグラフを構築することで重要すべてのノードの重要度が収束するまで繰り返し計算を行う必度を推定する手法を提案した．ObjectRank はエッジごとに異要があるが，提案手法は解になり得ないノードを逐次的に枝刈なる重みをもち，重みが小さいエッジをもつノードは他のノーりし上位 k 件のノードが得られた時点で計算を終了するため，

ドへと与える影響も小さい．Sakakura らの手法は，エッジの高速な計算が可能となる．グラフの構造情報を用いた提案手法

重みを考慮することで重要度推定に与える影響の小さいノード（Schema）は，全ての手法の中で最も高速であることが示されを推定し，グラフから枝刈りすることで高速な重要度推定を実た．この結果より，Schema Graph に対する ObjectRank の現した．Fujiwara [7] らは，繰り返し計算の過程で解になり得重要度を用いることで，上限値をよりタイトに設定することがないノードを逐次的に枝刈りし，PageRank の Top-k 検索をできたことがわかる．

高速化する手法 F-Rank を提案した．F-Rank では，繰り返し

図 5 は DBLP データセットに対する BinRank の事前計算

計算の各ステップにおいて各ノードの重要度の上限値と下限値

部の実行時間を示している．maxBinSize はクラスタサイズの推定値を用いて解になり得ないノードを特定し，グラフからを制御する内部パラメータであり，maxBinSize が大きくなる

枝刈りする．グラフからノードの枝刈りを行うが，検索結果はほどクラスタの数が減少し，索引に格納される部分グラフの数

理論的に正しいことが保障されている．しかし，F-Rank は遷も減少する．実験結果より，BinRank は 10 時間以上もの事前

移行列の列が正規化される PageRank の特性を利用している計算を要することが示された．

ため，ObjectRank には適用できない．

4. 2 近 似 精 度
ObjectRank によって得られた結果を真値とし，提案手法とBinRank の近似精度を計測した．近似精度の指標は以下の式を用いた．

|CompSet(t, k) ∩ ORSet(t, k)|
P rec(t, k) =. (18)
k

索引を用いた手法: クエリ応答の効率化のために，Chakrabartiら，Hwang らは索引を用いて高速化を図る手法 HubRank [4]，BinRank [15] をそれぞれ提案した．これらの手法は索引を事前に構築し，クエリ処理時には索引を参照することで検索結果を近似することでクエリ処理時間を短縮する．HubRank は，hub
ノードと呼ばれるクエリログに基づいて選択された一部のノードの random walk fingerprints [6] を事前計算し索引付けする．

ただし，CompSet(t, k) はキーワード t に対して提案手法またクエリ処理時には，クエリキーワードを含むノードから幅優先

は BinRank を，ORSet(t, k) は ObjectRank をそれぞれ実行

探索を開始し，hub ノードに到達するかクエリノードから一定した場合に得られた上位 k のノードの集合を表す．

の距離が離れた時点で探索をやめ，得られた部分グラフについて索引に基づいた重要度推定を行う．BinRank は，データベースに含まれるキーワードをクラスタリングし，クラスタに含まれるキーワードとの関連度が著しく低いノードを取り除いた部
分グラフを，クラスタごとに構築し索引に格納する．クエリ処
理時には，クエリキーワードを含むクラスタから作成された部
分グラフのみを対象に，べき乗法による重要度評価を行う．
しかし，これらの手法は索引構築に膨大な時間を要するだけ
でなく，クエリ応答時にも重要度推定のための計算を行う必要があるという問題がある．我々が行った評価実験では，BinRank
は文献データベースの索引構築に 10 時間以上かかることが示された（図 5）．
既存手法とは異なり，我々の提案手法は大規模なグラフを対象とした場合でも高速な Top-k 検索が可能である．我々が行った評価実験により，提案手法は事前計算を行わずに従来のObjectRank と同様の結果を得ることが可能であり，BinRank
より高速に結果を得られることが示された．

6 結論

本稿では ObjectRank の Top-k 検索の高速化手法を提案した．提案手法では，繰り返し計算の過程で各ノードの重要度の取り得る上限値と下限値を推定することで，上位 k 件になり得ないノードをグラフから逐次的に枝刈りする．この手法により重要度評価の繰り返し計算を進めるにつれてノードが減少するため，従来の ObjectRank と比較して Top-k 検索を高速に行うことができる．また，提案手法はグラフの構造を定義する

Schema Graph に対して ObjectRank を実行することで，より高速な枝刈りを実現する．実データを用いた評価実験では，提案手法は従来のべき乗法を用いた ObectRank および既存手法である BinRank と比較して高速に検索結果が得られることを示した．
今後の課題として，複数キーワードによるクエリ応答への対応が挙げられる．従来の ObjectRank では，クエリとして複数のキーワードが与えられた場合，各キーワードについてそれ
ぞれ重要度を計算し，それらの積や和を計算することによって最終的なランキングを決定する．我々の提案手法では，各キー
ワードについて上位 k 件が完全に独立して導出されるため，それぞれのランキング結果を複合することができないという問題がある．今後は，複数のキーワードからなるクエリに対する，重要度の上限値と下限値を用いた逐次的ノード枝刈り手法の検
討を行う．

謝

辞

本 研 究 の 一 部 は JSPS 科研費 JP18K18057 な ら び に

JST ACT-I の助成を受けたものである．
文

献[1] Bahman Bahmani, Abdur Chowdhury, and Ashish Goel.
Fast Incremental and Personalized PageRank. Proc. VLDB,
Vol. 4, No. 3, pp. 173–184, 2010.
[2] Andrey Balmin, Vagelis Hristidis, and Yannis Papakonstantinou. ObjectRank: Authority-Based Keyword Searchin Databases. In Proc. VLDB, pp. 564–575, 2004.
[3] Sergey Brin and Lawrence Page. The Anatomy of a LargeScale Hypertextual Web Search Engine. In Proc. WWW,
pp. 107–117, 1998.
[4] Soumen Chakrabarti. Dynamic Personalized Pagerank in
Entity-Relation Graphs. In Proc. WWW, pp. 571–580,
2007.
[5] Paul-Alexandru Chirita, Stefania Costache, Wolfgang Nejdl, and Raluca Paiu. Beagle + + : Semantically Enhanced
Searching and Ranking on the Desktop. In Proc. ESWC,
pp. 348–362, 2006.
[6] Dániel Fogaras, Balázs Rácz, Károly Csalogány, and Tamás
Sarlós. Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments. Internet Mathematics, Vol. 2, No. 3, pp. 333–358, 2005.
[7] Yasuhiro Fujiwara, Makoto Nakatsuji, Hiroaki Shiokawa,Takeshi Mishima, and Makoto Onizuka. Fast and Exact
Top-k Algorithm for PageRank. In Proc. AAAI, pp. 1106–
1112, 2013.
[8] Stefania Ghita, Wolfgang Nejdl, and Raluca Paiu. Semantically Rich Recommendations in Social Networks for Sharing, Exchanging and Ranking Semantic Context. In Proc.
ISWC, pp. 293–307, 2005.
[9] Marco Gori and Augusto Pucci. ItemRank: A RandomWalk Based Scoring Algorithm for Recommender Engines.
In Proc. IJCAI, pp. 2766–2771, 2007.
[10] Vagelis Hristidis, Heasoo Hwang, and Yannis Papakonstantinou. Authority-Based Keyword Search in Databases.
ACM Trans. Database Syst., Vol. 33, No. 1, 2008.
[11] Vagelis Hristidis, Yao Wu, and Louoiqa Raschid. Eﬃcient
Ranking on Entity Graphs with Personalized Relationships.
TKDE, Vol. 26, No. 4, pp. 850–863, April 2014.
[12] Zhipeng Huang and Nikos Mamoulis. Heterogeneous Information Network Embedding for Meta Path based Proximity. CoRR, Vol. abs/1701.05291, , 2017.
[13] Zhipeng Huang, Yudian Zheng, Reynold Cheng, Yizhou
Sun, Nikos Mamoulis, and Xiang Li. Meta Structure: Computing Relevance in Large Heterogeneous Information Networks. In Proc. KDD, pp. 1595–1604, 2016.
[14] Heasoo Hwang, Andrey Balmin, Hamid Pirahesh, andBerthold Reinwald. Information Discovery in Loosely Integrated Data. In Proc. SIGMOD, pp. 1147–1149, 2007.
[15] Heasoo Hwang, Andrey Balmin, Berthold Reinwald, andErik Nijkamp. BinRank: Scaling Dynamic Authority-Based
Search Using Materialized SubGraphs. In Proc. ICDE, pp.
66–77, 2009.
[16] Yuta Sakakura, Yuto Yamaguchi, Toshiyuki Amagasa, andHiroyuki Kitagawa. A local method for objectrank estimation. In Proc. IIWAS, p. 92. ACM, 2013.
[17] Satu Elisa Schaeﬀer. Graph Clustering. Computer Science
Review, Vol. 1, No. 1, pp. 27–64, 2007.
[18] Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum.
Yago: a core of semantic knowledge. In Proc. WWW, pp.
697–706. ACM, 2007.
[19] Jie Tang, Alvis C. M. Fong, Bo Wang, and Jing Zhang. A
Unified Probabilistic Framework for Name Disambiguationin Digital Library. TKDE, Vol. 24, No. 6, pp. 975–987, June
2012.
[20] Jie Tang, Limin Yao, Duo Zhang, and Jing Zhang. A Combination Approach to Web User Profiling. TKDD, Vol. 5,
No. 1, pp. 2:1–2:44, December 2010.
[21] Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, andZhong Su. Arnetminer: Extraction and mining of academic
social networks. In Proc. KDD, 2008.
[22] Yuto Yamaguchi, Tsubasa Takahashi, Toshiyuki Amagasa,and Hiroyuki Kitagawa. TURank: Twitter User Ranking
Based on User-Tweet Graph Analysis. In Proc. WISE, pp.
240–253, 2010.