DEIM Forum 2017 E8-4

ラベル付き有向グラフにおける部分グラフ同型問題を解くための外部記憶アルゴリズム
王

志華†

鈴木

伸崇††

† 筑波大学大学院 図書館情報メディア研究科 〒 305-8550 茨城県つくば市春日 1-2†† 筑波大学 図書館情報メディア系 〒 305-8550 茨城県つくば市春日 1-2
E-mail: †{s1521649,nsuzuki}@slis.tsukuba.ac.jp
あらまし

本稿では，サイズが大きく全体を主記憶上で処理できないグラフデータに対応した部分グラフ同型問題を解くためのアルゴリズムを提案した．提案アルゴリズムは，二つのアルゴリズム（アルゴリズム１，アルゴリズム２）として構成する．アルゴリズム１では，データグラフを先頭から一部分ずつ主記憶に読み込み，パターングラフとマッ
チングを行い，完全解と部分解を求める．アルゴリズム２では，アルゴリズム１で得られた部分解に対して，部分解がなくなるまで「拡大」操作を行う．
「拡大」操作の後，完全解になったら出力し，完全解にならなかったグラフは削除する．評価実験を行い，概ね所望の効率でアルゴリズムが動作することが分かった．
キーワード

部分グラフ同型問題，外部記憶アルゴリズム，RDF

1. は じ め にの外部記憶アルゴリズムとしては [15] がある．しかし，このアルゴリズムはラベル無し単純グラフを対象としており，I/O コ

グラフとは，人 ，モノ，場所などの多様な情報のつながりをストがパターングラフのサイズに関して指数的に増加する．一表現するデータ構造である．グラフは，データおよびデータ同方，本アルゴリズムはラベル付きグラフを対象としており，I/O士の関連性をそれぞれ「ノード」 と「エッジ」で表現するデー

コストはパターングラフのサイズに関して線形である．グラフ

タ構造を持ち，このデータ構造は Web ページのリンク関係やに関する他の外部記憶アルゴリズムとしては，グラフの強連結

SNS の交友関係，商品の購買関係，交差点と道路の接続関係な成分を求めるもの [10]，到達可能性を判定するもの [11]，三角

ど私たちの周りに多く存在している．

形分割問題を解くもの [12] がある．

部分グラフ同型問題（subgraph isomorphism）とは，発見

そこで本稿では，サイズが大きく全体を主記憶上で処理できしたいパターンを定義したグラフ（以下，パターングラフ）とないグラフデータに対応した部分グラフ同型問題を解くための探索対象のグラフ（以下，データグラフ）が与えられたときに，手法を提案する．提案手法は，まず全てのデータグラフをファ

データグラフに含まれるパターングラフと同型の部分グラフをイルとして外部記憶に格納し，一部ずつ主記憶に読み込み，検全て発見する問題である. 部分グラフ同型問題の判定は，グラ索や計算などの処理を行う．具体的には，次のような二つのア

フに関する問題の中で最も基本的な問題の一つであり，画像にルゴリズムとして構成する．アルゴリズム１では（図 1），デー

おける特徴量抽出 [1]，化学式における類似構造の検出 [2] など

タグラフを先頭から |S1 | 大きさのデータを一部分ずつ主記憶に様々な分野に応用できる．

読み込み，パターングラフとマッチングを行い，完全解と部分部分グラフ同型問題における先行研究としては，多くのアル解を求める．ここで，パターングラフと同じ形になるグラフはゴリズムがある．具体的には，Ullmann [3] の手法は部分グラ完全解と呼び，パターングラフと部分的に一致し，現時点で完フ同型問題を解くための最初の手法であり，検索範囲を減少さ全解になるか否か不明のグラフは部分解と呼ぶ．また，S1 とせる手続きであるバックトラック法を使って部分グラフ同型判

S2 はそれぞれ読み込んだデータグラフと部分解を格納する主記定を行う．近年，Ullmann の手法に基づいて発展した VF2 [4]，

憶上の領域である．アルゴリズム２では（図 2），アルゴリズム

QuickSI [5]， GraphQL [6]， GADDI [7]， SPath [8] のアルゴ１で得られた部分解に対して，部分解がなくなるまで「拡大」

リズムもある．これらのアルゴリズムを比較する先行研究 [9]操作を行う．ここで，パターングラフとデータグラフのノード

では，ラベル付き無向グラフを対象として共用のフレームワーとエッジを参照し，部分解において不明だったノードとエッジ

クを作って，各アルゴリズムを比較している．

の情報を追加するという処理を「拡大」操作と呼ぶ．
「拡大」操

これまで提案されてきた部分グラフ同型問題を解くためのア
ルゴリズムの多くはデータを主記憶に格納し処理することを前提としており，データが主記憶に収まらない場合には適用困難である．主記憶のサイズを超えるデータを効率良く処理するア
ルゴリズムとして，外部記憶アルゴリズム (external memoryalgorithm) が考えられている．部分グラフ同型問題を解くため

作の後，完全解になったら出力し，完全解にならなかったグラ
フは削除する．

2. 諸 定 義
本章では，グラフと部分グラフ同型問題に関する定義について述べる．

データグラフ(外部記憶)

r

Aさん

主記憶

r

部分解を格納

読み込んだ
部分グラフ

r 友達申請

r
Dさん

c

近況

c コメントr

動画s

解と成り得る「部分解」
集合u アップロード

u
c

Cさん

S2

S1

Bさん

r

u

写真

s

s シェア

Eさん

(b) ラベルの意味(a) Facebook の友人関係

出力

図 3: グラフの例

完全解集合

図 1: アルゴリズム１の概要

