DEIM Forum 2013 E9-4

局所計算に基づく ObjectRank 推定
坂倉

悠太†

山口

祐人†

天笠

俊之††,†††

北川 博之††† 筑波大学大学院システム情報工学研究科 〒 305–8573 茨城県つくば市天王台 1–1–1†† 筑波大学システム情報系情報工学域 〒 305–8573 茨城県つくば市天王台 1–1–1††† 宇宙航空研究開発機構宇宙科学研究所 〒 252–5210 神奈川県相模原市中央区由野台 3–1–1
E-mail: †{yuuta,yutoymgc}@kde.cs.tsukuba.ac.jp, ††{amagasa,kitagawa}@cs.tsukuba.ac.jp
あらましデータベース上のオブジェクトの重要性を評価する手法として，ObjectRank というリンク構造解析手法がある．ObjectRank は行列計算を繰り返すため，計算コストが大きい．一方で，全てのノードではなく，一部のノードの ObjectRank だけが必要とされる場合もある．本稿では，グラフ全体ではなく局所的なグラフを用いることで、計算コストを抑えつつ ObjectRank を推定する手法を提案する．提案手法では，エッジの重みを考慮し、ObjectRankの推定に適した局所的なグラフを作成する．評価実験では，提案手法は，比較手法と比較して，計算コストを抑えながら精度を維持することができた．
キーワード

ObjectRank，リンク構造解析，データマイニング，情報検索

Yuta SAKAKURA† , Yuto YAMAGUCHI† , Toshiyuki AMAGASA††,††† , and Hiroyuki
KITAGAWA††† Graduate School of Systems and Information Engineering, University of Tsukuba
1–1–1 Tennodai, Tsukuba, Ibaraki, 305–8573, Japan†† Faculty of Engineering, Information and Systems, University of Tsukuba
1–1–1 Tennodai, Tsukuba, Ibaraki, 305–8573, Japan††† Institute of Space and Astronautical Science, Japan Aerospace Exploration Agency
3–1–1 Yoshinodai, Chuo-ku, Sagamihara, Kanagawa, 252–5210, Japan
E-mail: †{yuuta,yutoymgc}@kde.cs.tsukuba.ac.jp, ††{amagasa,kitagawa}@cs.tsukuba.ac.jp

1. は じ め ににおけるグラフ全体に対して ObjectRank を計算すると，計算コストが膨大になってしまう．また，ある特定のノード群のラ論文の共著関係やソーシャルネットワークなど，様々な種類

ンキングを作成したい場合には，注目しているノード以外の重のノードから構成されるグラフが多く存在する．このようなグ要度は不要である．このような場合，注目しているノードの重ラフに関する研究は多く行われているが [6], [8], [16]，例えば良要度だけを高速に推定できると理想的である．

い論文を多く書いている著者のような，重要なノードを抽出するという問題がある．

PageRank においては，特定のノードの PageRank を推定する手法が提案されている [4]．しかし，PageRank とは異なり，複数種類のノードやエッジから構成されるグラフから重要な

ObjectRank は複数種類のノードとエッジを持つグラフを扱っ

ノードを抽出する手法として，ObjectRank [2] という手法があているため，エッジには重みが付けられている．この特徴による．ObjectRank は PageRank [7] を拡張したリンク構造解析

り，PageRank における手法をそのまま ObjectRank に適用す手法である．PageRank とは異なり，ObjectRank のエッジにることは不十分である．そのため，エッジの重みを考慮して重は種類ごとに重みが付けられている．

要度を推定する．

ObjectRank は，PageRank と同様に，行列計算を繰り返す

本稿では，グラフ全体ではなく局所的なグラフを用いて，ため計算コストが大きい．一方で，全てのノードではなく，一ObjectRank を推定する手法を提案する．ObjectRank におい部のノードの重要度だけが必要とされる場合がある．例えば，て，重みが小さいエッジをたどって遷移する評価値は小さいた

特定のノードの重要度の時間的な推移を知りたい場合，各時刻

め，そのエッジが持つ推定の精度への影響は小さい．提案手法

では，エッジの重みを考慮し，重要度の推定に適した局所的なグラフを作成する．本稿では，この局所的なグラフのことを局所グラフと呼ぶ．本研究の目的は，推定の精度を維持したまま，計算コストを抑えることである．精度の指標として，推定した重要度の精度と重要度を推定したノードのランキングの精度に注目する．計算コストの評価指標には，作成された局所グラフ

図 1 Schema Graph の例のサイズと，グラフデータを保存しているデータベースへのア
クセス回数を用いる．
本研究の貢献を以下に示す．

•

