DEIM Forum 2017 C8-1

大規模グラフに対する ObjectRank の高速化
佐藤朋紀†

塩川 浩昭††

山口祐人†††

北川 博之††† 筑波大学情報学群情報科学類 〒 305–8573 茨城県つくば市天王台 1–1–1†† 筑波大学計算科学研究センター 〒 305–8577 茨城県つくば市天王台 1–1–1††† 国立研究開発法人産業技術総合研究所 〒 135–0064 東京都江東区青海 2–3–26
E-mail: †t.sato@kde.cs.tsukuba.ac.jp, ††{shiokawa,kitagawa}@cs.tsukuba.ac.jp,†††yamaguchi.yuto@aist.go.jp
あらましObjectRank はデータベース内のオブジェクトをグラフのノードとみなすことで，キーワード検索を実現するグラフ分析手法である．ObjectRank は複数種類のノードとエッジからなるグラフを扱うことができるため，多様なデータに対して適用することができる．しかしながら，ObjectRank はデータベース内に現れる全てのキーワードに対して各ノードが持つ重要度を繰り返し計算する必要があるため，大規模なグラフへの適用が難しいという問題がある．そこで本稿では，ObjectRank の高速化手法を提案する．提案手法では，計算対象のノード数を削減することで ObjectRank の高速化を図る．具体的には，重要度の計算過程において重要度の著しく低いノードを逐次的にグ
ラフから枝刈りすることでノード数を削減する．提案手法は，計算過程で各ノードの重要度の取り得る上限値と下限値を計算することによって枝刈りをした場合に検索結果に与える影響が小さいノードを特定する．本稿では実データを用いた評価実験を行い，ObjectRank に対する提案手法の有効性を評価する．
キーワード

1. 序

ObjectRank，グラフマイニング，情報検索論

演算の繰り返し回数を T とすると，重要度評価の計算量はO((N + M )T ) となる．ゆえに，ノード数が大きいときクエリ

ソーシャルメディアやモバイル機器の普及に伴い日々大量の応答時間は増加する．一般的に，ObjectRank は応答時間の高データが生成されており，データから新たに知識を獲得する

速化のために，事前にデータベース内に現れる全てのキーワー

データ分析の需要が増加している．特に，データ間の関係性をドに対して各ノードの重要度を評価し索引付けする．しかし，表現するグラフと呼ばれるデータ構造に着目したグラフ分析

データベース内のキーワード数を K とすると索引構築の計算

は，データ間の関係性に隠れた知識を獲得できる分析技術であ

量は O((N + M )T K) となり，大規模なグラフを対象としたとり，推薦システムや SNS(Social Networking Service) といっ

き K ，N ，M が爆発的に増加し，索引構築に膨大な時間を必たサービスで広く用いられている [1–3]．

要とする．したがって，ObjectRank の高速化は重要な研究課

グラフ分析技術のひとつに，ObjectRank [4,5] がある．Ob-

題となっている．

jectRank は，PageRank [6] を拡張することでデータベース内

1. 1 本研究の貢献のオブジェクトに対するキーワード検索を実現する手法である．

本研究では，ObjectRank の重要度評価の高速化手法を提案

データベース内のオブジェクトをグラフに見立てることによっする．提案手法では，計算対象のノード数 N を削減することて PageRank のリンク解析手法を適用し，各オブジェクトの重で ObjectRank の高速化を図る．具体的には，重要度評価の計

要度を評価する．PageRank とは異なり，ObjectRank は複数算過程で重要度の著しく低いノードを逐次的に枝刈りする．提の種類のノードとエッジからなるグラフを扱うことができるた

案手法は，各ノードの重要度の取り得る上限値と下限値を計算

め，多様なデータに対して適用可能である [7, 8]．ObjectRank

することによって枝刈りした場合に検索結果に与える影響の少の実用的な応用例の一つに，TURank [9] がある．TURankないノードを特定することができるため，高い精度で結果を近は，マイクロブログサービスのひとつである Twitter （注 1） に似することができる．この手法により重要度評価の繰り返し計

ObjectRank を適用することで，Twitter のユーザの評価と算を進めるにつれて計算対象のノードが減少するため，従来のランク付けを行う手法である．TURank は，Twitter におけ

ObjectRank と比較して重要度評価を高速に行うことができる．

るユーザ間の様々な関係性をグラフで表現することによって本研究の貢献は下記の通りである．

ObjectRank の重要度評価手法を適用している．

•

高速性: 提案手法は従来の ObjectRank と比較して重要

ObjectRank は，クエリが与えられると行列ベクトル積の度評価を高速に行うことができる．提案手法は 100 万のノード