データグラフ
(外部記憶)

主記憶

S2

S1

ノードとエッジの情報を追加 「部分解」

読み込んだ
部分グラフ

部分解を
残す

集合

出力

r

C さん

B さん

r

A さん

C さん

r

B さん

D さん

r

E さん

D さん

r

B さん

B さん

u

動画

C さん

c

動画

D さん

s

写真

E さん

s

動画

E さん

u

近況

図 4: グラフを格納するファイルの例

削除

完全解
集合

A さん

マッチできなかった

2. 2 部分グラフ同型問題
パターングラフを P = (Vp , Ep )，データグラフを G = (V, E)

図 2: アルゴリズム 2 の概要と表す．グラフデータにおける部分グラフ同型問題を次のように定義する．もし∀u → u′ ∈ Ep ⇒ ∃f (u) → f (u′ ) ∈ E
l

2. 1 グラフの概要

l

ラベル付き有向グラフ (以下，単にグラフ) を G = (V, E) とという条件を満たす単射 f : Vp → V が存在するならば，P は表す．ここで V はノードの集合，E はラベル付き有向エッジ

G において部分グラフ同型であるという．部分グラフ同型問題(以下，単にエッジ) の集合である．エッジは両端にノードを持とは，上記の条件を満たす単射をすべて求める問題である．

ち，それらを端点と呼ぶが，両端のノードは同じ場合もある．
ノード v ∈ V を始点とし，ノード v ′ ∈ V を終点とする有向エッジ e ∈ E のラベルが l であるとき，e = v → v ′ （または
l

′

′

l

3. 提 案 手 法
本研究のアルゴリズムでは，サイズが大きく全体を主記憶上

e=v ←− v ）と表す．このようにエッジ e で v, v が結ばれていで処理できないグラフデータに対応した，部分グラフ同型問題

るとき，v と v ′ は隣接していると言い，エッジ e は v と v ′ にを解くためのアルゴリズムを提案する．提案アルゴリズムでは，接続していると言う．ノードに接続しているエッジのうち，そファイルとして外部記憶に格納されたグラフデータを一部ずつのノードを終点とするエッジを入力エッジ，始点とするエッジ

主記憶に読み込み，解を発見するための処理を行う．提案アルを出力エッジと呼ぶ．v ∈ V の入力辺のラベル集合と出力辺のゴリズムは，二つのアルゴリズムとして構成する．本章では，ラベル集合をそれぞれ Lin (v)，Lout (v) と表す．

この二つのアルゴリズムについて述べる．

′

′

′

′⊂

また，グラフ G = (V, E) と G = (V , E ) に対して，V =V′
かつ E ′ ⊂=E を満たす時，G は G の部分グラフであるという．

3. 1 準備

3. 1. 1 前 処 理

例として，図 3 に Facebook の友人関係を表すグラフ示す．

本アルゴリズムの処理では，グラフの各ノードに対して，出このグラフにおいて，各ノードは個々の人間や活動プラン，有力エッジ情報と入力エッジ情報両方を確認できる必要があるた

向エッジはそれらの関係や行動を表し，エッジにつけられたラめ，そのようなグラフデータを前処理で用意する．

ベルは始点を主語，終点を目的語とする動詞である．

パターングラフとデータグラフ両方とも，出力辺ファイルとグラフをファイルに格納する方法いくつか考えられるが，本

入力辺ファイル二つのファイルを用意する．出力辺ファイルは，

稿では，グラフを格納するファイルとして，各行に 1 つのエッ

「始点」
「端点を結ぶエッジラベル」「終点」の順で 1 行が構成さジが書かれているものを考える．この記法では，各行が「始点」れているファイルである．入力辺ファイルは，出力辺ファイル「端点を結ぶエッジのラベル」「終点」の 3 つで構成されている．

の「終点」と「始点」を逆にして，「終点」「端点を結ぶエッジの

図 3 のグラフをこの記法で表現した例を図 4 に示す．

ラベル」
「始点」の順で各行が構成されるファイルである．ノードをシーケンシャルな読み込みで特定するために，出力辺ファイルと入力辺ファイルいずれも左側のノードのアルファベット

は S1 を参照することで確認できる．
図 7 で は ，Vin=

{v1 , v2 , v6 } の よ う な ノ ー ド は順に外部ソートする．出力辺ファイルと入力辺ファイル二つの内 部 ノ ー ド で あ る ．こ れ ら の 内 部 ノ ー ド に よって ，ファイルを並列して読み込むことによって，一部分ずつ読み込{(v2 r v1 ), (v2 c v3 ), (v5 r v6 ), (v6 s v1 ), (v7 r v6 )} のようんでも，各ノードの出力エッジ情報と入力エッジ情報を容易にな情報が実際に得られる．

確認できる．

b ) 境界ノード

例でこれらの操作を示す．グラフ（図 5）に対して，出力辺

S1 に読み込まれたデータの境界にあるノードのことである．

ファイルと入力辺ファイルは図 6 のようになる．例えば，ノー

つまり，S1 の外にあるが，少なくとも S1 の中にある内部ノー

ド v1 に対して，出力辺ファイルと入力辺ファイルを同時に読ドと隣接するノードである．それ以外，外部ノード（後述）まll

み込む際に，一行目を読み込むだけで，v1 → v2 と v1 ←− v3 のたは同じ境界ノード同士と隣接する可能性がある．境界ノード

ような情報が得られる．本アルゴリズムの処理では，主記憶の集合は Vbn で表す．境界ノードは内部ノードと隣接している場

サイズを超えないように，一度に読み込む行数を制限するが，合だけ，接続しているエッジの情報が確認できる．

