DEIM Forum 2017 E2-4

部分グラフ同型問題と模倣関係の融合
菅原

知倫†

鈴木

伸崇††

† 筑波大学 情報学群 知識情報・図書館学類 〒 305–8550 茨城県つくば市春日 1–2†† 筑波大学 図書館情報メディア系 〒 305–8550 茨城県つくば市春日 1–2
E-mail: †s1311508@u.tsukuba.ac.jp, ††nsuzuki@slis.tsukuba.ac.jp
あらましグラフデータにおける主なパターンマッチの定義として，部分グラフ同型問題（subgraph isomorphism）と模倣関係（graph simulation）の二つがある．これらの概念はそれぞれ次のような特徴がある．(1) 部分グラフ同型問題は NP 完全であり，この問題を解くには最悪の場合指数時間を要する．(2) 模倣関係によるパターンマッチは多項式時間で計算できるものの，解の構造がパターングラフと一致しない．そこで本稿では，部分グラフ同型問題と模倣関係を融合し，両者の利点を活かしたパターンマッチングアルゴリズムを提案する．評価実験では，提案アルゴリズ
ムが概ね所望の動作効率でグラフデータにおけるパターンマッチを行えることを確認した．
キーワード

グラフデータ，部分グラフ同型問題，模倣関係

1. は じ め にそこで本稿では，まず部分グラフ同型問題と模倣関係を融合し，両者の利点を活かした新たな概念を定義する．次に，定義

グラフデータは情報のつながりを表現することに適したデー

した新概念に基づくパターンマッチングアルゴリズムを提案す

タ構造であり，人間関係や交通ネットワークの管理など幅広くる．具体的には，パターングラフのノードに対して，その中か利用されている．グラフデータの効率的なパターンマッチは，ら部分グラフ同型問題の定義を適用するノード（以下，キー

そうした実際の利用に応用できる重要な課題の一つである．

ノード）を任意に設定する．そして，キーノードに対しては部

グラフデータにおける主なパターンマッチの定義として，部分分グラフ同型問題の定義，それ以外のノードに対しては模倣関グラフ同型問題（subgraph isomorphism）と模倣関係（graph係の定義を適用したマッチングを行う．これにより本論文が提simulation）の二つがある．部分グラフ同型問題は，発見した案するアルゴリズムは，部分グラフ同型問題と比べて計算コス

いパターンを定義したグラフ（以下，パターングラフ）と探トが低く，模倣関係と比べて解の構造がパターングラフと一致

索対象のグラフ（以下，データグラフ）が与えられたときに，するマッチングを可能とする．ただし，よりパターングラフのデータグラフに含まれるパターングラフと同型の部分グラフを構造と一致するノードとマッチさせるために，本研究では一般全て見つけるというもので，SNS の分析や化学式の類似構造的な模倣関係の定義を拡張し，制約を強めた模倣関係を扱う．

の発見などに利用できる．部分グラフ同型問題に関する先行研

提案アルゴリズムを実装し，ラベル付き有向グラフを対象と究として，Ullmann によって提案された初の実用的なアルゴリ

した評価実験を行った．その結果，提案アルゴリズムが所望のズムがある [1]．また，近年では Ullmann のアルゴリズムを拡動作効率でグラフデータにおけるパターンマッチを行えること

張する形で VF2 [2]，QuickSI [3]，GraphQL [4]，GADDI [5]，を確認した．

SPath [6] といった多くのアルゴリズムが提案された．しかし，本稿の構成は以下の通りである．２章では，グラフ及びパ部分グラフ同型問題は NP 完全であり，上述のアルゴリズムを

ターンマッチに関する定義を行う．３章では，部分グラフ同型用いたとしても，この問題を解くには最悪の場合指数時間を要問題と模倣関係を融合した新たな概念を定義し，本研究で提案する．また，部分グラフ同型問題はパターングラフと解となる

するアルゴリズムについて説明する．４章では，評価実験につ部分グラフのノード間に 1 対 1 の関係があるため，本来は 1 つ

いて述べる．５章でまとめと今後の課題について述べる．

の解にまとまって欲しいノードが異なる解に分かれてしまい，
更に解の数が必要以上に大きくなってしまうという問題がある．
一方，模倣関係は，ウェブサイトの分類やソーシャルネット
ワーク上の役割の発見などに利用される．この概念によるパ

2. 諸 定 義
本章では，本研究で扱うグラフの概要と，部分グラフ同型問
題および模倣関係の定義について述べる．

ターンマッチは Henzinger らの研究 [7] により多項式時間で計

2. 1 グラフの概要

算できることが示されている．しかし，模倣関係はパターング

ラベル付き有向グラフ（以下，単にグラフ）を G = (V, E)