繰り返し演算によりグラフ全体のノードの重要度を評価すると 500 万のエッジを持つグラフに対し，約 1 秒で重要度評価必要があるため，グラフ内のノード数を N ，エッジ数を M ，を行うことができる（4. 3. 1 節）．

•（注 1）：http://twitter.com

近似精度: 提案手法は高い精度で ObjectRank の上位 k

件の結果を近似することができる．提案手法は上位 100 件の結果を 90 % 以上の精度で近似することができる．
（4. 3. 2 節）．
上述の通り，ObjectRank は計算コストが膨大であり，大規度評価の高速化を図るため，以降では ObjectRank の重要度評
価について説明を行う．

模グラフに適用することは難しい．しかし，提案手法は逐次的

2. 2 ObjectRank の重要度評価

なノードの枝刈りを行うことで計算対象のノード数を削減し，2. 2. 1 データモデル

重要度評価を高速に行うことができる．実データを用いた評価

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

実験では，90 % 以上の精度で ObjectRank と比較して約 8 倍

有向グラフとして表現する．まず，グラフのノードとエッジの種

重要度評価を高速に行うことができることを示した．

類，及びエッジの重みを定義した Authority Transfer Schema

本稿の構成は次の通りである．まず，2 節で前提となる知識

Graph を作成する（以降，Schema Graph と呼ぶ）．各種ノーについて説明し，3 節で提案手法について述べる．4 節で評価

ドとエッジはラベルが付与され，ラベルによって種類が区別さ実験について説明し，5 節で関連研究を紹介する．そして最後れる．各エッジの重みはそのエッジによって遷移する重要度のに 6 節でまとめと今後の課題について述べる．

割合を示す．ただし，重みは 0 以上 1 以下の値をとり，一つの2. 前 提 知 識
表 1 に本稿が用いる記号の定義を示す．
表 1 本稿が用いる記号の定義
記号
G
V
E
N
M
K
A
d
ϵ
r

定義
計算対象のグラフ
G に含まれるノードの集合
G に含まれるエッジの集合
グラフのノード数
グラフのエッジ数
データベース内のキーワード数
N × N の遷移行列
ダンピングファクタ閾値
各ノードの重要度を並べた N × 1 のベクトルノードから出るエッジの重みの総和は 1 以下に設定する必要がある．図 2 に文献データベースを表現した Schema Graph の例を示す．図 2 の例では，“Conference” や “Year” といったラベルが付与された 4 種類のノードと，それらをつなぐ 8 種類のエッジが存在する．
次に，Schema Graph に基づいて対象のデータから Authority

Transfer Data Graph を構築する（以降，Data Graph と呼ぶ）．
Data Graph の各ノードは “VLDB” や “2004” といったキー
ワードを保持する．Data Graph のエッジの重みは，Schema

Graph で定義した重みをエッジの元ノードの出次数で割った値となる．ただし，出自数は同じ種類のエッジの本数のみを数えたものとする．図 3 に 図 2 に基づいて作成された Data

ObjectRank [4, 5] はデータベースに対するキーワード検索

Graph の例を示す．“Balmin, A.” ノードから “ObjectRank”を実現する手法である．2. 1 節で ObjectRank の概要についノードには重みが 0.1 であるエッジが張られている．これは，て，2. 2 節で ObjectRank の重要度評価について，2. 3 節でSchema Graph の “Author” から “Paper” へのエッジの重み

ObjectRank の問題点についてそれぞれ述べる．

である 0.2 を，“Balmin, A.” の出次数 2 で割った値である．

2. 1 ObjectRank の概要

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

図 3 図 2 に基づいて作成された Data Graph の例
図 1 ObjectRank のシステム

ObjectRank のシステムの概要を図 1 に示す．ObjectRankのシステムは (a) 事前計算部と (b) クエリ処理部の二つに分けることができる．(a) 事前計算部では，各種パラメータを引数にとり ObjectRank 計算モジュールにおいてデータベース内の各オブジェクトの重要度を計算し，結果を索引付けする．(b)
クエリ処理部ではユーザから与えられたクエリと索引に基づいてオブジェクトのランキングを作成し，重要度が上位 k 件のオ
ブジェクトをユーザに返す．本研究は事前計算部における重要2. 2. 2 重要度の計算方法
ObjectRank は，Data Graph に対して重要度評価を行う．
Data Graph の遷移行列を A とする．Data Graph のノード数を N とすると A は N × N の行列であり，(i, j) 要素にはノード vj から vi にエッジ eji が存在する場合は eji の重みを，それ以外の場合は 0 を格納する．このとき，あるキー
ワード t に対する G の各ノードの重要度を並べたベクトルr = [r(v1 ), r(v2 ), . . . , r(vn )]T は以下の式で得られる．
r = dAr + (1 − d)q(1)