この方法で，主記憶に読み込まれるデータのサイズが制限されても，各ノードに対する入出力エッジを得ることができる．

㼂㻝{v3 , v5 , v7 } の よ う な ノ ー ド はc ) 外部ノード

㼂㻞U

S1 に読み込まれていないノードのことである．つまり， S1

㼂㻤

U

X

の外にあり，かつ，S1 の中にある内部ノードと隣接しないノー

F
F

㼂㻟

=

{(v2 c v3 ), (v6 s v1 ), (v7 r v6 )} のような情報が得られる．

UU

図 7 で は ，Vbn

境 界 ノ ー ド で あ る ．こ れ ら の 境 界 ノ ー ド に よって ，

㼂㻠

U
V

X

㼂㻡

V

㼂㻣

㼂㻢

ドである．境界ノードまたは外部ノード同士と隣接し，vout で表す．解のマッチングにおいて，境界ノードまでパターングラ
フとマッチングできるが，これ以上の情報は現時点のデータで確認できないため，未知のラベルを x にして，未知のノードを

図 5: グラフ

vout にしておく．
図 7 では，v4 のようなノードは外部ノードである．v4 と v5
v1 r v3

v1 r v2

v2 r v1

v2 r v3

v2 u v4

v2 r v8

v3 r v2

v3 r v1のエッジ情報は，{(v5 x vout )} のように記述する．
䝕䞊䝍䜾䝷䝣
㻔እ㒊グ᠈㻕

ǀϰ

v3 c v4

v4 c v3ǀϯ

v6 s v4

v4 s v6Đ

v6 u v5

v4 u v2ƌ

v6 s v7

v5 u v6

v8 r v2

v6 r v8

v8 r v6

v7 s v6

v8 c v7

v7 c v8(a) 出力辺ファイル(b) 入力辺ファイル

図 6: アルゴリズムの入力データ

^ϭ

Đ
Ƶ

ǀϱ

ǀϮ

ǀϭ
Ɛ

ƌ

ǀϲ
ƌ

ǀϳ

図 7: ノードの分類

3. 2 アルゴリズム１
本節では，アルゴリズム１の詳細及びその動作例を示す．ア3. 1. 2 基本的な考え方

ルゴリズム１では，データグラフを先頭から K ずつ主記憶の本アルゴリズムでは，データグラフを外部記憶から主記憶に

S1 に読み込み，パターングラフとマッチングを行い，完全解一部分ずつ読み込む．この主記憶上の領域を S1 とする．各エッと部分解を求める．ここで，パターングラフと同じ形になるグ

ジと接続している両端のノードについて，S1 への読み込まれ方

ラフは完全解と呼び，パターングラフと部分的に一致し，現時に応じて三種類に分けてアルゴリズムの処理を考える．例（図点で完全解になるか否か不明のグラフは部分解と呼ぶ．マッチ

7）では，現在外部記憶から主記憶に読み込まれた部分は S1 でングリスト M と M ′ をペアとして完全解と部分解を格納する．

示された上から二番目の領域である．

また，S2 は部分解を格納する主記憶上の領域である．

a ) 内部ノード

3. 2. 1 アルゴリズム１の詳細

S1 に読み込まれたノードのことである．境界ノード（後述）

まず Algorithm 1 でアルゴリズム１の全体の流れを示す．3

または同じ内部ノード同士と隣接する可能性がある．内部ノー

行目では，主記憶のサイズを超えないように，データグラフをド集合は Vin で表す．内部ノードと接続しているエッジ及び隣読み込む際に，読み込む行数を K 行に制限し，「一部分ずつ読接しているノードは同じ行で読み込まれるので，これらの情報み込む」を実現する．5 行目内部ノード集合を求める．6 行目で

は，GetBNnodes 関数で境界ノード集合を求める．その詳細はペアを M に格納する．v に関するラベルとノードの情報を M ′Algorithm 2 で示す．本アルゴリズムは，パターングラフの一に格納する．

つ目のノード（u1 とする）から操作を始めるため，7〜10 行目
では，u1 とマッチングする可能性があるノード v が発見できた
ら，新しい M を作成し，ノードペア (u1 , v) を M に追加してから，次の SubgraphSearch で照合を開始する．SubgraphSearchの詳細は Algorithm 3 で示す．

Algorithm 3 SubgraphSearch
入力: パターングラフ P = (VP , K, EP )，データグラフ G = (V, E)
出力: 完全解の M と M ′begin
1: if M の中に外部ノード vout がない，かつ，M ′ の中にラベル x がない then

Algorithm 1 アルゴリズム１全体の流れ

2:

入力: パターングラフ P = (VP , K, EP )，データグラフ G = (V, E)

3: else if M の中に外部ノード vout がある，または，M ′ の中にラベ

出力: 完全解の M と M ′M と M ′ を出力
ル x がある then

begin

4:

M と M ′ を S2 に格納する

1: S2 = ∅5: else2: while G の終端まで次の操作を行う do6:

まだマッチングされていない u ∈ Vp を一つ選ぶ

3:

G ファイルの K 行を S1 に読み込む

7:

for each v ∈ Vin do

4:

Vin = V (S1 )8:5:

Vbn = GetBNnodes(S1 , P )6:for each v ∈ V (S1 ) do′
は空
if IsJoinable_I(P, S1 , M.M ′ , u, v) の戻り値 Mtmp

ではない thenl9:′(u, v) を M に，v → v ′ ∈ Mtmp
を M ′ に追加する

7:

if Lout (v) = Lout (u1 ) or Lin (v) = Lin (u1 ) then10:

SubgraphSearch(P, S1 , M, M ′ )8:

新しい M を作成し，(u1 , v) を M に追加する

11:′を M ′ から削除
(u, v) を M から，v → v ′ ∈ Mtmp

9:M′ = ∅

12:

10:

SubgraphSearch(P, S1 , M, M ′ )13:lfor each v ∈ Vbn do′
if IsJoinable_B(P, S1 , M.M ′ , u, v) の戻り値 Mtmp
は空endではない thenlx′′(u, v) を M に，v → v ′ ∈ Mtmp
または v → v ′ ∈ Mtmp

14:を M ′ に追加する

Algorithm 2 GetBNnodes

15:

SubgraphSearch(P, S1 , M, M ′ )入力: パターングラフ P = (VP , K, EP )，データグラフ G = (V, E)

16:

′
′
(u, v) を M から，v → v ′ ∈ Mtmp
または v → v ′ ∈ Mtmplを M ′ から削除

出力: Vbn′
値 Mtmpは空ではない thenl

1: for each v → v ′ ∈ V (S1 ) do2:

if v ′ ∈ V (S1 ) but v ∈/ V (S1 ) thenv を Vbn に追加する

3:
4:

else if v ∈ V (S1 ) but v ′ ∈/ V (S1 ) thenv ′ を Vbn に追加する

5:

if v = vout かつIsJoinable_O(P, S1 , M.M ′ , u, v) の戻り

17:

begin

x

x

18:

′
(u, v) を M に，v → v ′ ∈ Mtmp
を M ′ に追加する

19:

SubgraphSearch(P, S1 , M, M ′ )20:′(u, v) を M に，v → v ′ ∈ Mtmp
を M ′ から削除

xend

6: return Vbn

end

IsJoinable_I では，u の出力エッジと入力エッジそれぞれに対して，マッチングできる内部ノード v を探索する．内部ノー

SubgraphSearch では，1〜4 行目は完全解と部分解を判断す

ドと隣接するノードは境界ノードと内部ノードなので，ラベルる．完全解の場合，M と M ′ は vout と x を含まない．そこで，情報は確認できる．出力エッジ u → u′ ∈ Ep と (u′ , v ′ ) ∈ M

1〜2 行目の条件を満たす場合，M と M ′ を出力する．3〜4 行に対して，u にマッチする適切な v 発見をできたら．v に関す′

l目の条件を満たす場合，部分解になるので，M と M を主記′
る出力エッジとノードの情報 (v l v ′ ) を Mtmpに追加する．同

憶の S2 に残し，次のアルゴリズム２で「拡大」操作を行う．6

様に，入力エッジ u′ → u ∈ Ep と (u′ , v ′ ) ∈ M に対して，u に行目でパターングラフのまだマッチング操作していないノードマッチする適切な v を発見できたら．v に関する入力エッジと

u を一つ選択する．7〜20 行目では，データグラフのノードと′ノードの情報 (v ′ l v) を Mtmpに追加する．

エッジの照合を行う．データグラフのノードは内部ノード，境界lIsJoinable_B では，u の出力エッジと入力エッジそれぞれ

ノードと外部ノード三つの種類があるため，パターングラフとに対して，マッチングできる境界ノード v を探索する．境界のマッチング操作をそれぞれ行う．8〜11 行目は内部ノードに対ノードと隣接するノードは内部ノード，外部ノードまたは境界する処理である．IsJoinable_I の詳細は Algorithm 4 で示す．

ノードであるが，内部ノードと隣接する場合だけラベル情報

12〜16 行目は境界ノードに対する処理である．IsJoinable_Bは確認できる．ラベル情報が確認できる場合，3〜5 行目と 12の詳細は Algorithm 5 で示す．17〜20 行目は外部ノードに対〜14 行目のように IsJoinable_I と同じ操作を行う．ラベル情する処理である．IsJoinable_O の詳細は Algorithm 6 で示す．

報が確認できない場合，6〜8 行目と 15〜17 行目で示すよう選択された u に対して，これらの三つ関数では，適切な v を決に，ラベルを x にする（x は未知のラベルを表す）．出力エッ定する．パターングラフとデータグラフのマッチするノードのジ u → u′ ∈ Ep に対して，u にマッチする適切な v を発見できl′
たら．v に関する出力エッジとノードの情報 (v x v ′ ) を Mtmp′l

応する．外部ノードは境界ノードまたは外部ノードと隣接するに追加する．同様に，入力エッジ u → u ∈ Ep の場合，u にので，いずれの場合もラベル情報は確認できない．3〜5 行目マッチする適切な v を発見できたら．v に関するラベルとノーと 9〜11 行目で示すように，エッジのラベルを x にする．出力′
ドの情報 (v ′ x v) を Mtmpに追加する．

エッジ u → u′ ∈ Ep に対して，u にマッチする適切な v を発l

見できたら．v に関する出力エッジとノードの情報 (v x v ′ ) を

Algorithm 4 IsJoinable_I′
Mtmpに追加する．同様に，入力エッジ u′ → u ∈ Ep の場合，

入力: パターングラフ P = (VP , K, EP )，データグラフ G = (V, E)，

u にマッチする適切な v を発見できたら．v に関するラベルとl

ノード u ∈ Vp ，ノード y ∈ V (S1 )′
出力: Mtmp

begin

Algorithm 6 IsJoinable_O′
1: Mtmp=∅l

2: for each 出力エッジ u → u′ ∈ Ep ，(u′ , v ′ ) ∈ M do
3:l

if v ′ ∈ Vin ∪ Vbn ，かつ v → v ′ ∈ E(S1 ) thenl4:′v → v ′ を Mtmp
に入れる