ラフとデータグラフ間の対応を関係として求めるため，解の構と表す．ここで，V はノードの集合，E はラベル付き有向辺の造がパターングラフと一致しないという問題がある．特に，模集合である．始点を u ∈ V ，終点を v ∈ V ，ラベルを l とする

倣関係の解は単一の関係として得られるため，本来は異なる解

有向辺 e ∈ E を e = u → v と表す．このときノード u と v をに分かれるべきノードが同じ解に含まれてしまうという問題が有向辺 e の端点と呼び，端点は辺 e に接続しているという．まある．

た，ノードに接続する辺のうち，そのノードを終点とする辺をl(u, v) ∈ S ならば, (u′ , v ′ ) ∈ S となる辺 v → v ′ ∈ E が

•

l

存在する．

ǀϬ
Ɛƚ

Ɛƚ

Ɛϭ

(u′ , v ′ ) ∈ S ならば, (u, v) ∈ S となる辺 v → v ′ ∈ E が

•

l

存在する．

ƐϮ

部分グラフ同型問題と模倣関係の定義に基づくパターンマッチ
ƚĂ

ƚĂ

ĐϮ

Đϯ

ƚĂ

Ɛǀ

ƚĂ

Ɛǀ

ƚĂ

の一例を示す．データグラフを図 1，パターングラフを図 2 と
Đϭ

ƚϭ

Đϰ

Đϱ

ƚϮ
ƚĞ

ƚĞ

する．図 2 のパターングラフは「指導教員の担当する授業を受講する学生」を表す．部分グラフ同型問題の場合，次の 3 つの解が得られる．

ƚĞƐƚ сƐƚƵĚĞŶƚ͕Ɛǀ сƐƵƉĞƌǀŝƐŽƌ͕ƚĂсƚĂŬĞƐ͕ƚĞ сƚĞĂĐŚĞƐ図1•f (学生) = s1 , f (授業) = c2 , f (教員) = t1•

f (学生) = s1 , f (授業) = c3 , f (教員) = t1•

f (学生) = s2 , f (授業) = c5 , f (教員) = t2

一方模倣関係の場合，次の解が得られる．

グラフの例

•
入力辺，始点とする辺を出力辺と呼び，v ∈ V の入力辺集合と{(学生, s1 )，(学生, s2 )，(授業, c2 )，(授業, c3 )，(授業, c5 )，(教員, t1 )，(教員, t2 )}出力辺集合をそれぞれ In(v)，Out(v)，入力辺のラベル集合と
出力辺のラベル集合をそれぞれ labin (v)，labout (v) と表す．

学生

G における辺の系列 e1 , e2 , · · ·, en について，辺 ei の端点が′vi−1 と vi であり (1 <=i<= n)，v0 = v, vn = v とすると，こsvtaの辺の系列を v から v ′ への foward/backward パス（以下，fb
パス）と呼ぶ．また，v から v ′ への fb パスが存在するならば，

v ′ は v から fb パスで到達可能であるという．

授業

te

例として，図 1 に学生や教員と授業の関係を表すグラフ
図2

G = (V, E) を示す．ここで，V = {v0 , s1 , s2 , c1 , c2 , c3 , c4 , c5 , t1 , t2 }教員

パターングラフの例

st

st

sv

sv

3. 提 案 手 法

ta

ta

ta

ta

本章では，部分グラフ同型問題と模倣関係を融合した新たな

ta

te

te

te

概念の定義および定義した新概念に基づくパターンマッチング

E = {v0 → s1 , v0 → s2 , s1 → t1 , s2 → t2 ,s1 → c1 , s1 → c2 , s1 → c3 , s2 → c4 ,s2 → c5 , t1 → c2 , t1 → c3 , t2 → c5 }である．ノードは学生や教員，授業を表し，ラベル付き有向辺

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

3. 1 新概念の定義

はそれらの関係を表している．ただし，学生の集合を {s1 , s2 }，新たな概念を定義するために，パターングラフの定義を

授業の集合を {c1 , c2 , c3 , c4 , c5 }，教員の集合を {t1 , t2 } とする．

拡張する（拡張パターングラフ）．拡張パターングラフは

例えば，学生 s1 は授業 c1 ，c2 ，c3 を受講していること，授業P = (Vp , K, Ep ) と定義され，ここで，K はキーノードの集

c2 と c3 は学生 s1 の指導教員である教員 t1 が教える授業であ合，Vp はそれ以外のノードの集合である．P とデータグラフ

るということがわかる．また，このグラフにおいて s1 から c4

G = (V, E) に対して，f : K → V を単射，S ⊂=Vp × V を二項

st

st

ta

への fb パス p0 は s0 ← v0 → s2 → c4 となり，c4 は s1 から関係とする．もし f と S が次の条件を満たすならば，組 (f, S)

p0 で到達可能であるという．