ただし，d (0 < d < 1) はダンピングファクタ，BS(t) をキー
ワード t を含むノードの集合としたとき，q は n 次元のクエリベクトルであり，以下のように求める．

1/|BS(t)|q(v) =
0度の計算対象から枝刈りする．下限値 r は，繰り返し計算の過程で上限値 r を効率的に更新するために用いる．

3. 2. 1 上限値と下限値
重要度の下限値 r と上限値 r を以下に定義する．

(v ∈ BS(t))［定義 3.1］（下限値） i 番目の繰り返し計算におけるノード v(otherwise)の下限値は次のように計算する．

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

任意の初期値を与えて以下の式を繰り返し計算する．

i∑

dj pj (v)

(3)

j=0

r i+1 ← dAr i + (1 − d)q(2)［定義 3.2］（上限値） i 番目の繰り返し計算におけるノード v

r i は i 回目の繰り返し計算によって求めた重要度のベクトの上限値は次のように計算する．

ルである．r が収束したとき繰り返し計算を終了する．

2. 2. 3 索 引 構 築i∑ri (v) = (1 − d)ObjectRank はクエリ応答の効率化のために，クエリ処理

dj pj (v) + di+1 pi (v)j=0

時に重要度評価を行う代わりに事前に索引構築を行う．まず+データベースに現れるキーワード t について各ノードの重di+1∆i A(v)(1 − d)(4)

要度 rt を計算し，ノードの id id(u) と重要度 rt (u) のペア

pi は長さ i のランダムウォークの確率を表す N 次元ベクト< id(u), rt (u) > を rt (u) の降順で並べたリストを作成する．

ルであり，pi = Ai q で計算する．ただし，i = 0 であるとき

次に，重要度 rt (u) が任意の閾値 ϵ を下回るノードのペアをリ

pi = q とする．また，∆i は次のように計算する．
1∆i = ∑


ストから取り除き，リストを索引に格納する．最後に，上述の処理をデータベースに現れる全てのキーワードについて実行することで索引を構築する．

2. 3 ObjectRank の問題点
ObjectRank は，べき乗法を用いて各ノードの重要度が収束するまで式 (1) を繰り返し計算する必要があるため，重要度評
価の計算量は O((N + M )T ) となる．索引構築時にはこの計算をデータベース内に現れる全てのキーワードに対して行う必要があり，索引構築の計算量は O((N + M )T K) となる．大規(i = 0)u∈V0 ∆i (v)

(i =
| 0)

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

G0 を元のグラフとしたとき，V0 は G0 のノード集合を表す．
∆i (v) は ∆i (v) = max{pi (v) − pi−1 (v), 0} によって計算する．
A はエッジの最大の重みを格納した N 次元ベクトルであり，A(v) = max{A(v, u) : u ∈ Gi } となる．

模グラフを対象とした際には N ，M ，および K が増加するた［補題 3.1］（下限値の性質） i 番目の繰り返し計算において，

め，計算コストが爆発的に増大するという問題がある．

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

3. 提 案 手 法
本節では，提案手法について説明を行う．3. 1 節で概要を述

ri (v) <= r(v)(5)〈証明〉式 (2) より，

べ，3. 2 節で提案手法の詳細を説明する．

3. 1 概要

提案手法は，計算対象とするノード数 N を削減することによって ObjectRank の重要度評価の高速化を図る．2. 2. 3 節で

r i = dAr i−1 + (1 − d)q= d2 A2 r i−2 + (1 − d)(dAq + q)
= di Ai r 0 + (1 − d){di−1 Ai−1 q + di−2 Ai−2 q + · · · + q}

述べた通り，ObjectRank は重要度が閾値 ϵ より低いノードについてはノードの id と重要度のペア < id(u), r(u) > の索引= di Ai r 0 + (1 − d)

i−1
∑

dj pj

j=0

への格納は省略する．すなわち，重要度の著しく低いノードは検索結果に影響を持ちにくいという性質がある．そこで提案手

最終的な重要度のベクトルは r の収束値であるため，r = r ∞法では，重要度評価における繰り返し計算の過程で検索結果にとなる．0 < d < 1 かつ A∞ の各要素は 0 以上 1 以下の値を影響を持ちにくいノードを特定し，計算対象から逐次的に枝刈とるため，りすることによってノード数を削減する．

3. 2 提案手法の詳細

r = d∞ A∞ r 0 + (1 − d)= (1 − d)∞∑ド ui の上限値 r(ui ) が任意の閾値 ϵ を下回ったとき，ui の最終的な重要度も同様に ϵ を下回ることが保証されるため，重要

dj sj

j=0

提案手法では，枝刈り可能なノードを特定するために各ノードが取り得る重要度 r の上限値 r と下限値 r を推定する．ノー