5:

continue6:l

2: for each 出力エッジ u → u′ ∈ Ep ，(u′ , v ′ ) ∈ M do

return ∅ll

if v ′ ∈ Vin ∪ Vbn ，かつ v ′ → v ∈ E(S1 ) thenl′v ′ → v を Mtmp
に入れる

10:

continue

11:
12:

3:

l

if v ′ ∈ Vbn ∪ {vout }，かつ v → v ′ ∈ E(S1 ) thenx′v → v ′ を Mtmp
に追加する

4:

continue

5:
6:

else
return ∅

7:

else

l

8: for each 入力エッジ u′ → u ∈ Ep ，(u′ , v ′ ) ∈ M do

return ∅13:

ノード u ∈ Vp ，ノード y ∈ V (S1 )′
出力: Mtmp′=∅
1: Mtmp

8: for each 入力エッジ u′ → u ∈ Ep ，(u′ , v ′ ) ∈ M do
9:

入力: パターングラフ P = (VP , K, EP )，データグラフ G = (V, E)，

begin

else

7:

′
ノードの情報 (v ′ x v) を Mtmpに追加する．

9:′
14: return Mtmpl

if v ′ ∈ Vbn ∪ {vout }，かつ v ′ → v ∈ E(S1 ) thenx′v ′ → v を Mtmp
に追加する

10:

end

continue

11:
12:

else
return ∅13:

Algorithm 5 IsJoinable_B
入力: パターングラフ P = (VP , K, EP )，データグラフ G = (V, E)，′
14: return Mtmp

end

ノード u ∈ Vp ，ノード y ∈ V (S1 )′
出力: Mtmp

3. 2. 2 アルゴリズム１の動作例

begin

本節では，アルゴリズム１の動作例を示す（図 8）．パター′
1: Mtmp=∅l

2: for each 出力エッジ u → u′ ∈ Ep ，(u′ , v ′ ) ∈ M do
3:l

if v ′ ∈ Vin ，かつ v → v ′ ∈ E(S1 ) then′v → v ′ を Mtmpに追加する

された二番目の領域では，v4 と v6 は u1 と同じ入力ラベルを

continue

持っているので，その領域が主記憶に読み込まれてからマッチ

l

4:
5:

ングラフ P とデータグラフ G に対して，P のノード u1 とマッ
チングできるノードが発見できたら, 照合を開始する．S1 で示

6:else if v ′ ∈ Vbn ∪ {vout } then7:′v → v ′ を Mtmpに追加する

M1 = {(u1 , v4 )} と M2 = {(u1 , v6 )} である．この時 M ′ はま

8:continueだ空であるが，SubgraphSearch で M ′ が作成される．S1 に読

9:

x

else

み込まれたグラフデータにおいて，内部ノード集合 Vin と境界

return ∅10:l

11: for each 入力エッジ u′ → u ∈ Ep ，(u′ , v ′ ) ∈ M do
12:
13:

′ l
if
in ，かつ v → v ∈ E(S1 ) thenl′′v → v を Mtmp に追加する

v′ ∈ V

continue

14:
15:

else if v ′ ∈ Vbn ∪ {vout } then16:′v ′ → v を Mtmp
に追加する

17:

continue

18:

x

else
return ∅19:

ング操作を始める．ここでは，新しい M を二つを作成する．

′
20: return Mtmp

end

ノード集合 Vbn を作成する．ここで，Vin = {v1 , v3 , v4 , v5 , v6 }，Vbn = {v2 , v7 , v10 } である．S1 に読み込まれたデータは
r

s

c

r

r

u

である．M1 の場合，パターングラフの各ノードとマッチング
できたノードは全て S1 にあるので，最後に完全解になり，M1′llとペアで出力する．M2 の場合，v5 → v6 と v7 → v6 は得られ
たたが，それ以外の情報は現在読み込まれたデータだけで判断できないので，まだ不明のラベルとノードをそれぞれ x と voutにして，M2′ とペアで部分解として主記憶の S2 に残す．完全解(M1 , M1′ ) と部分解 (M2 , M2′ ) は次のように記述する．
IsJoinable_O では，u の出力エッジと入力エッジを別々に対r{v1 → v4 , v1 → v10 , v2 → v3 , v2 → v4 , v5 → v6 , v5 → v7 , v7 → v6 }

^ϭ

ǀϵ Ɛ
ǀϮ
䝟䝍䞊䞁W

Ƶϭ

ㄞ䜏㎸䜐

ǀϯ Ƶ

ǀϰ

^ϭ

ƌ

ƌ

ƵϮ

Ƶϯ

Ɛ

Đ

ǀϭϬ

ǀϭ ǀϱ

ƌ

Ƶ

Ƶϰ

ƌ

ǀϲ

ƌ

ǀϭϭ

ƌ

ǀϭϮ

場合，M と M ′ には，vout と x が含まないため，この条件をǀϮƌ ǀϮ Đ ď

ǀϴ

ǀϳ Đ

Đ

ƌ

で，
「拡大」したグラフは完全解であるかを判断する．完全解の୺グ᠈䝕䞊䝍䜾䝷䝣';እ㒊グ᠈Ϳ

᏶඲ゎ㞟ྜ ฟຊƐ㒊ศゎ㞟ྜ^Ϯ

Đ

ǀϰ ǀϯ

ǀϭϯ

Ě
ǀϰ Ă Đǀϯ Ƶƌǀϰ ƌ ǀϭ ǀϱ ƌ ǀϲ
ǀƐ ϭ
ǀϱ
ǀϭϬ

ǀϮ