複数種類のノードやエッジを持つグラフに対するノードの評価値を推定する手法の提案•

手法を提案した．Chen らの手法は，評価値の推定に適した局所グラフを作成し，その局所グラフを用いて評価値を推定する．
また，過去にクローリングした Web グラフを用いて，新しくクローリングした Web グラフにおける評価値を推定する手法も提DBLP（注 1）データセットを用いた提案手法の有効性の検証

案した．詳細は 3. 2 節で述べる．Chen らの手法は，PageRank

DBLP データセットを用いて評価実験を行った．提案手法は，を推定しているため，局所グラフを作成する時にエッジの重み

既存手法と比較して，局所グラフサイズが約 39% 削減され，推定した重要度の精度が約 24%，ランキングの精度が約 6% 向上
した．

を考慮していない点が，本研究と異なる．

Broder ら [3] は，グラフ凝集による PageRank の推定手法を提案した．Broder らの手法は，Web ページをホストごとに凝

本稿の構成は以下の通りである．2 節で関連研究を紹介し，3集したホストグラフを作成し，ホスト間における計算とホスト

節で予備知識を説明する．4 節で提案手法について説明する．5

内の計算によって，PageRank を推定した．本研究との違いは，

節で評価実験を行い，6 節でまとめと今後の課題を述べる．

特定のノードの評価値だけではなくグラフ全体の評価値を推定

2. 関 連 研 究している点である．

複数種類のノードを含むグラフを用いた様々な研究がされて3. 予 備 知 識いる．Neubauer ら [6] は，ソーシャルブックマークにおける

3. 1 ObjectRank

ユーザ，Web ページ，タグをノードで表現したグラフを分析し，ObjectRank [2] は PageRank [7] を拡張したリンク構造解析

スパマー分類器を作成した．Sun ら [8] は，著者と会議をノー手法であり，データベース上のオブジェクトの重要度を評価

ドで表現したグラフを用いた，著者のランキング手法を提案しするためのアルゴリズムである．PageRank とは異なり，Ob-た．山口ら [16] は，Twitter（注 2）におけるユーザと投稿された

jectRank では複数種類のノードとエッジを扱うことができる．

メッセージをノードで表現したグラフに対して，ObjectRank

ObjectRank では，ノードとエッジにラベルを付与することで，を適用し，ユーザのランキングを行った．本研究では，DBLP

ノードとエッジの種類を区別する．

データセットを，著者，論文，出版年，出版場所をノードで表現したグラフを用いる（詳細は 3. 1 節で述べる）．

まず，Authority Transfer Schema Graph と呼ばれる，グ
ラフ構造とエッジの重みを定義するグラフを定義する（以下，また，あるグラフの部分グラフ内のノードの PageRank に注

Schema Graph と呼ぶ）．図 1 に Schema Graph の例を示す．

目した研究も行われている．Davis ら [5] は，推定したい部分グ

Schema Graph は，ノードラベルの集合（図 1 における “Con-

ラフ内のノードからエッジを張られているノードを部分グラフ

ference”，“Year”，“Paper”，“Author”）とノードラベル間のに追加し，元の部分グラフを含む部分グラフを作成した．この関係を表すエッジの集合から構成される．ノードラベル間に存作成した部分グラフ内で PageRank を計算することで，ノード在する各エッジには，エッジラベルと重みが付与されている．まの PageRank を推定した．Xue ら [15] は，ユーザのアクセスパ

た，評価値は互いに遷移すべきという考え方に基づいて，ノーターンを用いて，推定したい Web グラフから新しいグラフを作

ドラベル間には双方向のエッジが存在している．エッジの重み成し，そのグラフを用いて PageRank を推定した．Wu ら [14]は，そのエッジをたどって遷移する評価値の割合を表している．

は，推定したい部分グラフに含まれていないノードを一つの例えば，図 1 の例では，Paper ラベルノードの評価値は，1 割ノードで表現し，このノードと推定したい部分グラフから構が Year ラベルノードへ，2 割が Author ラベルノードへ，7 割成される部分グラフを用いて PageRank を推定した．Vattaniが他の Paper ラベルノードへ遷移する．エッジの重みは，ノーら [13] は，任意のノード集合が与えられた時に，それらのノードラベル間の関係を反映するように手動で設定される．この時，ドの Personalized PageRank を保存する誘導部分グラフを作各ノードから出るエッジの重みはそれぞれ 0 以上，エッジの重成する手法を提案した．これらの研究は，部分グラフ内のノー

みの総和は 1 以下になるように設定しなければならない．

ドの評価値に注目している点が，本研究とは異なる．