を G における P の解と定義する．
各辺 u → u′ ∈ E が次の条件を満たす．

•

2. 2 パターンマッチの定義l– u ∈ K の場合：u′ ∈ K ならば，f (u) = v∧f (u′ ) = v ′ ，パターングラフを P = (Vp , Ep )，データグラフを G = (V, E)′とする．グラフデータにおけるパターンマッチを次のように定u ∈/ K ならば，f (u) = v∧(u′ , v ′ ) ∈ S となる辺 v → v ′ ∈ E

義する．

が存在する．

– u∈/ K の場合：u′ ∈ K ならば，(u, v) ∈ S ∧ f (u′ ) =部分グラフ同型問題
′

l

l

l

′

もし ∀u → u ∈ Ep ⇒ ∃f (u) → f (u ) ∈ E という条件を満た

v ，u′ ∈
/ K ならば，(u, v) ∈ S ∧ (u′ , v ′ ) ∈ S となる辺

す単射 f : Vp → V が存在するならば，P は G において部分グv → v ′ ∈ E が存在する．

ラフ同型であるという．部分グラフ同型問題とは，上記の条件•を満たす単射をすべて求める問題である．

′

l

各辺 u′ → u ∈ E が次の条件を満たす．
l– u ∈ K の場合：u′ ∈ K ならば，f (u) = v∧f (u′ ) = v ′ ，u′ ∈/ K ならば，f (u) = v∧(u′ , v ′ ) ∈ S となる辺 v ′ → v ∈ E
l

模倣関係
l

′

もし ∀u → u ∈ Ep が次の条件を満たすならば，二項関係

S⊂=Vp × V を模倣関係という．

が存在する．

– u∈/ K の場合：u′ ∈ K ならば，(u, v) ∈ S ∧ f (u′ ) =v ′ ，u′ ∈/ K ならば，(u, v) ∈ S ∧ (u′ , v ′ ) ∈ S となる辺

Algorithm 1 MATCH
Input: パ タ ー ン グ ラ フ P = (VP , K, EP )，デ ー タ グ ラ フ

v ′ → v ∈ E が存在する．
l

G = (V, E)

ただし，G における P の解 (f, S) に対して，もし他のどの組

Output: 解 (f, S) の集合 R(f, S ′ ) に対しても S ′ ⊂=S となるならば，(f, S) は最大であると

1: R ← ∅いう．なお，この定義は部分グラフ同型問題と模倣関係を一般

2: K の中から In(us ) ∪ Out(us ) が最大のノード us ∈ K を化したものである．この定義は K = Vp のとき部分グラフ同型選択する．

問題と一致し，K = ∅ のとき模倣関係と一致する．以下，拡張

3: for each ui ∈ K\{us } do

パターングラフのことを単にパターングラフと呼ぶ．

4:

この定義に基づくパターンマッチの一例を示す．データグラ
フを図 1，パターングラフを図 2 とする．また，図 2 中のノード「学生」をキーノードとすると次の２つの解が得られる．

5: C(us )

←

{vs

∈

V

|

labout (us )⊂=labout (vs )}6: for each vs ∈ C(us ) do•f (学生) = s1 ， {(授業, c2 )，(授業, c3 )，(教員, t1 )}7:•

f (学生) = s2 ， {(授業, c5 )，(教員, t2 )}8:

3. 2 提案アルゴリズム

P における us から ui までの fb パス pi を求める．

9:

labin (us )⊂=labin (vs ) か つ

for each pi do
Ki ← {v ∈ V | v は vs から f b パス pi で到達可能 }if Ki = ∅, 1 <=i<= k then

本節では，3.1 節の定義を用いたパターンマッチングアルゴ

10:

リズムについて述べる．ただし，u′ → u ∈ Ep と v ∈ S(u) に11:

対して，v ′ ∈ S(u′ ) である辺 v ′ → v が存在しない場合，v を

12:

f (us ) ← vs13:

f (ui ) ← vi , 1 <=i<=k

対して，v ∈ S(u) である辺 v → v が存在しない場合，v を

14:

S ← IN IT IALIZE(P, G, f )dangling node とよぶ．Algorithm 1 にアルゴリズム MATCH

15:

S ← S \ {(u, v) ∈ S | v = vs ∨ v = vi , 1 <
=i<
= k}

を，Algorithm 2 にアルゴリズム MATCH の 14 行目で用いて

16:

Q←∅

いる INITIALIZE 関数を示す．

17:

for each u ∈ Vp do

l

l

′

l

′

′

dangling node とよぶ．同様に，u → u ∈ Ep と v ∈ S(u ) に′′lcontinue
for each (v1 , v2 , · · ·, vk ) ∈ K1 × K2 × · · · × Kk , do

Algorithm 1 は 2 行目で，入出力辺が最も多い P のノード us