ƌ

͘͘͘

ƌ

ǀϳ

ǆ

ǀϯ

ǀŽƵƚ

ǀϭ

満たす場合は完全解になるので出力する．そうでない場合，引ǀϳ

き続き 8〜14 行目の「拡大」を行う．8〜14 行目では，S2 にある部分解を記述する M と M ′ に対して，その中にある外部ṧ䛩

ノード vout と不明なラベル x 情報を適切な v と l に置き換えǀϳ

る．具体的には，9〜11 行目では，もし M において u とペア

ƌである v が vout であり，v と隣接する v ′ が vout でない場合，ǀϱ ƌ ǀϲ

新しく S1 に読み込まれたグラフデータの中で，vout と置き換
図 8: アルゴリズム１動作例

えるノードを探索する．もし v ′′ → v ′ のようなエッジ発見できl

たら，v ′′ で v を置き換えて，v ′′ → v で v → v ′ を置き換える．
lx

12〜14 行目は，もし M において u とペアである v が vout で完全解

M1 ={(u1 , v4 )，(u2 , v1 )，(u3 , v2 )，(u4 , v3 )}ないが，v と隣接する v ′ が vout である場合に対応する．もしM1′ ={(v1 r v4 )，(v2 r v4 )，(v2 c v3 )}v → v ′′ のようなエッジ発見できたら，(u′ v ′′ ) で (u′ v ′ ) を置き
l

換えて，v → v ′′ で v → v ′ を置き換える．最後に，
「拡大」の
l

部分解

x

後，完全解にならなかった M と M ′ を削除する．

M2 ={(u1 , v6 )，(u2 , v5 )，(u3 , v7 )，(u4 , vout )}M2′ ={(v5 r v6 )，(v7 r v6 )，(v7 x vout )}3. 3. 2 アルゴリズム 2 の動作例

3. 3 アルゴリズム 2

本節では，アルゴリズム 2 の動作例を示す（図 9）．ここで，本節では，アルゴリズム 2 の詳細及び動作例を述べる．アルアルゴリズム 1 の動作例で得られた部分解 (M2 , M2′ ) に対して，

ゴリズム 2 では，アルゴリズム１で得られた部分解に対して， 「拡大」操作を行う．データグラフ G を先頭から S1 に読み込
む．先頭の領域が主記憶の S1 に読み込まれることで，以下の部分解がなくなるまで「拡大」操作を行う．
ノードとエッジの情報が得られる．

3. 3. 1 アルゴリズム 2 の詳細
Algorithm 7 でアルゴリズム 2 の「拡大」操作の詳細を示す．

c

r

u

r

c

s

{v2 → v3 ，v2 → v4 ，v5 → v7 ，v7 → v6 ，v7 → v8 ，v9 → v8 }アルゴリズム 2 では，データグラフを先頭から一部分ずつを読

x

これらのノードとエッジの中で v7 → vout と置き換えること

Algorithm 7 アルゴリズム 2の可能な情報を探索する．具体的な操作は Algorithm 7 の 8〜

入力: パターングラフ P = (VP , K, EP )，データグラフ G = (V, E)，

14 行目を参照する．パターングラフの u3 → u4 に対して，(u3S2 に格納されている M と M ′c，v7 ) が M に含まれている．しかも，現在の部分解の M ′ に

出力: 完全解の M と M ′xv7 → vout も含まれているので，12〜14 行目を参照する．こ

begin

c

1: 「拡大」できる部分解がなくなるまで，2〜15 行目の操作を行う

こで，v7 → v8 が発見できたため，(u4 ，vout ) を (u4 ，v8 ) で置

2: while G の終端まで次の操作を行う do

き換えて，v7 → v8 で v7 → vout を置き換える．以上で，部分

c

x

3:

G ファイルの K 行を S1 に読み込む

解 (M2 ，M2′ ) に対する「拡大」操作を終了する．今回の例では，

4:for each (M, M ′ ) ∈ S2 do「拡大」後の部分解は完全解になったため，(M2 ，M2′ ) を完全解

if M の中に外部ノード vout

5:がない，かつ，M ′ の中にラベル x がない then

うに記述する．

M と M ′ を出力6:として出力する．
「拡大」前と「拡大」後の (M2 ，M2′ ) は次のよ

else

7:

，(u′ , v ′ ) ∈ M ，v ′9:

if (u, v) ∈ M ，v = vout

10:l，v ′′ → v ′ ∈ E(S1 ) then(u, v) ∈ M を (u, v ′′ ) で置き換えるlv → v ′ ∈ M ′ を v ′′ → v で置き換える

else if (u, v) ∈ M ，v =| vout ，(u′ , v ′ ) ∈ M ，v ′ = vout

12:l，v → v ′′ ∈ E(S1 ) then
x

^ϭ
䝟䝍䞊䞁
W Ƶ
ϭ

ƌ

ƵϮ

Ƶϯ

Ɛ

Đ

ǀϭϬ

ƌ

ǀϭ ǀϱ

ƌ

Ƶϰ

Ɛ

ǀϭϯ

᏶඲ゎ㞟ྜ

ǀǀϰ
ϰ

ǀ

ď

ǀϭϮ

ǀϰ ǀ
ƌϯ

ǀϯ Ƶ ϳ
ƌ
ǀ
ǀϲ
ǀϱ

ǀϭ

ǀϱ

ϱ

ǀϭ
Đ

ǀϳ

ฟຊ

ǆ

ǀϳ

ƌ

ǀϲ

ǀŽƵƚ

ƌ

ƌ
ƌ

ǀ
ǀ ϳ

Đ