Chen ら [4] は，局所グラフを用いて PageRank を推定する

次に，Schema Graph に基づいて，リンク構造解析の対象のグラフである Authority Transfer Data Graph を構築する（以下，Data Graph と呼ぶ）．図 2 に Data Graph の例を示す．

（注 1）：http://www.informatik.uni-trier.de/∼ley/db/（注 2）：http://twitter.com/

Data Graph におけるノード vi からノード vj へのエッジ eij図 2 Data Graph の例
図 3 作成された局所グラフの例の重み wij は，エッジ eij のエッジラベルに付与されている重みを，vi におけるそのエッジラベルの出次数で割った値になる．例えば，図 2 の例では，Year ラベルノードである “2013”からは，Paper ラベルノードである “Paper1” と “Paper3” へのエッジが張られている．図 1 より，Year ラベルノードから

Paper ラベルノードへのエッジの重みは 0.3 である．Year ラ
ベルノードである “2013” は，Paper ラベルノードに対して 2
本のエッジを張っている．そのため，ノード “2013” がノード

“Paper1” とノード “Paper3” に対して張っているエッジの重みは，それぞれ 0.15 になる．

ObjectRank は以下のように定式化される．
(1 − d)r = dAr +uN

そのエッジ元のノードの情報を取得する．その中で，対象ノードに張られているエッジとそのエッジ元のノードを部分グラフに追加する．あるノードに張られているエッジとそのエッジ元のノードを部分グラフに追加する操作のことをノードの展開と呼ぶ．次に，ノードの展開によって部分グラフに新しく追加されたノードについて注目し，それらのノードも同様に展開する．
ある展開の基準を満たさなくなるまで再帰的にノードの展開を繰り返すことで，部分グラフを拡大し，局所グラフを作成する．
作成された局所グラフの例を図 3 に示す．
局所グラフは三種類のエッジとノードを含んでいる．一つ目のエッジは入力エッジと呼ばれる局所グラフ外から局所グラフ
内へ入ってくるエッジ，二つ目のエッジは出力エッジと呼ばれここで，N はノードの総数，r は全ノードの評価値ベクトル，

る局所グラフ内から局所グラフ外へ出ていくエッジ，三つ目

d はエッジをたどって評価値が遷移する確率（ダンピングファ

は，内部エッジと呼ばれる局所グラフ内から局所グラフ内へのクター），A は遷移確率行列，u は要素が全て 1 の N 次元ベ

エッジである．また，入力エッジを張られているノードを境界

クトルである．

ノードと呼ぶ．対象ノードと境界ノードを除く，局所グラフ内

評価値を計算するために，以下の式による計算を繰り返す．

のノードを内部ノードと呼ぶ．図 3 の局所グラフは，7 本の出(1 − d)r(k+1) ← dAr(k) +uN

力エッジ（点線）と，4 本の入力エッジ（破線），10 本の内部

（ ← は代入を意味する）

ここで，r(k) は k 回目の計算によって得られた評価値ベクトルr である．評価値ベクトル r が収束するまで，上式による計算を繰り返す．

エッジ（実線）を持つ．また，対象ノードは 1 個，内部ノード
は 2 個，境界ノードは 4 個である．

Chen らは，効率的に部分グラフを拡大するために，ノードの影響力を考慮した．あるノードの影響力とは，そのノードのまた，この式は PageRank と同様であるが，ObjectRank は持つ評価値のうち，ランダムジャンプを除いて，最終的に対象

遷移確率行列 A の作成の仕方が異なる．ObjectRank では，ノードに到達する評価値の割合のことである．影響力の大きい

ノード vi から vj へのエッジが存在する場合，aji には Data

ノードは，対象ノードの評価値の推定精度への影響が大きい．

Graph におけるエッジの重み wij が格納され，それ以外の場合

また，影響力が大きいノードに対してエッジを張っているノーは 0 が格納される．

ドも，大きな影響力を持つと考えられる．Chen らの手法では，

3. 2 Chen らの PageRank 推定手法

影響力を入次数で割った値を展開の基準として用い，この値がChen ら [4] の手法は，局所グラフを用いて PageRank を推閾値以上であるノードを展開する．

定する手法である．Chen らの手法では，評価値の推定に適し

影響力の正確な計算は計算コストが大きいため，Chen らはた局所グラフを作成する．作成した局所グラフを用いて評価値

OPIC アプローチ [1] を用いて，以下の手順で影響力の推定値を推定したいノード（対象ノード）の評価値を推定する．

を計算した．

まず，対象ノードからエッジを逆方向にたどっていくことで（ 1 ） 影響力の推定値を計算したいノード v に評価値 1 を与部分グラフを拡大し，局所グラフを作成する．拡大の始点となえる．