∞
∑

j=0

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

dj sj

(6)

r = (1 − d)

∞
∑

dj sj

i (i = 0, 1, . . . ) 番目の繰り返し計算において，各ノードの重(7)

要度 ri (v)，上限値 ri (v)，下限値 ri (v) を計算する（6，7 行

j=0>= (1 − d)i∑目）．このとき、定義 ?? より上限値と下限値は O(1) で計算
j

d sj

(8)

することができる．次に，得られた上限値が ϵ を下回ったノーj=0

ド u と u に隣接するエッジをグラフ Gi から取り除き，新た□が成り立つため，補題 3.1 の式 (5) が得られる．

［補題 3.2］（上限値の性質） i 番目の繰り返し計算において，な部分グラフ Gi+1 を構築する（12 行目）．i 番目の繰り返し計算において，Gi に含まれる全てのノードの重要度が収束したとき，または繰り返し計算回数がユーザの設定した上限 τ に

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

達したときにアルゴリズムを終了する．
ir (v) > r(v)(9)
Algorithm 1 提案手法のアルゴリズム□〈証明〉付録 1. を参照．

重要度評価の際の繰り返し計算において，下限値 r と上限値

r は次のように逐次的に計算することができる．
［補題 3.3］（下限値と上限値の逐次的な計算） 下限値 r i と上限値 r i の逐次的な計算は以下のように行う．また，次式はO(1) で計算可能である．

(1 − d)q(v)r (v) =
ri−1 + (1 − d)di p (v)ii(i = 0)
(i =
| 0)


q(v) + d A(v)(1−d)
ri (v) =ri−1 + di p (v) + di+1 ∆ A(v)
i

(1−d)

i

(10)