㒊ศゎ㞟ྜ^Ϯ

ǀϯ

ǀϴ

ǀϲ

ǀϱ

図 9: アルゴリズム 2 動作例

end

み込む．アルゴリズム 1 と同じく主記憶のサイズを超えない
ように，3 行目で読み込む行数を K 行に制限する．5，6 行目

ǀϴ
Đ

Đ

Ă

ƌ Ϯ Đ
ƌ

ǀϭϭ

Ϯ

ƌ

ǀϲ

ƌ

Ƶ

l

15: S2 に残った M と M ′ を削除

ǀ
ǀϮ

Ě

ǀϳ
ǀϯ Ƶ

ǀϰ

ƌ

ㄞ䜏㎸䜐

Đ

v → v ′ ∈ M ′ を v → v ′′ で置き換える

14:

ǀϴ

Đ

ƌ

^
ϭǀ Ɛ
ϵ

Ɛ

ǀϮ

͘͘͘

(u′ , v ′ ) ∈ M を (u′ , v ′′ ) で置き換える

13:

ǀϵ

=
| vout

x

11:

୺グ᠈

䝕䞊䝍䜾䝷䝣';እ㒊グ᠈Ϳ

lfor each u → u′ ∈ Ep do

8:

部分解「拡大」前M2 ={(u1 ，v6 )，(u2 ，v5 )，(u3 ，v7 )，(u4 ，vout )}⨨䛝᥮䛘䜛M2′ ={(v5 r v6 )，(v7 r v6 )，(v7 x vout )}部分解「拡大」後評価実験では，SP2 Bench による 559MB（n=5,000,000）から 5,644MB（n=50,000,000）まで 5 つのデータグラフを作成

M2 ={(u1 ，v6 )，(u2 ，v5 )，(u3 ，v7 )，(u4 ，v8 )}した．作成したデータグラフの詳細を表 1 に示す．

M2′ ={(v5 r v6 )，(v7 r v6 )，(v7 c v8 )}3. 4 I/O コスト

表 1: SP2 Bench で作成されたデータグラフ

提案アルゴリズムの I/O コストを考える．一般的な外部記憶

n データサイズ (MB)

エッジ数

アルゴリズムのモデルにしたがって，外部記憶と主記憶間では5,000,000

サイズ B のブロック毎にデータ転送を行うものとする [13]．

10,000,000

1,105 10,000,457

20,000,000

2,259 20,000,629

30,000,000

3,386 30,025,97850,000,000

5,644 50,042,632

まず，前処理の I/O コストを考える．前処理では，出力辺ファイルと入力辺ファイルの外部ソートを行うので，前処理のI/O コストは O(sort(|E|)) である．
次に，アルゴリズム本体（アルゴリズム１とアルゴリズム
２）の I/O コストを考える．まず，アルゴリズム１について，

Algorihtm 1 の 3 行目で K 行のデータを読み込んでいる．このサイズを S <= |S1 | とする．このとき，K 行読み込むための559

5,000,632

今回の実験では，エッジ数 3 本のパターングラフ（図 10）利用し，評価を行った．

I/O コストは O(S/B) なので，アルゴリズム１の I/O コスト
は次のようになる．

Editor

(
O

S |E|
·
B S

)

(
=O

|E|
B

)

editoreditor

JournalProceeding

次に，アルゴリズム２の I/O コストを考える．Algorithm 8

publisherの 3 行目に要する I/O コストは，グラフデータ全体を１回読み込むごとに，次の I/O コストを要する．

(
O

S |E|
·
B S

)

(
=O

|E|
B

Publisher)

図 10: パターングラフ

ここで，Algorithm 7 の 1 行目の「拡大」が繰り返される回数を考える．１回の「拡大」で少なくとも１つの辺が部分解に追加されるので，「拡大」は最大で |Ep | − 1 回繰り返される．よっ4. 2 評価実験の詳細て，アルゴリズム２の I/O コストは次のようになる．

評価実験を行った環境は以下の通りである．

(
O|E||Ep |B)

主記憶: 16GB RAM

以上から，アルゴリズム本体（アルゴリズム１およびアルゴ
リズム２）の I/O コストは次のようになる．

(
O|E||Ep |B

CPU: Intel Xeon E5-2623 v3 3.0GHz)

4. 評 価 実 験
本稿では，提案アルゴリズムを実装し，(1) 完全解と部分解の数，(2) 実行時間，(3) 主記憶使用量の 3 点を評価する．

OS: Linux CentOS 7 (64bit)
使用言語:

C++

主記憶について，最大使用量を ulimit コマンドで 4G に制限し，これを超えるサイズのファイルを処理可能か否かを確認した．生成した 5 つのデータグラフによる作成した入力ファイル（出力辺ファイルと入力辺ファイル）とエッジ数 3 本のパター
ングラフを用いて，以下の実験を行った．データグラフの読み
込む行数は 20 万行（K=200,000）とした．主記憶に読み込んだデータはそのままページキャッシュとして再利用することで

4. 1 評価用データ

次回以降 CPU からは高速に読み書きができるため，実行時間

評価実験では，SP2 Bench [14] を用いてデータグラフを作成に影響がある．このような状況を回避するために，$sudo sh

する．SP2 Bench は Notation3 形式のラベル付き有向グラフを-c "echo 3 > /proc/sys/vm/drop_caches"コマンドでページ生成するベンチマークソフトである．SP2 Bench によって，グキャッシュと Slab キャッシュの解放した後，データを読み込む．

ラフデータを作成する際に，n の値を指定することによって，任