る部分グラフは，対象ノードだけを含む部分グラフである．ま（ 2 ） ノード v の評価値を，ノード v が張っているエッジ

ず，対象ノードについて注目し，対象ノードから出ているエッとランダムジャンプによって遷移させる．この時，出力エッジ

ジとそのエッジ先のノード，対象ノードに入っているエッジとによって部分グラフ外に遷移する評価値とランダムジャンプによって遷移する評価値は無視する．
（ 3 ） 評価値を持っている内部ノードと境界ノードから一つのノードを選択し，そのノードの評価値を（2）と同様に遷移
させる．
（ 4 ） 内部ノードと境界ノードが持っている評価値の合計が閾値未満になるまで，（3）の操作を繰り返す．
（ 5 ） 対象ノードが持っている評価値をノード v の影響力の推定値とする．
図 4 fetch 操作の例

局所グラフの作成後，境界ノードの評価値を推定する．境界
ノードは局所グラフ内からだけではなく，局所グラフ外からもエッジ（入力エッジ）を張られている．そのため，境界ノードの評価値を直接計算することはできず，その評価値を推定する必要がある．また，対象ノードの評価値の推定精度は，境界ノードの影響力と境界ノードの評価値の推定精度に影響される．そのため，境界ノードの評価値を精度よく推定することが重要である．Chen らは，ヒューリスティックな方法を用いて，境界ノードの評価値を推定した．具体的には，境界ノードに張られている入力エッジから評価値 d/E が遷移してくると推定した．
ここで，E はグラフ全体におけるエッジの総数である．ランダ
ムジャンプと内部ノード，対象ノードから境界ノードに遷移してくる評価値は計算することができる．これにより，境界ノードの評価値を推定することができる．
最後に，局所グラフ内で PageRank を計算することで対象ノードの評価値を計算する．PageRank の計算の繰り返しごとに以下の操作を行う．

•

推定した評価値 (d/E) が入力エッジから境界ノードに遷

本稿では，グラフデータがリレーショナルデータベースなどに保存されている環境を想定する．そのため，ノードの情報を取得するために，“fetch” 操作を用いる．fetch 操作では，一つのノードの ID が与えられた時，以下の情報をデータベースから取得する．

•

与えられたノードの入次数と出次数•与えられたノードが張っているエッジとそのエッジのラベル，そのエッジ先のノードの ID•与えられたノードに張られているエッジとそのエッジのラベル，そのエッジ元のノードの ID

fetch 操作の例を図 4 に示す．図 4 において，ノード A に
fetch 操作を行った時，ノード B，E，F，H，これらのノードとノード A をつなぐエッジ，これらのエッジのラベルを取得できる．また，ノード A の入次数と出次数を取得することができる．5. 節の評価実験では，部分グラフの拡大の時に行った

fetch 操作の回数を計算コストの指標として用いる．

移する．

•

が異なるため，その重みの違いを考慮する．

ランダムジャンプと出力エッジによって局所グラフ外に遷移する評価値を無視する．

PageRank の計算終了後の対象ノードの評価値を，推定した対象ノードの評価値とする．

4. 2 提案手法 1：Data Graph におけるエッジの重みを考慮した部分グラフの拡大手法
提案手法 1 は，Data Graph におけるエッジの重みを考慮して部分グラフを拡大する．重みが小さいエッジが持つ対象ノードの評価値の推定精度への影響は小さい．そこで，提案手法 1

4. 提 案 手 法
本節では，まず提案手法の概要について説明する．その後，3 種類の提案手法の詳細について説明する．提案した手法の中で，最も精度が良かった手法は提案手法 1 であった（詳細は 5.

全てのエッジとエッジ元のノードを部分グラフに追加するのではなく，Data Graph におけるエッジの重みを考慮し，追加するエッジとノードを選択する．これにより，次に展開する境界
ノードを減らし，fetch 操作の回数を減らすことができる．そ節で述べる）．

4. 1 概では，境界ノードを展開する時に，境界ノードに張られている

要

重みが小さいエッジをたどって遷移する評価値は小さいため，
そのエッジが持つ対象ノードの評価値の推定精度への影響は小さい．そこで，エッジの重みを考慮しながら対象ノードから部
分グラフを拡大し，局所グラフを作成する．その後，局所グラフの境界ノードの評価値を推定する．最後に，局所グラフを用
いて ObjectRank を計算し，対象ノードの評価値を計算する．