18:を選択する．3，4 行目で，us を起点とし，us から us 以外の各

19:

Sold (u) ← S(u)キーノードへの fb パスを求める．5 行目で，us にマッチし得る

20:

S(u) からすべての dangling node を削除し，Q

G のノード C(us ) を求める．6 ∼ 31 行目のくり返しで，C(us )に u を加える．

のノードから fb パスを辿ることで，us 以外のキーノードにマッ

21:

チし得る G のノード C(ui ) を求め，単射 f : K → V を作成す22:

おいて，作成した単射 f : K → V に基づき，関係 S ⊂=Vp × Vを求める．関係 S ⊂
V
×
V
は，
14
行目の
INITIALIZE関数に= p
よって解の候補となる関係（dangling node を含む）を求めた

for each u′ ∈ Q dofor each v ′ ∈ Sold (u′ )\S(u′ )and each v ′ → v ∈ E
ls.t. u′ → u ∈ Ep ∧ v ∈ S(u) dolる．もし，fb パスが複数存在する場合，すべての fb パスで到達可能なノードをマッチし得る候補とする．また各くり返しに

if S(u) が dangling node を含む then23:

if v が dangling node になる thenS(u) から v を削除し，Q に u を加える．

24:

Sold (u) ← S(u)

25:
26:

for eachv ′ ∈ Sold (u′ )\S(u′ )and each v → v ′ ∈ E
ls.t. u → u′ ∈ Ep ∧ v ∈ S(u) dol

後，17 ∼ 29 行目で dangling node を削除することで求める．

Algorithm 2 は 2 行目で，始点もしくは終点どちらか片方の27:

みがキーノードの辺を T に追加する．3 ∼ 5 行目で，始点と28:

if v が dangling node になる thenS(u) から v を削除し，Q に u を加える．
Sold (u) ← S(u)終点が共にキーノードである P の辺に対応する辺が G に存在

29:

するかどうかをチェックする．6 ∼ 32 行目のくり返しで，すべ30:ての u ∈ Vp について，マッチし得る G のノード S(u) を求め

31:

る．S(u) は，P のノード u の入出力辺と，u にマッチし得る

32: R を返す．

if すべての u ∈ Vp について，S(u) =| ∅ then
R に (f, S) を加える．

候補ノードの入出力辺を順々に見ていくことで求める．6 ∼ 32
行目のくり返しの対象となる辺 u → u′ ∈ T は，常に始点かl

辺を T に追加する．

終点どちらか一方のノードはマッチし得る候補が求まっている

提案アルゴリズムの時間計算量について考える．まず，アルが，もう一方のノードにマッチし得る候補が求まっていない．

ゴリズム MATCH の 14 行目で用いている INITIALIZE 関数

マッチし得る候補が求まっているノードが始点か終点かによっの時間計算量を考える．1，12，13 行目は定数時間で実行できて 7 ∼ 19 行目の処理を行うか 20 ∼ 32 行目の処理を行うか決る．2 行目は P のすべての辺から，始点もしくは終点どちらか定する．どちらの場合も，マッチし得る候補が求まっていない
ノード u ∈ Vp に対応する候補を求め，その後 u ∈ Vp の入出力
辺のうち，隣接する頂点にマッチし得る候補が求まっていない

片方のみがキーノードの辺を T に追加するため，O(|Ep |) の時間がかかる．3 ∼ 5 行目のくり返しは最大でも |Ep | 回であるたAlgorithm 2 INITIALIZE
Input: パ タ ー ン グ ラ フ P = (Vp , K, Ep )，デ ー タ グ ラ フ
G = (V, E)，単射 f : K → V

キーノードを調べる必要があるので，O(|K|) の時間がかかる．

3，4 行目は |K| − 1 回くり返されるが，各回において fb パス

1: S ← ∅′l| u → u′ ∈ Ep , (u ∈ K ∧ u′ ∈/ K) ∨ (u′ ∈
l

′

l

′

3: for each u → u

べての辺を調べる必要があるので，O(|Ep | + |E|) の時間がかか∈ Ep s.t. u ∈ K ∧ u ∈ K do

if f (u) → f (u′ ) ∈/ E thenlる．6 ∼ 31 行目のくり返しは us にマッチするノードの数だけくり返さるので，最大 |V | 回くり返される．7 ∼ 8 行目は fb パ

∅ を返す．

5:′l∈ T doスの数だけくり返され，その数は ui の数が |K| − 1 であり，各if u ∈ K ∨ (u ∈/ K ∧ S(u) =| ∅) thenui までの fb パスの数が最大 |Ep | なので，最大 (|K| − 1) × |Ep |6: for each u → u
7:

を深さ優先探索で求めるため，O(|K| · (|V | + |E|)) の時間がかかる．5 行目は us の入出力辺の数が最悪 |Ep | であり，G のす

K ∧u∈
/ K)}
4:

アルゴリズム MATCH の時間計算量を考える．1，9 ∼ 10，

12，13，16 行目は定数時間で実行できる．2 行目はすべてのOutput: 二項関係 S ⊂=Vp × V
2: T ← {u → u

である．

if u ∈/ K then

8:回である．また，各くり返しの中で fb パスを深さ優先探索で

′

′

l

′

′

′

l

′

辿るので，合計で O(|K| · |Ep | · (|V | + |E|)) の時間がかかる．

S(u ) ← {v ∈ V | v ∈ S(u), v → v ∈ E}

9:

11 行目以降のくり返しは，それぞれのキーノードにマッチする

else

10:

候補のノード数が |V | 以下で，それの |K| − 1 個の直積をとる

S(u ) ← {v ∈ V | v ∈ f (u), v → v ∈ E}

11:

ので |V ||K|−1 回くり返される．14 行目の INITIALIZE 関数のif S(u′ ) = ∅ then12:

時間計算量は式（3.1）のように O(|Ep | · |E|) であり，15 行目∅ を返す．

13:

′

′′

l

′

14:

for each u → u ∈ Out(u ) do

は Vp の各ノードに対し，マッチした最大 |V | の候補ノードを

15:

if u′′ ∈/ K ∧ S(u′′ ) = ∅ then

調べるので O(|Vp | · |V |) である．17 ∼ 20 行目は v が dangling

′

′′

l

u → u を T に加える．

16:

′′

′

l

node かどうか調べるため，各 u とその入出力辺，u にマッチ′する v とその入出力辺を見る必要があるので，O(|Ep | · |E|) のfor each u → u ∈ In(u ) do

17:

′′

′′

時間がかかる．21 ∼ 29 行目のくり返しは，Q の大きさが最悪

if u ∈/ K ∧ S(u ) = ∅ then

18:

′′

′

l

の場合 |Vp | なので，最大 |Vp | 回くり返される．22，26 行目にu → u を T に加える．

19:

ついて，Sold (u′ )\S(u′ ) の大きさは最悪の場合 |V | である．まelse if u′ ∈ K ∨ (u′ ∈/ K ∧ S(u′ ) =| ∅) then

20:

た，u′ → u ∈ Ep ∧ v ∈ S(u) となる各 v ′ → v ∈ E を得るた
l

if u′ ∈
/ K then21:

S(u) ← {v ∈ V | v ′ ∈ S(u′ ), v → v ′ ∈ E}l

22:

め，u と v の入出力辺を調べる必要があり，21 行目以降のくり返し全体で O(|Ep | · |E|) の時間が必要である．更に，23 ∼ 25，

else

23:

′

′

l

′

27 ∼ 29 行目は v が dangling node になるか判定するため，vS(u) ← {v ∈ V | v ∈ f (u ), v → v ∈ E}

24:
25:
26:

l

if S(u) = ∅ thenの入出力辺を調べる必要があり，v の入出力辺は最大 |E| なの∅ を返す．

で，O(|E|) の時間がかかる．そのため，21 ∼ 29 行目のくり返

27:

′′

for each u → u ∈ Out(u) do

しは全体で O(|Ep | · |E|2 ) の時間がかかる．30 ∼ 31 行目はす28:

if u′′ ∈/ K ∧ S(u′′ ) = ∅ then

べての u を調べるので O(|Vp |) である．よって，提案手法の時

l

′′

l

u → u を T に加える．

29:

′′

間計算量は

l

for each u → u ∈ In(u) do

30:

O(|V ||K| (|Ep |·|E|2 )+|K|·|Ep |·|V |·(|V |+|E|)) = O(|V ||K| (|Ep |·|E|2 ))if u′′ ∈/ K ∧ S(u′′ ) = ∅ then

31:

(2)

u′′ → u を T に加える．
33: S を返す．
l

32:

である．
以上の議論から，以下が成り立つ．

め，2 行目と同様に O(|Ep |) である．6 ∼ 32 行目のくり返しに定理 1. 定数 c に対して |K| <= c であるとする．このとき，

ついて考える．8 ∼ 11 行目は，調べる必要がある v の出力辺

Algorithm 1 は多項式時間で動作する．

l′v → v ∈ E の数が最大 |E| であるため，O(|E|) の時間がかかる．14 ∼ 16 行目および 17 ∼ 19 行目の処理は，6 ∼ 32 行目のくり返し全体でそれぞれ最大 |Ep | 回実行される．そのため，くり返し全体で O(|Ep |) の時間がかかる．また，20 行目以降に分|K| が定数で抑えられない場合，上記時間計算量は指数オーダーとなる．しかし，以下の結果から，これを多項式オーダーにするのは困難である．

岐した場合の計算コストは 8 ∼ 19 行目と同様である．6 ∼ 32

定理 2. |K| が定数でない任意のサイズを許すとする．P = NP

行目のくり返しは最大 |Ep | 回くり返されるので，INITIALIZE

でない限り，本問題を多項式時間で解くことは困難である．

関数の時間計算量は証明. P != NP かつ本問題が多項式時間で解けると仮定する．

O(|Ep | · |E|)(1)

与えられたパターングラフ P とデータグラフ G に対して，P

に任意にノードを追加して，P を部分グラフとして含む（多項′′数を実行した結果，{(授業, c1 ), (授業, c2 ),式サイズの）パターングラフ P を作る．P のキーノード集合(授業, c3 )} という関係が求まる．15 行目で，キーノードにマッ

K を P のノードと一致するように指定する．P ′ と G に対してチし得る候補ノード s1 と t1 が求めた関係に含まれていないか

本問題を解き，得られた解から K にマッチしないノードを取を調べる．14 行目の INITIALIZE 関数で求めた関係に含まれり除く．これは，P にマッチする部分グラフ同型問題を解くこる c1 は dangling node であるため 17 ∼ 20 行目で削除する．

とと同じである．本問題が多項式時間で解けることから，NPもし dangling node を削除したことで，新たな dangling node完全である部分グラフ同型問題も多項式時間で解けることになが発生した場合 21 ∼ 29 行目で削除するが，この場合，新たにり，P != NP に矛盾する．よって P = NP でない限り，本問発生した dangling node は存在しない．30，31 行目で，求め題を多項式時間で解くことは困難である．

た単射と関係の組を解の集合 R に加える．s2 に対しても同様に 6 ∼ 31 行目の処理を行い，最後に 32 行目で解の集合 R を

3. 3 アルゴリズムの動作例
本節では，パターングラフを図 2，データグラフを図 1 としてアルゴリズムの動作例を示す．図 2 中のノード「学生」と「教員」をキーノードとする．
まず，Algorithm 1 の 2 行目で，キーノード集合の中から入力辺と出力辺の合計が最多のキーノードを選択する．この場合，キーノード「学生」とキーノード「教員」の入出力辺の合計は共に 2 であるため，任意に「学生」を選択したとする．3，4 行
目で，選択した「学生」から他のキーノード「教員」への fb パ
sv

スを求める．
「学生」から「教員」への fb パスは 学生 → 教員tateと 学生 → 授業 ← 教員 の 2 つである．5 行目で，選択した「学生」にマッチする候補を求める．データグラフの中で，「学生」と同じラベルの入出力辺を持つ s1 と s2 が候補となる．こ
うして求めた s1 と s2 それぞれに対して 6 ∼ 31 行目の処理を行う．仮に vs ∈ C(us ) を s1 として 6 行目以降の説明をする．

7，8 行目で，s1 から先ほど求めた fb パスを辿ることで，選択しなかったキーノード「教員」にマッチし得る候補を求める．
この場合，候補は t1 のみである．こうして求めた候補を用いて，12，13 行目で f (学生) = s1 , f (教員) = t1 という単射を作成する．14 行目の INITIALIZE 関数で，作成した単射に基づきキーノードでない P のノード「授業」にマッチし得る候補の関係を求める．
ここで，INITIALIZE 関数の動作について述べる．2 行目taで，始点か終点どちらかがキーノードである辺 学生 → 授業 とte

教員 → 授業 を集合 T に加える．3 ∼ 5 行目で，始点と終点
svが共にキーノードである辺 学生 → 教員 に対応する辺 f (学生返し，マッチングを終了する．

4. 評 価 実 験
本章では，提案アルゴリズムに関する評価実験について述べる．提案アルゴリズムを実装し，(1) データグラフのサイズを変化させたときのアルゴリズムの処理時間，(2) キーノードの数を変化させたときのアルゴリズムの処理時間，(3) 提案手法
による解の数の 3 点を評価する．

4. 1 評価用データ
評価実験に用いるデータグラフは，任意のサイズのラベル付き
有向グラフを生成するベンチマークソフトである SP2 Bench [9]及び BSBM(Berlin SPARQL Benchmark) [10] を用いて作成する．SP2 Bench で作成したグラフの概要を表 1 に，BSBM で作成したグラフの概要を表 2 に示す．実験に用いるパターング
ラフは，それぞれのベンチマークソフトが生成するグラフデー
タの構造に沿って人工的に作成する．SP2 Bench が生成するグラフに対するパターングラフとして図 3 と図 4 を，BSBM が生成するグラフに対するパターングラフとして図 5 を作成した．
表 1 SP2 Bench で作成したデータグラフの概要
辺数 ノード数

データサイズ (KB)

10,303

6,533

1,088

30,02918,6073,225

50,16830,794

5,400

70,27043,008

7,588

90,06155,0859,730

sv) → f (教員) がデータグラフ中に存在するかどうかを調べる．2
tate

行目で求めた辺 学生 → 授業 と 教員 → 授業 それぞれに対して 6 ∼ 32 行目の処理を行う．仮に u → u′ ∈ T を 学生 → 授業lta

として 6 行目以降の説明をする．
「学生」はキーノードなので，

表 2 BSBM で作成したデータグラフの概要
辺数 ノード数

データサイズ (KB)

7 ∼ 19 行目に分岐する．また，8 ∼ 11 行目は 10，11 行目の40,177

14,205

10,174

処理に分岐し，始点が「学生」にマッチし得る候補 s1 であり，

115,387

37,68329,370ラベルが「ta」である辺の終点を S(授業) に加える．この場合，

190,496

60,66848,548260,92280,784

66,611

331,385

100,81784,713

c1 ，c2 ，c3 が S(授業) に加わる．S(授業) が空でないため 12，
13 行目の処理は行われない．また，隣接する頂点がキーノード
でなく，マッチし得る候補も求まっていない「学生」の入出力
辺が存在しないため，14 ∼ 19 行目で新たに T に加わる辺はな
teい．教員 → 授業 に対しても同様に 6 ∼ 32 行目の処理を行い，最後に 33 行目で関係 S を返し，INITIALIZE 関数を終了する．
再び Algorithm 1 の動作について述べる．INITIALIZE 関4. 2 評価実験の詳細
評価実験の環境は以下の通りである．

OS: Windows 10 Home (64bit)
CPU: Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz
主記憶:

8.00GB

使用言語: Ruby 2.3.1
以下，得られた結果について述べる．

4. 2. 1 実験 1:データグラフのサイズを変化させたときのア
ルゴリズムの処理時間
はじめに，SP2 Bench で作成した 5 つのデータグラフ（表1）を対象に，パターングラフを図 3，キーノードの数を 3 としてマッチングにかかる時間を計測した．処理時間の計測はWindows PowerShell の Measure-Command を用いた．計測
した結果を図 6 に示す．また，BSBM で作成した 5 つのデー
図 3 作成したパターングラフ (1)タグラフ（表 2）を対象に，パターングラフを図 5，キーノー
ドの数を 1 としてマッチングにかかる時間を計測した．計測した結果を図 7 に示す．実験の結果から，キーノードの数を定数とすると，提案アルゴリズムの処理時間はデータグラフのサイズ（辺数）に関してほぼ線形であることがわかる．

title

JournalJournalTitle
14
12

journal10

ArticleTitle

title

(s)

時 8
間

Article6
4creatorCreator

2
0

10303

30029

50168

70270

90061

データグラフのサイズ（辺数）

図 4 作成したパターングラフ (2)図6Country
country

DeliveryDays

HomepagePricehomepage

price

データグラフの変化と処理時間 (1)4. 2. 2 実験 2:キーノードの数を変化させたときのアルゴリ
ズムの処理時間

deliveryDays

2

Offer

Producer

Label

Product
Type

ノード数 1 から 6 までのマッチングにかかる時間を計測した．
計測した結果を図 8 に示す．また，BSBM で作成した 5 つのreviewFor
type

SP Bench で作成した５つのデータグラフ（表 1）のうち辺数 50168 のグラフを対象に，パターングラフを図 3 としてキー

Product

product
Featurelabel

Vendorproduct

producer

Product
FeaturevendorReview

reviewer

title

Title

Person

データグラフ（表 2）のうち辺数 40177 のグラフを対象に，パターングラフを図 5 としてキーノード数 1 から 5 までのマッチ

name

Name

ングにかかる時間を計測した．計測した結果を図 9 に示す．実
験の結果から，キーノード数を変数とすると，提案アルゴリズ
ムの実行時間は線形より大きくなることがわかる．

図 5 作成したパターングラフ (3)4. 2. 3 実験 3:提案手法と部分グラフ同型問題の解の数
SP2 Bench で作成した５つのグラフ（表 1）のうち辺数 50168のグラフを対象に，パターングラフを図 4 としてマッチングを得られた結果を図 10 に示す．部分グラフ同型問題による解の16

数が 4811 個に対し，提案手法による解の数は 104 個であった．

14

対象としたグラフに含まれている雑誌ノードの数が 104 個なので，提案手法による解の数は検索目的を満たす必要最小限の数12だと言える．実験の結果から，部分グラフ同型問題の解の数が10必要以上に大きくなるのに対し，提案手法は検索目的に適した

時
間 8

(s)

キーノードを指定することで解の数を抑えることが可能である
とわかる．

6
4

6000

2

0
40177

1153871904962609223313854811

データグラフのサイズ（辺数）

4000
図7

データグラフの変化と処理時間 (2)

ϭϬϬ

100

ϵϬ

104

ϴϬ
ϳϬ

᫬㛫;ƐͿ

ϲϬ

0

ϱϬ

提案手法

部分グラフ同型問題

ϰϬϯϬ

図 10 提案手法と部分グラフ同型問題の解の数

ϮϬ
ϭϬ
Ϭ
ϭ

Ϯ

ϯ

ϰ

ϱ

ϲ

4. 3 考察

前章の式 (2) より，Algorithm 1 の時間計算量は線形よりも䜻䞊䝜䞊䝗䛾ᩘ

大きくなっている．しかし，式 (2) の時間計算量は最悪の場合
図8

キーノード数の変化と処理時間 (1)のものであり，実験 1 の結果から，実際にはより効率よく動作することが期待される．
また，実験 2 の結果から，実行時間はキーノード数に関して

600

指数関数的に増加する．定理 2 の結果から，キーノード数を変500数とした場合は本問題は計算困難であり，実験 2 の結果はこのことを反映したものといえる．このことから，キーノードを増400加させた場合の，実行時間の上昇を抑えるのは本質的に困難であると考えられる．

時
間 300

(s)

5. む す び200

本稿では，部分グラフ同型問題と模倣関係を融合した新たな概念を定義し，定義した新概念に基づくパターンマッチングア

100

ルゴリズムを提案した．具体的には，パターングラフのノードに対して，その中からキーノードを任意に設定し，キーノード

0
1

2

3

4

5

キーノードの数に対しては部分グラフ同型問題の定義，それ以外のノードに対しては模倣関係の定義を適用してマッチングを行うアルゴリズ
ムである．また，提案アルゴリズムの処理時間を評価するため

図9

キーノード数の変化と処理時間 (2)Ruby 言語を用いて実装し，評価実験を行った．その結果，(1)キーノードの数を定数とすると，データグラフのサイズに対し行い，提案手法と部分グラフ同型問題の解の数を計測した．たて線形の処理時間でマッチングを行えること，(2) キーノード

だし，検索目的を「雑誌ごとに，雑誌に含まれる論文のタイトの数を変数とすると，キーノード数の増加に従い，処理時間がルと著者の一覧（タイトルと著者の対応は求めない）」とし，提指数関数的に増加することを確認した．

案手法におけるキーノードは「Journal」のみとして計測した．

今後の課題としては，本稿の提案アルゴリズムではマッチしない情報を検索するため，融合させるパターンマッチの定義を修正あるいは拡張することが考えられる．また，本稿が提案したアルゴリズムはすべてのデータを主記憶に格納し処理することを前提としているため，データグラフのサイズが主記憶のサイズを大幅に超える場合，本稿の提案アルゴリズムを適用することは困難である．そこで，主記憶のサイズを大幅に超える大規模グラフに対してもマッチングが行えるようアルゴリズムを拡張することが重要な課題であると考えられる．

文

献[1] J.R. Ullmann, “An algorithm for subgraph isomorphism,”
J. ACM, 1976, 23(1), pp. 31–42.
[2] 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.
[3] H. He and A. K. Singh, “Closure-tree: An index structure
for graph queries,” Proc. ICDE, pp.38–49, Atlanta, USA,
April. 2006.
[4] Huahai He, Ambuj K. Singh. “Graphs-at-a-time: query language and access methods for graph databases,” Proc. SIGMOD, pp. 405–418, Vancouver, Canada, June. 2008.
[5] Shijie Zhang, Shirong Li, Jiong Yang, “GADDI: distance index based subgraph matching in biological networks,” Proc.
EDBT, pp. 192–203, Bordeaux, France, March. 2009.
[6] Peixiang Zhao, Jiawei Han, “On graph query optimizationin large networks,” Proc. VLDB, pp. 340–351, Singapore,
Sept. 2010.
[7] Monika R. Henzinger, Thomas A. Henzinger, Peter W.
Kopke, “Computing Simulations on Finite and Infinite
Graphs,” Foundations of Computer Science, 1995, pp. 453–
462.
[8] Milner, R. Communication and Concurrency. Prentice Hall,
1989.
[9] Michael Schmidt, Thomas Hornung, Georg Lausen, andChristoph Pinkel, “SP2Bench: a SPARQL Performance
Benchmark,” Proc. ICDE, pp. 222–234, Shanghai, China,
2009.
[10] Chris Bizer, Andreas Schultz, “Berlin SPARQL Benchmark(BSBM) - Benchmark Rules,” http://wifo5-03.informatik.unimannheim.de/bizer/berlinsparqlbenchmark/spec/ BenchmarkRules/index.html, 参照 Feb. 3, 2017.