まず，入力ファイルのサイズを変化させたときの部分解と完意のサイズのデータが作成できる．生成されるデータは，コン全解の数を集計した．その結果を図 11 に示す．この結果から，

ピュータサイエンス分野の書誌情報データベースである DBLP

入力ファイルのサイズを大きくすることで，部分解数と完全解のデータ構造に沿ったものである．そのため，生成されるファ数いずれも概ね線形に増加することが分かった．部分解と完全イルは論文や書籍，修士論文や博士論文，議事録などの書誌情解の数は主記憶使用量と関連するため，主記憶使用量も線形に報が格納されたグラフデータとなる．

増加することが推測できる．

とで，主記憶使用量は概ね線形に増加していることが分かった．
主記憶最大使用量を 4G に制限した状態で，少なくとも 11G のデータを処理可能であった．このことから，提案アルゴリズム

160000140000は主記憶使用量より大きいデータを処理可能であると言える．

解の数（個）

120000100000

ただし，主記憶使用量の増加を抑えるための更なる工夫も必要

80000と考えられる．

60000

40000

5. む す び

20000
0
0

1,000

2,000

3,000

4,000

5,000

6,000

7,000

8,000

9,000 10,000 11,000 12,000

本稿では，サイズが大きく全体を主記憶上で処理できないグ

入力ファイルのサイズ（MB）
部分解

完全解

ラフデータに対応した部分グラフ同型問題を解くためのアルゴ
リズムを提案した．
図 11: 部分解と完全解の数

今後の課題として，主記憶使用量を抑える手法を考案する．
主記憶使用量を抑えることで，より大きなサイズのデータを用
いて，アルゴリズムが動作できることが期待される．さらに，

次に，入力ファイルのサイズを変化させたときアルゴリズムの実行時間を time コマンドで計測する．その結果を図 12 に示

パターングラフのサイズを変化させる際に，アルゴリズムの全体を評価したいと考えている．

す．この結果から，入力ファイルのサイズを大きくすることで，実行時間は概ね線形に増加すると言える．しかし，より多くのパターングラフを用いて検証する必要がある．

7000
6000

実行時間（s）

5000

4000
3000
2000
1000
0

0

1,000

2,000

3,000

4,000

5,000

6,000

7,000

8,000

9,000 10,000 11,000 12,000

入力ファイルのサイズ（MB）

図 12: 実行時間

3,000

最大主記憶使用量（MB）

2,500
2,000
1,500

1,000
500
0
0

1,000

2,000

3,000

4,000

5,000

6,000

7,000

8,000

9,000 10,000 11,000 12,000

入力ファイルのサイズ（MB）

図 13: 主記憶使用量

更に，入力ファイルのサイズを変化させたときの主記憶最大
使用量を/usr/bin/time -f "%M KB"コマンドで計測した．その結果を図 13 に示す．入力ファイルのサイズを大きくするこ

文

献[1] 下野弘貴, 佐藤正実, 北澤仁志, “特徴空間中の部分グラフ間距離の高速計算による実時間行動識別,” 信学技報, 104(669),
PRMU2004-197, pp.109–114, 2005.
[2] 高橋由雅, 藤島悟志, 加藤博明, “化学物質の構造類似性に基づく
データマイニング”, J.Comput. Chem. Jpn., 2(4), pp.119–126,
2003.
[3] J.R. Ullmann, “An algorithm for subgraph isomorphism,” J.
ACM, 23(1), pp.31–42, 1976.
[4] L.P. Cordella, P. Foggia, C. Sansone, and M. Vento, “A (sub)graph isomorphism algorithm for matching large graphs,”IEEE Trans. PAMI, 26(10), pp.1367–1372, 2004.
[5] H. He and A. K. Singh, “Closure-tree: An index structure
for graph queries,” Proc. ICDE, pp.38–49, 2006.
[6] Huahai He, Ambuj K. Singh. “Graphs-at-a-time: query language and access methods for graph databases,” Proc. SIGMOD, pp.405–418, 2008.
[7] Shijie Zhang, Shirong Li, Jiong Yang, “GADDI: distance index based subgraph matching in, biological networks,” Proc.
EDBT, pp.192–203, 2009.
[8] Peixiang Zhao, Jiawei Han, “On graph query optimizationin large networks,” PVLDB, 3(1), pp.340–351, 2010.
[9] Lee, Jinsoo, et al. “An in-depth comparison of subgraph isomorphism algorithms in graph databases,” PVLDB, 6(2),2012.
[10] Zhiwei Zhang, Jeﬀrey Xu Yu, Lu Qin, Lijun Chang, andXuemin Lin. “I/O eﬃcient: Computing sccs in massivegraphs,” VLDB Journal, 24(2), pp.245–270, 2015.
[11] Zhiwei Zhang, Jeﬀrey Xu Yu, Lu Qin, Qing Zhu, and Xiaofang Zhou. “I/O cost minimization: reachability queries
processing over massive graphs,” Proc. EDBT, pp.468–479,
2012.
[12] Xiaocheng Hu, Yufei Tao, and Chin-Wan Chung. “Massivegraph triangulation,” Proc. SIGMOD, pp.325–336. 2013.
[13] Jeﬀrey Scott Vitter. “Algorithms and Data Structures forExternal Memory,” Foundations and Trends in Technology,
Now Publishers, 2008.
[14] Michael Schmidt, Thomas Hornung, Georg Lausen, andChristoph Pinkel. “SP2Bench: a SPARQL performancebenchmark,” Proc. ICDE, pp.222–233, 2009.
[15] Francesco Silvestri. “Subgraph enumeration in massivegraphs,” CoRR, abs/1402.3444, https://arxiv.org/abs/1402.3444,
2015.