Chen らの手法は PageRank を対象にしているため，全てのエッジを平等に扱っている．しかし，ObjectRank で扱うエッジは複数種類あり，重み付きエッジである．そのため，提案手法では，エッジの重みを考慮して部分グラフを拡大する．例
えば，図 2 において，ノード “2013” は，ノード “DEIM” と“Paper1” からエッジを張られている．これらのエッジは重みのため，計算コストを小さくすることができる．
提案手法 1 では，影響力を入次数で割った値が閾値以上である境界ノードに張られているエッジのうち，Data Graph における重みが閾値以上であるエッジとエッジ元のノードだけを部分グラフに追加する．図 5 に例を示す．この例では，ノード“2012” とノード “Paper1” は境界ノードである．影響力を入次数で割った値の閾値として 0.1，Data Graph におけるエッジの重みの閾値として 0.02 が設定されている．まず，それぞれのノードの影響力の推定値を計算すると，ノード “2012” の影響力は 0.4，ノード “Paper1” の影響力は 0.33 であった．影響力を入次数で割った値を計算すると，ノード “2012” は 0.08，
ノード “Paper1” は 0.11 である．閾値は 0.1 であるため，ノード “2012” は展開しない．次に，ノード “Paper1” に張られて図 5 部分グラフの拡大例 1

図 6 部分グラフの拡大例 2いるエッジ a，b，c の Data Graph における重みを計算すると，るのは，Conference ラベルノード “DEIM” とノード “DEIM”

順に 0.04，0.01，0.03 であった．エッジの重みの閾値は 0.02

が張っているエッジだけである．

であるため，部分グラフに追加されるのはエッジ a とエッジ c，
これらのエッジ元のノードだけである．

4. 3 提案手法 2：Schema Graph におけるエッジの重みを考慮した部分グラフの拡大手法

4. 4 提案手法 3：Schema Graph におけるエッジの重みを考慮した確率的な部分グラフの拡大手法

Schema Graph におけるエッジの重みが大きいほど，対象ノードの評価値の推定精度に与える影響は大きいと考えられる．

提案手法 2 は，Schema Graph におけるエッジの重みに対しそのため，提案手法 3 では，Schema Graph におけるエッジのて閾値を設定し，追加するエッジのラベルを選択する．例えば，

重みが大きいほど，大きな確率をエッジに与え，その確率に基

図 1 の Schema Graph に対して，エッジの重みの閾値としてづいて部分グラフを拡大する．

0.15 が設定されたとする．この時，Paper ラベルノードから提案手法 2 と提案手法 3 は Schema Graph におけるエッジ

Year ラベルノードへのエッジと，cited ラベルエッジの重みはの重みを考慮している．提案手法 2 はエッジの重みに対して閾

閾値未満であるため，これらのラベルのエッジは部分グラフに値が設定されると，重みが閾値未満であるエッジラベルを全て追加されない．他の 6 種類のラベルのエッジだけが追加される．

無視してしまう．一方，提案手法 3 では，エッジの重みに基づ提案手法 1 は Data Graph におけるエッジの重みを考慮する

いた確率を与え，その確率に基づいてエッジとエッジ元のノーのに対して，提案手法 2 は Schema Graph におけるエッジのドを部分グラフに追加する．そのため，必ず無視されるエッジ重みを考慮して部分グラフを拡大する．提案手法 1 において，

ラベルはなく，全てのエッジラベルが追加される可能性を持っData Graph におけるエッジの重みを計算するためには，実際ている．

に境界ノードを展開する前に，部分グラフ外にある，境界ノー

提案手法 3 は，提案手法 2 と同様の手法である．ただし，

ドにエッジを張っているノードに対して fetch 操作を行う必要

Schema Graph におけるエッジの重みに基づいて，エッジとがある．一方，提案手法 2 では，Schema Graph とエッジの重エッジ元のノードを確率的に部分グラフに追加する．図 7 に例

みに対する閾値が決定されると，追加するエッジのラベルが決を示す．この例は，4. 3 節と同様に，図 1 の Schema Graph を定される．境界ノードに対して fetch 操作を行えば，境界ノー用いている．ノード “2013” とノード “Paper3” は境界ノード

ドに張られているエッジのラベルを取得することができる．そであり，影響力を入次数で割った値の閾値として 0.1 を設定しのため，提案手法 2 は，提案手法 1 と比較して，fetch 操作のている．まず，影響力を入次数で割った値について判定すると，回数を小さくすることができる．

閾値未満であるため，ノード “Paper3” は展開しない．次に，

図 6 に例を示す．この例では，図 1 の Schema Graph を用

ノード “2013” に張られている各エッジのラベルから，Schema