Input: G, 元のグラフ; ϵ, 閾値; τ , 最大反復回数
Output: 枝刈りされたものを除いた各ノードの重要度
1: i ← 0
2: Gi ← G
3: while i < τ do4:ϵ ← ϵ/Gi のノード数
5:for each Gi に含まれるノード v に対して do
6:
式 (2 より重要度 ri (v) を計算
7:
式 (10)，(11) より上限値 ri (v)，下限値 r i (v) を計算
8:
end for9:
if Gi の全てのノードの重要度が収束 then
10:
アルゴリズムを終了する
11:
end if
12:
Gi から上限値が ϵ を下回るノードを取り除き Gi+1 を構築
13:
i←i+1
14: end while(i = 0)4. 評 価 実 験

(i =
| 0)

本節では，実データに対して提案手法および ObjectRank を(11)

実行し，実行速度と上位 k 件の結果の近似精度の観点で提案手〈 証 明 〉i = 0 で あ る と き ，定 義 1 よ り ri (v) = (1 −∑d) ij=0 dj pj (v) = (1 − d)p0 (v) = (1 − d)q(v)．ま た ，定d
義 2 より ri (v) = (1 − d)q(v) + dq(v) + (1−d)A(v) となり，
dri (v) = q(v) + (1−d)A(v) が成り立つ．このとき，d，q(v)，A(v) は定数であるため，ri (v) と ri (v) は O(1) で計算可能で法の有効性を検証する．実験環境の詳細は表 2 に示す．
表2
CPU
メモリ
OS
言語

実験環境

Intel Xeon (E5-1620 v4) 3.5GHz
128GB
CentOS (7.3.1611 (Core))
C++11 (gcc 4.8.5)

ある．

i =
| 0 であるとき，定義 1 より ri (v) − ri−1 (v) = (1 −∑i∑jid) j=0 dj pj (v) − (1 − d) i−1
j=0 d pj (v) = (1 − d)d pi (v) と

4. 1 データセット

なり，ri (v) = r i−1 + (1 − d)di pi (v)．また，定義 1，2 より，
i+1dri (v) − ri−1 (v) = di pi (v) + (1−d)∆i A(v) となり，ri (v) =i+1

dri−1 (v)+di pi (v)+ (1−d)∆i A(v) が成り立つ．このとき，ri−1 (v)は i − 1 番目の繰り返し計算時においてあらかじめ計算されており，d，pi (v)，A(v) は定数であるため，r i (v) と r i (v) はO(1) で計算可能である．

□

3. 3 アルゴリズム
本節では，提案手法のアルゴリズムについて述べる．Algo-rithm 1 に提案手法の疑似コードを示す．Algorithm 1 は，グ
ラフ G，閾値 ϵ，最大反復回数 τ を入力に受け取り，枝刈りされたノードを除いた各ノードの重要度を計算する．ただし，閾
値 ϵ は計算対象のノード数で割った値を使用する（4 行目）．
これは，各ノードの重要度の総和は 1 となり，ノード数が大きいときはノードの重要度や上限値，下限値は小さい値を取ってしまうためである．

図4

Schema Graph 2

データセットは AMiner （注 2） が公開している文献データベース [10–14] を用いた．このデータセットには文献のタイトル，
発表年，発表場所，著者名，引用している文献のリストの情報が含まれている．Schema Graph で定義したエッジの重みの実験結果への影響も加味するために，グラフは 2 つの Schema

Graph に基づいて作成した．1 つは図 2 の Schema Graph に基づいて構築し（以降，Schema Graph 1 とする），2 つ目は各ノードの出エッジの重みの総和が全て等しくなるように設定し（注 2）：http://aminer.org/

た図 4 の Schema Graph に基づいて作成した（以降，Schema

Graph 2 とする）．Schema Graph 2 は Schema Graph 1 と比
較して，全ての種類のノードが高い重要度を持ちやすいように設定されていると考えることができる．作成したグラフのノード数とエッジ数の詳細は表 3 に示す．
表 3 ノード数とエッジ数の詳細
Conference のノード数
Year のノード数
Paper のノード数
Author のノード数
Conference，Year 間のエッジ数
Year，Paper 間のエッジ数
Paper，Paper 間のエッジ数
Paper，Author 間のエッジ数
総ノード数
総エッジ数

12,6096762981459577648
1,259,628
1,265,502
2,624,116
1,238,266
5,149,294

図 5 実行時間（条件 1）

4. 2 実 験 方 法
本実験は，単一キーワードについて重要度評価を行った際の実行時間と上位 k 件の近似精度を計測した．本稿では，“Pa-per” および “Conference” ラベルのノードから “PageRank”，“VLDB” というキーワードを選択し，これらに対する重要度をそれぞれ計算した．すなわち，以下の 4 通りの条件で実験を行った．

•(条件 1) Schema Graph: 1，キーワード: “PageRank”•(条件 2) Schema Graph: 2，キーワード: “PageRank”•(条件 3) Schema Graph: 1，キーワード: “VLDB”•(条件 4) Schema Graph: 2，キーワード: “VLDB”

図 6 実行時間（条件 2）

し，枝刈りが行われにくくなったためであると考えられる．

このとき，ダンピングファクタ d は 0.85，最大計算回数 τ は

100 回に固定し，閾値 ϵ の値を変更して実行した．近似精度の指標は以下を用いた．

P rec(t, k) =|P roSet(t, k) ∩ ORSet(t, k)|k(12)

P roSet(t, k) と ORSet(t, k) は，キーワード t に対して提案手法と ObjectRank の重要度評価をそれぞれ実行し，得られた上
位 k のノードの集合である．P rec(t, k) は 0 以上 1 以下の値を取り，近似精度が良くなるにつれて 1 に近い値をとる．

4. 3 実 験 結 果
4. 3. 1 実 行 速 度
様々な閾値 ϵ の値に対する ObjectRank と提案手法の実行

図 7 実行時間（条件 3）

時間をそれぞれ計測した．条件 1，条件 2，条件 3，条件 4 について実行した結果をそれぞれ図 5，図 6，図 7，図 8 に示す．
実験結果より，いずれの条件の場合でも閾値の値が小さい場合
は提案手法の方が遅くなってしまうということがわかる．閾値
の値が小さい場合は枝刈りが行われにくく，上限値の計算によるオーバーヘッドが影響したためであると考えられる．一方，
閾値の値が大きい場合は枝刈りが上手く行われ，提案手法の方が高速に結果を得られることがわかる．条件 1（図 5）と条件

2（図 6）の間に大きな差は見られないが，条件 3（図 7）と条件 4（図 8）を比較すると，条件 3 の方がより小さな閾値の値で提案手法が ObjectRank よりも高速になっていることがわかる．これは，条件 4 は Schema Graph の重みを図 2 から図 4に変更したことで検索結果へと影響を与えにくいノードが減少

図 8 実行時間（条件 4）

4. 3. 2 近 似 精 度
ObjectRank によって得られた上位 k 件の結果を真値とし，式 (12) を用いて様々な閾値 ϵ に対する提案手法の上位 k 件の近似精度を計測した．条件 1，条件 2，条件 3，条件 4 について実行した結果をそれぞれ図 9，図 10，図 11，図 12 に示す．実験結果より，いずれの条件の場合でも上位 50 件程度であれば90 % 以上の高い精度で結果を得られることが示された．提案
手法は計算過程において重要度の上限値と下限値を計算することによって検索結果に影響を持ちにくいノードの特定を目指したが，実験結果より枝刈り対象のノードが適切に選択されたことがわかる．また，条件 1（図 9）と条件 2（図 10，および条件 3（図 11）と条件 4（図 12）を比較すると，Schema Graph

図 11

近似精度（条件 3）

図 12

近似精度（条件 4）

1 を用いた場合よりも Schema Graph 2 を用いた場合の方が近似精度が低くなる傾向が見られた．これは，Schema Graph の重みを図 2 から図 4 に変更したことで，検索結果へと影響を与えにくいノードが減少したためであると考えられる．
実行時間および近似精度の実験結果より，提案手法は閾値が小さい場合は実行時間が長く，近似精度が高くなった．一方で，閾値が大きい場合は実行時間が短く，近似精度は比較的低くなったため，実行時間と近似精度の間にはトレードオフの関係が存在する．最適な閾値の値の選択は今後の課題としてあげら
れる．

5. 関 連 研 究
5. 1 PageRank に対する関連研究
Monte Carlo 法 [15–17] は，べき乗法による繰り返し計算を行う代わりに，PageRank におけるランダムサーファーモデ
ルに基づいて重要度が遷移する様子をランダムに試行する手法である．ランダムサーファーモデルとは，Web のランダムなページから遷移を開始し，ランダムなハイパーリンクを選択してページの遷移を繰り返すモデルである．Monte Carlo 法で図 9 近似精度（条件 1）

は，ランダムサーファーの遷移を複数回試行して終着点を記録する．あるページの重要度は，そのページが終着点となった回数に応じて決定される．しかし， [16] で述べられている通り高い精度で結果を近似するためには試行回数を増やす必要がある．

Fujiwara ら [18] は，繰り返し計算の過程で解になり得ないノードを逐次的に枝刈りし，PageRank の Top-k 検索を高速化する手法 F-Rank を提案した．F-Rank では，繰り返し計
算の各ステップにおいて各ノードの重要度の上限値と下限値の推定値を用いて Top-k 検索の結果になり得ないノードを特定し，グラフから枝刈りする．グラフからノードの枝刈りを行う
が，検索結果は理論的に正しいことが保障されている．しかし，

F-Rank は遷移行列の列が正規化される PageRank の特性を利用しているため，ObjectRank には適用できない．

5. 2 ObjectRank に対する高速化手法
図 10

近似精度（条件 2）

Hwang ら [19] は，元のグラフから比較的ノード数の少ない部分グラフを構築することで ObjectRank を高速化する手法 BinRank を提案した．計算対象のキーワードをクラスタリ

Weighted Personalized Pagerank: Breaking A Decade-Old
Performance Barrier,” in Proc. KDD, pp. 1325–1334, 2015.
Y. Yamaguchi, T. Takahashi, T. Amagasa, and H. Kitagawa, “TURank: Twitter User Ranking Based on UserTweet Graph Analysis,” in Proc. WISE, pp. 240–253, 2010.
J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su, “Arnetminer: Extraction and mining of academic social networks,” in Proc. KDD’08, pp. 990–998, 2008.
J. Tang, L. Yao, D. Zhang, and J. Zhang, “A Combination
Approach to Web User Profiling,” TKDD, vol. 5, pp. 2:1–
2:44, Dec. 2010.
J. Tang, A. C. M. Fong, B. Wang, and J. Zhang, “A Unified Probabilistic Framework for Name Disambiguation in
Digital Library,” TKDE, vol. 24, pp. 975–987, June 2012.
J. Tang, J. Zhang, R. Jin, Z. Yang, K. Cai, L. Zhang, andZ. Su, “Topic Level Expertise Search over Heterogeneous
Networks,” Machine Learning Journal, vol. 82, pp. 211–
237, Feb. 2011.
J. Tang, D. Zhang, and L. Yao, “Social Network Extraction of Academic Researchers,” in Proceedings of the 2007
Seventh IEEE International Conference on Data Mining,
ICDM ’07, pp. 292–301, 2007.
K. Avrachenkov, N. Litvak, D. Nemirovsky, and N. Osipova,“Monte Carlo Methods in PageRank Computation: WhenOne Iteration is Suﬃcient,” SIAM J. Numer. Anal., vol. 45,
pp. 890–904, Feb. 2007.
D. Fogaras, B. Rcz, K. Csalogny, and T. Sarls, “Towards
Scaling Fully Personalized PageRank: Algorithms, Lower
Bounds, and Experiments,” Internet Mathematics, vol. 2,
no. 3, pp. 333–358, 2005.
S. Chakrabarti, “Dynamic Personalized Pagerank in EntityRelation Graphs,” in Proc. WWW, pp. 571–580, 2007.
Y. Fujiwara, M. Nakatsuji, H. Shiokawa, T. Mishima, and
M. Onizuka, “Fast and Exact Top-k Algorithm for PageRank,” in Proc. AAAI 2013, pp. 1106–1112.
H. Hwang, A. Balmin, B. Reinwald, and E. Nijkamp, “BinRank: Scaling Dynamic Authority-Based Search Using Materialized SubGraphs,” in Proc. ICDE, pp. 66–77, 2009.

ングし，クラスタに含まれるキーワードとの関連度が著しく低いノードを取り除いた部分グラフを，クラスタごとに構築し索[9]引に格納する．クエリ処理時には，キーワードが含まれるクラスタから作成された部分グラフのみを対象に重要度評価を行う．

[10]

しかし BinRank は，キーワードのクラスタごとに部分グラフを構築し索引付けするため，対象のグラフサイズが大きいとき[11]

索引サイズが膨大となる．また，クエリ処理時にべき乗法による繰り返し計算を行うためクエリ応答に時間がかかってしまい，[12]依然として計算コストが問題となる．

6. 結

[13]

論

本稿では大規模グラフに対する ObjectRank の高速化手法を提案した．提案手法では計算対象とするノード数 N を削減[14]することによって ObjectRank の高速化を図った．提案手法は重要度評価の繰り返し計算の過程において重要度の著しく低いノードを逐次的にグラフから枝刈りすることでノード数を削減[15]する．提案手法は，計算過程で各ノードの重要度の取り得る上限値と下限値を計算することによって検索結果に影響を持ちに
くいノードを特定することができるため，高い精度で結果を近[16]似することができる．実データを用いた評価実験では，提案手法は ObectRank と比較して高速かつ精度よく重要度評価を行うことができることを示した．

[17]

今後の課題として，計算対象のキーワード数 K の削減による ObjectRank の高速化手法の提案があげられる．2. 3 節で述[18]

べた通り ObjectRank の索引構築の計算量は O((N + M )T K)となるため，キーワード数 K の削減により ObjectRank の索[19]

引構築の高速化が期待できる．

謝

辞付

本研究成果は，JSPS 科研費 (26280037,16H07410) の助成を受けたものである.

録

1. 補題 3.2 の証明〈証明〉式 (6) より，
文

献[1] M. Gori and A. Pucci, “ItemRank: A Random-Walk Based
Scoring Algorithm for Recommender Engines,” in Proc. IJCAI, pp. 2766–2771, 2007.
[2] B. Bahmani, A. Chowdhury, and A. Goel, “Fast Incremental and Personalized PageRank,” Proc. VLDB, vol. 4,
pp. 173–184, Dec. 2010.
[3] S. E. Schaeﬀer, “Graph Clustering,” Computer Science Review, vol. 1, pp. 27–64, Aug. 2007.
[4] A. Balmin, V. Hristidis, and Y. Papakonstantinou, “ObjectRank: Authority-Based Keyword Search in Databases,” inProc. VLDB, pp. 564–575, 2004.
[5] V. Hristidis, H. Hwang, and Y. Papakonstantinou,“Authority-Based Keyword Search in Databases,” ACM
Trans. Database Syst., vol. 33, Mar. 2008.
[6] S. Brin and L. Page, “The Anatomy of a Large-Scale Hypertextual Web Search Engine,” in Proc. WWW, pp. 107–117,
1998.
[7] V. Hristidis, Y. Wu, and L. Raschid, “Eﬃcient Ranking
on Entity Graphs with Personalized Relationships,” TKDE,
vol. 26, pp. 850–863, Apr. 2014.
[8] W. Xie, D. Bindel, A. Demers, and J. Gehrke, “Edge-r(v) = (1 − d)∞∑dj pj (v)j=0

= (1 − d)i∑j=0

dj pj (v) + (1 − d)∞∑di+j pi+j (v)

j=1

(A·1)
まず，

pi+j (v) <= pi (v) + j∆i A(v)(A·2)

が成り立つことを示す．Hj (v) を j 回エッジをたどることでノード v に到達可能なノードの集合，Ri を Vi に含まれるノードに到達可能なノードの集合とする．pi+j − pi+j−1 =Ai+j q − Ai+j−1 q = AAj−1 (pi − pi−1 ) より，
pi+j (v) − pi+j−1 (v)=∑∑u∈H1 (v)j−1(u, w)(pi (w) − pi−1 (w))
w∈Hj−1 (u) A(v, u)A

<
=

∑

∑
w∈Hj−1 (u)j−1(u, w)∆i (w)u∈H1 (v) A(v)A

A(0, 0) + · · · + A(N − 1, 0) =

∑
∑
j−1
<
= A(v) w∈Ri ∆i (w)( u∈H1 (v) A (u, w))(A·3)

A(0, 1) + · · · + A(N − 1, 1) =となる．ここで，αmax を Schema Graph 内のノードの出エッ
出エッジの重みの総和は 1.0 であり，Schema Graph 内で最大

u=0
N
−1
∑

A(0, N − 1) + · · · + A(N − 1, N − 1) =となる．したがって，αmax = 1.0 となる．

∑

A(u, 1) <= αmaxN−1∑

A(u, N − 1) <= αmaxu=0

j−1
Aj−1 (u, w) <= αmax(A·4)

u∈H1 (v)

より，

∑N −1
u=0

が成り立つことを示すために，∑A(u, 0) <= αmaxu=0..
.

ジの重みの総和の最大値とする．図 2 の例の場合，“Paper” の

N
−1
∑

k−1
Ak (u, w) <(0, w) + · · · + αmax Ak−1 (N − 1, w)= αmax A∑ k−1= αmaxA(u, w)
(A·9)
u∈V0

j−1
Aj−1 (u, w) <= αmax

(A·5)

u∈V0

を数学的帰納法を用いて証明する．

(i) j=1 のとき，E を単位行列とするとが成り立つ．式 (A·7)，(A·9) より，∑∑kAk (u, w) <= αmaxu∈V0

u∈V0 E(u, w) = 1

より式 (A·5) は成り立つ．

が成り立つ．したがって，j = k + 1 のときも式 (A·5) が成り(ii) j=k のとき，式 (A·5) は成り立つ，すなわち，

立つ．

∑(i)，(ii) より，全ての自然数 j に対して式 (A·5) が成り立つ．

k−1
Ak−1 (u, w) <= αmax

(A·6)

u∈V0

が成り立つと仮定する．式 (A·6) の両辺に αmax をかけると，

αmax

∑

k−1

A

k
(u, w) <= αmax∑

Ak−1 (u, w) = αmax Ak−1 (0, w) + . . .

u∈V0

(A·8)
k−1

Aj−1 (u, w)

し た がって ，式 (A·3) よ り pi+j (v) − pi+j−1 (v) <=∑V
A(v) w∈Ri ∆i (w)αj−1
0 より
max と な る ．こ こ で ，Ri ⊂=∑∑< w∈V ∆i (w) が成り立ち，
w∈Ri ∆i (w) =0
j−1
pi+j (v) − pi+j−1 (v) <= αmax ∆i A(v)

(A·10)となるため，kである．一方で，A = AA

より，行列 A の (u, w) 要素は∑ −1
k−1(v, w) =次のように表される．A (u, w) = N
v=0 A(u, v)Akj−1
pi+j (v) <= ...
= pi+j−1 (v) + αmax ∆i A(v) <j−1<= pi (v) + (1 + · · · + αmax )∆i A(v) <= pi (v) + j∆i A(v)(A·11)A(u, 0)Ak−1 (0, w) + A(u, 1)Ak−1 (1, w) + · · · + A(u, N − 1)
Ak−1 (N − 1, w) ここで，u について総和をとると，
N
−1
∑

∑
u∈V0

u∈H1 (v)+αmax Ak−1 (N − 1, w)

kAj−1 (u, w) <=となるため，式 (A·4) が成り立つ．

が成り立つ．このとき，∑

ここで，H1 (v)⊂
=V0 より

(A·7)

u∈V0

αmax

以上で数学的帰納法による式 (A·5) の証明を終了する．

が成り立つ．したがって，式 (A·2) は成り立つ．以上より，kk−1

A (u, w) = A(0, 0)A

u=0(0, w) + . . .
+A(0, N − 1)A

k−1

k−1

+A(1, 0)A

(0, w) + · · · + A(1, N − 1)A(N − 1, w)

k−1(N − 1, w)(1 − d)∞∑j=1+A(N − 1, N − 1)Ak−1 (N − 1, w)= {A(0, 0) + · · · + A(N − 1, 0)}Ak−1 (0, w)+{A(0, 1) + · · · + A(N − 1, 1)}Ak−1 (1, w)∞∑{pi (v)di+j + jdi+j ∆i A(v)}
j=1

∑
∑∞
i+j < di+1
i+j
di+1
ここで， ∞< (1−d)2 から= 1−d ， j=1 jd
j=1 d

+...
+A(N − 1, 0)Ak−1 (0, w) + . . .

di+j pi+j (v) <= (1 − d)(1 − d)∞∑di+j pi+j (v) < di+1 pi (v) +j=1が成り立つ．したがって，式 (A·1) より，

r(v) = (1 − d)i∑dj pj (v) + (1 − d)

j=0

+...
+{A(0, N − 1) + · · · + A(N − 1, N − 1)}Ak−1 (N − 1, w)が成り立つ．このとき，式 (A·8) とdi+1∆i A(v)(1 − d)< (1 − d)i∑dj pj (v) + di+1 pi (v) +j=0となるため，補題 3.2 は成り立つ．

∞∑

di+j pi+j (v)

j=1

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