いており，ノード “2013” とノード “Paper3” は境界ノードでGraph におけるエッジの重みを取得する．Schema Graph におある．影響力を入次数で割った値の閾値として 0.1，Schema

けるエッジの重みを，そのエッジとエッジ元のノードを追加する

Graph におけるエッジの重みの閾値として 0.15 が設定されて確率として与える．この例では，0.3 の確率でノード “DEIM”

いる．まず，それぞれのノードの影響力の推定値を計算すると，とノード “DEIM” から張られているエッジを，0.1 の確率でノード “2013” の影響力は 0.33，ノード “Paper3” の影響力はノード “Paper1” とノード “Paper2”，これらのノードから張0.21 であった．影響力を入次数で割った値を計算すると，ノーられているエッジを部分グラフに追加する．

ド “2013” は 0.11，ノード “Paper3” は 0.07 である．閾値は0.1 であるため，ノード “Paper3” は展開しない．次に，ノード

5. 評 価 実 験“2013” に張られているエッジのラベルから，Schema Graph

本節では，まず実験で用いるデータセットについて説明する．

におけるエッジの重みを取得する．Conference ラベルノード

次に，提案手法と比較する手法について説明し，実験の方法をから Year ラベルノードへのエッジの重みは 0.3，Paper ラベル

述べる．その後，評価指標について述べ，実験結果を示し，結ノードから Year ラベルノードへのエッジの重みは 0.1 である．

果に対する考察を述べる．

エッジの重みの閾値は 0.15 であるため，部分グラフに追加されサンプリングした対象ノードの評価値を推定した．Chen らの手法を参考にして，入力エッジから評価値 d/E が遷移してくるとした．また，ダンピングファクター d の値を 0.85 に設定した．
各手法の閾値を以下のように設定して，評価実験を行った．
提案手法 1 と比較手法 2 は，以下の閾値の組合せ（15 通り）で評価実験を行った．

図 7 部分グラフの拡大例 3•

影響力/入次数：0.1, 0.01, 0.001•

エッジの重み（Data Graph）：0.1, 0.01, 0.001, 0.0001,

0.00001
表 1 Data Graph の詳細

Paper ラベルノード数

1, 572, 278

Author ラベルノード数

916, 973

Conference ラベルノード数
Year ラベルノード数

提案手法 2 は，以下の閾値の組合せ（6 通り）で評価実験を行った．

6, 711•

影響力/入次数：0.1, 0.01, 0.001

76•

エッジの重み（Schema Graph）：0.1, 0.2

29, 427

提案手法 3 と Chen らの手法は，影響力を入次数で割った値のYear–Paper 間のエッジ数

1, 572, 134

閾値を 0.1, 0.01, 0.001 に設定して評価実験を行い，比較手法 1

cites/cited ラベルエッジ数

2, 083, 947

は，ステップ数 k を 1, 2 に設定して評価実験を行った．

Paper–Author 間のエッジ数

4, 121, 353

Conference–Year 間のエッジ数

5. 4 評 価 指 標
本実験では，推定の精度と計算コストの観点から手法を評価

5. 1 データセット

した．

本実験では，Arnetminer（注 3）が提供している DBLP のデー

各手法の評価値の推定精度の評価指標として，相対誤差を用

タセット [9]〜[12] を用いた．このデータセットには，文献ごといた．対象ノード t の評価値の相対誤差 err(t) は以下のようにのタイトル，著者，出版場所，出版年，引用している文献，引定義される．

用されている数が含まれている．図 1 の Schema Graph と上記のデータセットに基づいて Data Graph を作成した．作成された Data Graph の詳細を表 1（注 4）に示す．

5. 2 比 較 手 法
本実験では，3 種類の提案手法を Chen らの手法および次の二つの手法と比較した．
比較手法 1 は，対象ノードから k ステップだけエッジを逆方向にたどることで部分グラフを拡大する．すなわち，対象ノードまでの距離が k 以下である全てのノードを含む局所グラフを作成する．例えば，図 3 のグラフは k = 2 の時に作成される局
所グラフの例である．
比較手法 2 は，提案手法 1 と同様の部分グラフ拡大手法である．ただし，Data Graph におけるエッジの重みを計算する

err(t) =|r(t) − r′ (t)|r(t)

ここで，r(t) は対象ノード t の正確な評価値，r ′ (t) は対象ノード t の推定した評価値である．相対誤差 err(t) の値が小さいほど，対象ノード t の評価値を高い精度で推定できていることを示している．サンプリングした対象ノードの相対誤差の平均を計算して，各手法を評価した．
サンプリングした対象ノードのランキングの精度を評価する
ために，スピアマンの順位相関係数を用いた．スピアマンの順
位相関係数 ρ は以下のように定義される．

ρ=1−

6ΣD2
N3 − N

時に，Schema Graph におけるエッジの重みを使用しない．具

ここで，D は正確な評価値に基づくサンプリングした 100 個の体的には，部分グラフ外にあるノード v から境界ノードに張対象ノードのランキングと推定した評価値に基づくサンプリンられているエッジの重みを 1/outdegree(v) とする．ここで，グした 100 個の対象ノードのランキングにおける同一ノードのoutdegree(v) はノード v の出次数である．

順位差，N はノードの数（本実験では 100）である．順位相関

5. 3 実 験 方 法

係数 ρ の値が 1 に近いほど，推定した評価値に基づくランキン

まず，グラフ全体に対して ObjectRank を計算し，各ノード

グは精度よく推定できていることを示している．

の正確な評価値を求めた．次に，評価値を推定する対象ノード

計算コストを評価するために，fetch 操作の回数と作成されたを選択するために，5. 1 節で示したデータセットから対象ノー局所グラフのサイズを用いた．大規模なグラフデータはリレー

ドをサンプリングした．本実験では，Author ラベルノードのショナルデータベースなどに保存されているため，fetch 操作

上位 100 件を選択した．そして，提案手法と比較手法を用いて，を行うにはデータベースにアクセスする必要がある．fetch 操
作の回数を減らすことで，データベースへのアクセスを減らせ（注 3）：http://arnetminer.org/（注 4）：データセットに出版年が不明な文献が含まれていたため，作成されたData Graph において，“Paper ラベルノード数” と “Year–Paper 間のエッ
ジ数” が一致していない．

るため，部分グラフの拡大における計算コストを小さくすることができる．また，局所グラフのサイズが小さいほど，評価値の推定の時に作成する遷移確率行列が小さくなる．そのため，

局所グラフのサイズが小さいほど，評価値の推定における計算コストを小さくすることができる．

5. 5 実 験 結 果
手法ごとの順位相関係数と平均 fetch 回数および平均局所グ
ラフサイズの比較結果を，それぞれ図 8 と図 9 に示す．提案手
法 1，提案手法 2，比較手法 2 については，順位相関係数が最大の時におけるエッジの重みの閾値の結果を用いて比較した．
凡例の括弧の中の値はエッジの重みの閾値である．
また，手法ごとの平均相対誤差と平均 fetch 回数の比較結果
を図 10 に示す．相対誤差は，サンプリングした 100 個のノードの正確な評価値と推定した評価値について，それぞれの総和が 1 になるように正規化してから計算した．

図 8 順位相関係数と平均 fetch 回数の比較

図 8 と図 10 より，3 種類の提案手法の中では，提案手法 1 の順位相関係数が最も大きく，平均相対誤差が最も小さいことが分かった．また，図 9 より，提案手法 1 は順位相関係数を維持しながら，平均局所グラフサイズを小さくできることが分かった．提案手法 2 では，Schema Graph のエッジラベルを考慮しているため，エッジの重みの閾値が決定すると部分グラフに追加するエッジラベルが決定される．提案手法 3 では，Schema

Graph のエッジラベルに基づいて，確率的に部分グラフを拡大している．一方，提案手法 1 では，Data Graph におけるエッジの重みを考慮しており，重みが閾値以上であるエッジだけを部分グラフに追加する．そのため，閾値を適切に設定すること
で，評価値の推定に適した局所グラフを作成することができた

図 9 順位相関係数と平均局所グラフサイズの比較と考えられる．
また，提案手法 1 は，比較手法 1 と比較手法 2 と比較して，順位相関係数の大きさと平均 fetch 回数が同程度であるが，平均局所グラフサイズが小さいことが分かった．提案手法 1 は，

Data Graph におけるエッジの重みが閾値以上のエッジだけを追加していくことで部分グラフを拡大していく．すなわち，この結果は，提案手法 1 は評価値の推定に不要なエッジとノードを追加せずに，局所グラフを作成することができることを示していると考えられる．比較手法 2 も Data Graph におけるエッジの重みを考慮しているが，出次数の逆数をエッジの重みとして用いているだけで，エッジラベルを考慮していない．そのため，正確なエッジの重みを考慮できず，評価値の推定に不要な

図 10

平均相対誤差と平均 fetch 回数の比較

ノードとエッジも部分グラフに追加してしまったと考えられる．
さらに，提案手法 1 は，Chen らの手法と比較して，ほぼ同

6. まとめと今後の課題

じ平均 fetch 回数であるが，順位相関係数と平均相対誤差，平均局所グラフの点で優れていた．Chen らの手法は，影響力を入次数で割った値が閾値以上である境界ノードにエッジを張っている全てのノードを部分グラフに追加する．一方，提案手法

1 は，Data Graph におけるエッジの重みを考慮し，評価値の推定に不要なエッジとノードを部分グラフに追加せずに，局所グラフを作成できる．そのため，提案手法 1 の局所グラフサイ
ズは，Chen らの手法よりも小さくなったと考えられる．また，提案手法 1 は，Chen らの手法より局所グラフサイズが小さいにもかかわらず精度が向上していた．これより，境界ノードの展開時に全てのエッジを追加するのではなく，追加するエッジを適切に選択することが重要であると考えられる．

本稿では，局所グラフを用いた ObjectRank の推定手法を提案した．提案手法では，対象ノードから，エッジの重みを考慮して部分グラフを拡大し，局所グラフを作成した．作成した局
所グラフを用いて ObjectRank を計算することで，対象ノードの評価値を推定した．評価実験では，提案手法は比較手法と比較して，計算コストを抑えつつ，精度を維持することができた．
今後の課題として，境界ノードの評価値の推定方法の改善が挙げられる．今回の評価実験では，Chen らの手法を参考にした方法で評価値を推定した．そのため，ObjectRank に適した評価値の推定手法を提案することで，推定の精度を向上させることができると考えられる．

謝辞 本研究の一部は，科学研究費補助金・若手 B(23700102)
による．
文

献

[1] Serge Abiteboul, Mihai Preda, and Gregory Cobena. Adaptive on-line page importance computation. In World Wide
Web Conference Series, pages 280–290, 2003.
[2] Andrey Balmin, Vagelis Hristidis, and Yannis Papakonstantinou. ObjectRank: Authority-Based Keyword Searchin Databases. In Very Large Data Bases, pages 564–575,
2004.
[3] Andrei Z. Broder, Ronny Lempel, Farzin Maghoul, andJan O. Pedersen. Eﬃcient PageRank approximation via
graph aggregation. Information Retrieval, 9:123–138, 2006.
[4] Yen-Yu Chen, Qingqing Gan, and Torsten Suel. Local methods for estimating pagerank values. In International Conference on Information and Knowledge Management, pages
381–389, 2004.
[5] Jason V. Davis and Inderjit S. Dhillon. Estimating the
global pagerank of web communities. In Knowledge Discovery and Data Mining, pages 116–125, 2006.
[6] Nicolas Neubauer, Robert Wetzker, and Klaus Obermayer.
Tag spam creates large non-giant connected components. In
Adversarial Information Retrieval on the Web, pages 49–52,
2009.
[7] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry
Winograd. The pagerank citation ranking: Bringing orderto the web. Technical Report 1999-66, Stanford InfoLab,
November 1999.
[8] Yizhou Sun, Jiawei Han, Peixiang Zhao, Zhijun Yin, Hong
Cheng, and Tianyi Wu. RankClus: integrating clusteringwith ranking for heterogeneous information network analysis. In Extending Database Technology, pages 565–576,
2009.
[9] Jie Tang, Limin Yao, Duo Zhang, and Jing Zhang. A combination approach to web user proﬁling. ACM TKDD, 5(1):1–
44, 2010.
[10] Jie Tang, Duo Zhang, and Limin Yao. Social network extraction of academic researchers. In ICDM’07, pages 292–
301, 2007.
[11] Jie Tang, Jing Zhang, Ruoming Jin, Zi Yang, Keke Cai,
Li Zhang, and Zhong Su. Topic level expertise searchover heterogeneous networks. Machine Learning Journal,82(2):211–237, 2011.
[12] Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, andZhong Su. Arnetminer: Extraction and mining of academic
social networks. In KDD’08, pages 990–998, 2008.
[13] Andrea Vattani, Deepayan Chakrabarti, and Maxim Gurevich. Preserving personalized pagerank in subgraphs. In
International Conference on Machine Learning, pages 793–
800, 2011.
[14] Yao Wu and Louiqa Raschid. ApproxRank: Estimating
Rank for a Subgraph,. In International Conference on Data
Engineering, pages 54–65, 2009.
[15] Gui-Rong Xue, Hua-Jun Zeng, Zheng Chen, Wei-Ying Ma,
Hong-Jiang Zhang, and Chao-Jun Lu. Implicit link analysis for small web search. In Research and Development inInformation Retrieval, pages 56–63, 2003.
[16] 山口祐人，天笠俊之，高橋翼，北川博之. 情報伝搬を考慮したグラフ分析による Twitter ユーザランキング手法. 情報処理学会
論文誌データベース, 4:142–157, 2011.