DEIM Forum 2017 E8-2

データグラフ上の並列枝刈りによるサブグラフマッチング
新井

淳也†

藤原

靖宏†

真††

鬼塚

岩村 相哲†† 日本電信電話株式会社 ソフトウェアイノベーションセンタ
†† 大阪大学 大学院情報科学研究科
E-mail: †{arai.junya,fujiwara.yasuhiro,iwamura.sotetsu}@lab.ntt.co.jp, ††onizuka@ist.osaka-u.ac.jp
あらましデータグラフ G とクエリグラフ Q が与えられたとき，Q と同型なサブグラフを G から発見する問題はサブグラフマッチングと呼ばれる．ラベル付きグラフ上のサブグラフマッチングを高速化するため，これまで頂点間のマッチングを取る際の探索順序を最適化する手法についてよく研究されてきた．しかし既存手法は実世界のグラフのように冪乗則に従った次数分布を持つグラフにおいて多数の頂点を訪問するため計算コストが高いという問題がある．
そこで本論文では高次数頂点の訪問を避ける動的なマッチング順序と，データグラフ上の局所的な隣接関係に基づく枝刈りを組み合わせたサブグラフマッチングアルゴリズムを提案する．
キーワード

グラフアルゴリズム，サブグラフマッチング，ラベル付きグラフ

1. は じ め に
多様な事物間の関係性を表現できるグラフデータは，近年ま

𝑞1 a

𝑣3 b

すます多くの分野で分析の対象として利用されるようになっている．グラフ分析において最も頻繁に用いられる処理の一つとして，特定の構造を持つ部分グラフの発見，すなわちサブグラ

𝑣2 a

𝑣1 a

𝑣4 c

𝑣5 c

100

𝑞2 b

𝑞3 c

𝑞4 b

𝑞5 b

フマッチングがある．より厳密には，サブグラフマッチングは

𝑣6 b… 𝑣105 b

𝑣106 b … b 𝑣115

b 𝑣11610𝑣117 c … c
10

大きいグラフ (データグラフ) G と小さいグラフ (クエリグラ

𝑣7 bc … c … c … c 𝑣1116
1010フ) Q を受け取り，Q と同型な G のサブグラフへの埋め込み(a) クエリグラフを発見する問題である．この問題は様々な場面で利用されてい図 1 クエリグラフ Q とデータグラフ G の例．頂点内のアルファベッ

る．Fang ら [4] は人物，学校，専門分野，住所など複数種類の(b) データグラフ

トはラベルを，qi , vi は頂点の ID を示す．

事物を頂点として持つグラフ上のサブグラフマッチングによって，人物間の関係に意味付けを行った．例えば同じ学校と専門

q2 はラベル b なので，同じくラベル b を持つ 112 個のデータ分野に接続されている 2 人の人物はクラスメイトであると考え

頂点 v3 , v6 , v7 , . . . , v116 にマッチし得る．同様に q3 はラベル c

ることができる．同様に Hu ら [8] は企業，従業員，役職などを持つ 1,002 個の頂点 v4 , v5 , v117 , v118 , . . . , v1116 にマッチし得を含むグラフをサブグラフマッチングによって企業のみから成る．従って最初の 2 頂点 q2 , q3 への部分的なマッチングだけでるグラフに変換し，営業活動における顧客推薦に利用した．ま112 × 1,002 = 112,224 通りもの部分的な埋め込みが生じる．以た Park ら [10] はプログラムの振る舞いをグラフとして表現し，降の探索ではこれらの部分埋め込みに残りのクエリ頂点とマッ

新種あるいは自己変異型マルウェアの検出にサブグラフマッチ

チするデータ頂点を追加していくことになるため，計算コストングを使用した．
以上のようにラベル付きグラフ上のサブグラフマッチングが高い．一方で (q1 , q2 , . . .) という順序では，最初の 2 頂点が隣接するラベル a と b の頂点である．これを満たすデータ頂点の応用は広いが，NP 困難な問題であるため計算に時間を要すの組合せは (v1 , v3 ), (v2 , v3 ) の 2 通りのみであるため，部分埋る [6]．さらに 1 回のグラフ分析の中で繰り返しサブグラフマッ

め込みの数は 112,224 通りと比べ大幅に減少する．

チングを用いる場合もある [8, 18] ことから，サブグラフマッチ
ングの計算時間は大きな問題となる．
サブグラフマッチングの計算時間を短縮するために重要なの

こ の よ う な マッチ ン グ 順 序 の 最 適 化 に 関 し て 近 年 Tur-boISO [6], BoostISO [11], CFLMatch [1] などでよく研究されてきた．これらの手法はマッチング先のデータ頂点から幅優先

はマッチング順序の最適化である．マッチング順序とは埋め込

探索 (BFS) を行いデータグラフの要約構造を作成し，各クエ

みとなるクエリ頂点とデータ頂点のペアを探す順番に関する実リ頂点にマッチし得るデータ頂点の数を見積もる．そしてその行プランである．どのようなマッチング順序を取るかによって，情報を用いてマッチング順序の最適化を行う．

一部の頂点ペアについてのみ対応関係が記録された中間結果，

しかしながら実世界のグラフにおける BFS は計算コストが高

すなわち部分的な埋め込みの生成数は大きく変化する．例えばいという問題点がある．なぜならば実世界のグラフは一般に冪図 1(a) のクエリグラフと図 1(b) のデータグラフのマッチング乗則に従う次数分布，すなわちごく少数の頂点が極端に大きいにおいて，(q2 , q3 , . . .) というマッチング順序を取ったとする．

次数を持つような構造を持っており [13]，BFS で高次数頂点を表1

訪問すると大量の隣接頂点へのアクセスが発生するためである．
例えば図 1(b) のデータグラフにおいては頂点 v3 が極端に高い
次数 (102) を持つ．そのため，仮に v1 からの BFS で v3 に訪問したとすると，その先にある 100 個の隣接頂点 v6 , v7 , . . . , v105

本論文で用いる表記

表記

定義

Q, G

データグラフとクエリグラフ

VQ , VG

頂点集合; VQ = {q1 , q2 , . . .}, VG = {v1 , v2 , . . .}EQ , E G⊂
エッジ集合; EQ ⊂= VQ × VQ , EG = VG × VG

へのアクセスが発生する．v6 , v7 , . . . , v105 はそれぞれ次数 11

Σ

ラベル集合

または 12 であり極端に高くはないが，それらの下には 1000 個ℓ(v)

頂点 v のラベル

N (v)

頂点 v の隣接頂点集合

Nσ (v)

頂点 v の隣接頂点のうちラベル σ を持つものの集合の走査には時間を要する．このような BFS による要約グラフ

M

写像 (埋め込み); (x, y) ∈ M を M [x] = y とも書くの作成はクエリグラフのマッチング先領域をデータグラフ上でdom(M )

M の定義域; dom(M ) = { x | (x, y) ∈ M }ran(M )

M の値域; ran(M ) = { y | (x, y) ∈ M }の隣接頂点 v117 , v118 , . . . , v1116 が存在し，これら大量のエッジ変更するたびに発生し，そのことが実世界のグラフにおける既存手法の性能を低下させると考えられる．

C[v]v ∈ VG とマッチし得るクエリ頂点の集合

C −1 [q]q ∈ VQ とマッチし得るデータ頂点の集合

本論文ではこのようなマッチング順序に関する問題点を解決したアルゴリズムを提案する．提案手法は 2 つのステップから成る．ますステップ 1 はマッチング候補頂点の枝刈りである．
ここでマッチング候補頂点とは各データ頂点がマッチし得るク
エリ頂点の集合である．既存手法はデータグラフの構造を分析するために BFS によるグラフ要約を行うのに対し，提案手法
ではデータグラフ上で隣接頂点の情報を利用した繰り返し処理を行うことにより探索空間の削減とマッチング順序最適化のための情報収集を行う．次のステップ 2 では動的にマッチング
順序を最適化しながら埋め込みの探索を行う．提案手法はマッチし得るデータ頂点の数が最も少ないクエリ頂点から順にマッ
チングを行う．そのため，高次数頂点に隣接する大量の頂点への訪問を避けることができる．さらにクエリグラフにおいて閉路を含む部分から優先的にマッチングを行うことで，隣接頂点集合の交差を用いたマッチング候補頂点の絞り込みを行う．ステップ 1, 2 とも容易に並列化が可能であり，マルチコアまたはマルチソケットのマシンを効率的に利用することができる．評
価では提案手法の逐次処理版プロトタイプ実装を用いて実験を行い，現状でも手法提案者などによる既存手法の実装と比肩する性能でサブグラフマッチングが可能であることを確認した．
本論文の構成は次のとおりである．第 2 節において必要な背景知識を説明する．第 3 節で提案手法の詳細を述べ，その評価結果を第 4 節で示す．第 5 節で関連研究を紹介し，最後に第 6
節で結論を述べる．

2. 背 景 知 識
本節ではサブグラフマッチング問題を定義したのち，提案手法の説明に必要となる既存技術について述べる．

2. 1 問 題 定 義
本論文ではデータグラフとして頂点がラベルを持つ無向グラフ

G = (VG , EG , Σ, ℓ) を扱う．VG は頂点の集合，EG ⊂= VG × VG
はエッジの集合，Σ はラベルの集合，ℓ は頂点とラベルを対応させる関数である．同様にクエリグラフ Q = (VQ , EQ , Σ, ℓ) をなお，簡単のため以降は頂点がラベルを持つ無向グラフについてのみ説明するが，エッジがラベルを持つグラフや有向グラ
フにも容易に拡張することができる．

2. 2 バックトラッキングによるサブグラフマッチング
サブグラフマッチングのアルゴリズムはバックトラッキングに基づくものが一般的である．このアプローチではクエリグラ
フに含まれる頂点に対してマッチング順序を適当に定め，その順でしらみつぶしにマッチする頂点を探索する．マッチする頂点が見つからない場合は，一旦マッチング順序を手前に戻り，別の頂点にマッチさせて再度探索を行う．例として図 1 のクエ
リグラフとデータグラフを用いてこの処理の流れを説明する．
クエリ頂点のマッチング順序はランダムに (q4 , q5 , q3 , q1 , q2 ) を選んだとする．最初のクエリ頂点 q4 はラベル b なので，112 個のデータ頂点 v3 , v6 , v7 , . . . , v116 がマッチング候補となる．ここではまず q4 に v3 をマッチさせたとして進める．このことをM ← M ∪ {(q4 , v3 )} または M [q4 ] ← v3 と書くことにする．2
番目にマッチを取る q5 もラベル b であるが，v3 は使用済みなので，M [q5 ] ← v6 を選んだとして次の q3 へ進む．q3 はラベル c を持ち q1 と q4 に隣接しているので，q3 の候補もマッチング済み頂
点 M [q4 ] (= v3 ) と隣接していなければならない．しかしそのよ
うな頂点は存在しないので，マッチング順序が 1 つ手前の q5 のマッチングを行う段階まで戻り，M [q5 ] ← v6 , v7 , . . . v116 とマッ
チングを変更しながら再度探索する．それでも見つからないた
めさらにマッチング順序が手前の q4 まで戻り，同様に探索する．
最終的に M = {(q1 , v2 ), (q2 , v3 ), (q3 , v5 ), (q4 , v105 ), (q5 , v116 )}という唯一の埋め込みを発見し探索を終了する．
バックトラッキングは最新の手法も含め多くの手法の基礎となっている [1]．このような探索に要する時間はクエリ頂点のマッチング順序によって大幅に変化するため，順序を最適化す
る研究が行われてきた．また不要な探索を枝刈りするためのマッチング候補頂点の枝刈り手法を併用することでさらに探索空間を削減することが可能である [7, 19]．

考える．VQ と EQ はそれぞれ頂点とエッジの集合である．こ
こで次のようなとき Q は G に対してサブグラフ同型であるという: 単射 M : VQ → VG が存在し，∀q ∈ VQ , ℓ (q) = ℓ (M [q])かつ ∀ (q, q ′ ) ∈ EQ , (M [q], M [q ′ ]) ∈ EG ．このような単射 Mは埋め込みとも呼ばれる．サブグラフマッチングとは，データ
グラフ G とクエリグラフ Q が与えられたとき，上記の条件を満たす全ての埋め込み M を発見する問題と定義する．

3. 提 案 手 法
サブグラフマッチングはバックトラッキングで大量の部分埋め込みを生成しながらマッチングを探索するため，計算コストが高い．そこで提案手法では (i) 候補頂点の枝刈りと (ii) 動的なマッチング順序による埋め込み探索という 2 つのステップによAlgorithm 1 候補頂点枝刈り

さらに多くのクエリ頂点を候補から除外するとともに，データ

入力: データグラフ G，クエリグラフ Q

グラフから不要なエッジを削除することでグラフの規模を縮小

出力: マッチング候補頂点集合 C

する．この処理では，データ頂点 v とクエリ頂点 q がマッチし

1
2
3
4

for v ∈ VG do

う性質を利用する．この判定を行う関数 HasCandidates の定

repeat義は後で議論する．例えば図 1 において，IsCandidate(v4 , q3 )for v ∈ VG do

5

C[v] ← { q ∈ C[v] | HasCandidates(v, q, C) }6

for v ′ ∈ N (v) do

7

if C[v ′ ] ∩ N (C[v]) = ∅ then

8

′

9

得るならば，v の隣接頂点は q の隣接頂点にマッチし得るといC[v] ← { q ∈ VQ | IsCandidate(v, q) }が成立する．しかし，q3 は q4 と隣接しているにもかかわらず，
前段の枝刈りの結果 v106 , . . . , v115 は q4 にマッチし得ないことが分かっているので，v4 は q4 とマッチし得る頂点と隣接してエッジ (v, v ) を削除

いない．従って v4 と q3 にマッチし得ないことが分かる．このuntil C が変更されていない

ように枝刈りの情報を伝播させることでより多くのクエリ頂点
り部分埋め込みの生成数を削減する．候補頂点の枝刈りによって，データグラフにおいて隣接頂点がどのクエリ頂点にマッチし得るかを知ることができる．動的なマッチング順序の生成ではその情報を用いることにより，マッチし得るデータ頂点が最も少ないクエリ頂点から順にマッチングを行っていく．本節ではこれらの 2 ステップの詳細についてそれぞれ説明する．

を C から除外することができる．
さらにこのように C に含まれる頂点を減少させていくと，マッチング結果に影響しない不要なエッジが見つかる．デー
タグラフのエッジ (v, v ′ ) を削除してよい条件は，クエリグラ
フにおいて C[v] と C[v ′ ] の間にエッジがないこと，すなわち

C[v ′ ] ∩ N (C[v]) = ∅ である．例えばラベル a と c の頂点を接続するエッジはクエリグラフでは (q1 , q3 )，データグラフでは

3. 1 データグラフ上の候補頂点枝刈り
最初のステップである候補頂点枝刈りでは，各データ頂点(v1 , v4 ), (v2 , v4 ), (v2 , v5 ) が存在する．ここで v4 は q3 にマッv について，v がマッチし得るクエリ頂点の集合 (candidates)

チしないことが分かっているので，エッジ (v1 , v4 ), (v2 , v4 ) をC[v] を求める．このステップの目的は，各データ頂点の隣接頂含む埋め込みは存在せず，削除してもよいことが分かる．エッ点から得られる情報を用いて C[v] からなるべく多くのクエリ

ジを削除することでグラフの規模が縮小され，探索に要する時頂点を除外することである．アルゴリズム 1 に候補頂点枝刈り

間が減少する．

処理の全体像を示す．このアルゴリズムは隣接頂点のラベルを

以上のような枝刈りの効果を高めるためには適切に Has-

用いた局所的な枝刈り (1, 2 行目) と，繰り返し処理による枝刈Candidates 関数を定義する必要がある．求められる性質は，

り情報の伝播 (3–9 行目) という 2 つの処理に分けられる．以降「データ頂点 v の隣接頂点がクエリ頂点 q の隣接頂点にマッチ

でこれら 2 つの処理について詳しく説明する．

し得る」ことを偽陰性なく判定すること，偽陽性が少ないこと，

3. 1. 1 隣接頂点のラベルを用いた局所的な枝刈り計算が軽量であることの 3 点である．考えられる条件式の中で局所的な枝刈りではデータ頂点 v とクエリ頂点 q のラベルに最低限満たすべきものとしては，v の隣接頂点がマッチし得る

加え，特定のラベルを持つ隣接頂点の出現回数に着目してマックエリ頂点集合の和集合に q の隣接頂点が含まれる，すなわちチする可能性を判定する．すなわち，あるラベル σ について，

N (q) ⊂= C[N (v)]

ラベル σ を持つ q の隣接頂点の数がラベル σ を持つ v の隣接

(2)
∪

′
v ′ ∈N (v) C[v ] とする．

頂点の数よりも大きい場合，q と v はマッチし得ないことを利という条件がある．ただし C[N (v)] =用する．この条件では次数が高いクエリ頂点ほど C から除外さN (q) が大きければ大きいほど，つまり次数が高いクエリ頂点れやすい．v が q にマッチし得ることを IsCandidate(v, q) とほど，この条件を満たすデータ頂点は少なくなる．しかしながら式 2 の定義では，|N (q)| >= 2 の場合に 1 つのデータ頂点表すと，次のように条件を定義できる：と 2 つ以上のクエリ頂点をマッチさせてしまうことによる偽

IsCandidate(v, q) =ℓ(v) = ℓ(q) ∧ ∀σ ∈ ℓ(N (q)), |Nσ (q)| <= |Nσ (v)| .

(1)

陽性を生じる可能性がある．例えば v の隣接頂点 v ′ について′
N (q) ⊂= C[v ] を満たすものが 1 つ存在し，その他の v の隣接頂

ただし ℓ (N (q)) = { ℓ(q ) | q ∈ N (q) }，Nσ (q) は q の隣接頂

点は C[v ′ ] = ∅ であったとする．このとき式 2 は成立するが，点のうちラベル σ を持つものの集合 { q ′ ∈ N (q) | ℓ(q ′ ) = σ }同じ頂点は 1 度しか埋め込みに使用できないため，これは偽陽とする．Nσ (v) も同様である．例えば図 1 においてクエリ頂性である．N (q) に含まれるクエリ頂点をそれぞれ異なるデー

点 q4 はラベル b を持ち，ラベル b と c の頂点に隣接している．

タ頂点にマッチさせる組合せ (単射) が存在することを確認す

従ってラベル b を持ちながらもラベル b の隣接頂点を持たない

れば偽陽性を排除できるが，この処理は計算量が大きい．He′′

データ頂点 v106 は q4 にマッチし得ない，すなわち q4 ̸∈ C[v106 ]ら [7] の方法を用いた場合，繰り返し処理 1 イテレーションあであることがわかる．同様に v107 , . . . , v116 も q4 とはマッチしたりの最悪計算量は，クエリ頂点とデータ頂点の最大次数をそ得ない．隣接頂点の情報を用いた枝刈りでは，このように式 1

れぞれ dmax, dmaxとすると O(|VQ ||VG |(dmax+ dmax)2.5 ) とQ
GQ
Gを用いることでマッチし得ないクエリ頂点とデータ頂点の組合なる．最大次数はグラフの規模が増大するほど大きくなると考せを排除した C を生成する．

えられるため，この計算量は問題がある．

3. 1. 2 枝刈り情報の伝播
次の枝刈り情報の伝播では，局所的な枝刈りの結果を利用しそこで偽陽性の生成数と計算量の間でバランスを取り，提案
手法ではクエリ頂点の隣接頂点のうち同じラベルを持つものがHasCandidates(v, q, C) ={N (q) ⊂∈ ℓ(N (q)), |Nσ (q)| <= |Nσ (v)|)= C[N (v)] ∧ (∀σ
(
{ ′
}
)
′
′
<
>
N (q) ⊂
C[N
(v)]
∧
∀σ
∈
ℓ(N
(q)),
|N
(q)|
σ
= |Nσ (v)| ∧ v ∈ Nσ (v) qα ∈ C[v ] ∨ qβ ∈ C[v ]=2=
ただし qα , qβ は Nσ (q) の中で最も次数が高い 2 頂点．
図2

if |Nσ (q)| = 1
if |Nσ (q)| >=2(3)

関数 HasCandidates の定義

2 つ以下の場合に限り偽陽性を生じさせない条件式を用いる．

の for 文で各データ頂点について並列に処理を行わせる．これ

クエリグラフは一般に小さいため，同じラベルを持つ隣接頂点に対しエッジの削除 (8 行目) はグラフを書き換える処理であるが 2 つ以下になる場合は少なくない．HasCandidates の定義

が，エッジ (v, v ′ ) に対して削除済みの印をつける処理で代替すを式 3 に示す．この定義は 2 通りの場合に分かれている．まずることによりスレッド間の競合を回避することができる．

|Nσ (q)| = 1 の場合は式 2 でも偽陽性を生じさせることがない．

提案手法ではこのように軽量な計算で枝刈りの情報を伝播さそのため式 1 に含まれる隣接頂点数の条件と式 2 を組み合わせ

せていくことにより，隣接頂点の情報のみを用いて C からクエたものを定義として用いる．隣接頂点数の条件を含めるのは，リ頂点を除外していく．

処理の途中でエッジを削除していくので |Nσ (v)| の値が変化す> 2 の場合は，偽陽性を減らすた
るためである．次に |Nσ (q)| =3. 2 埋め込みの探索
埋め込みの探索では枝刈りの結果を利用しつつ埋め込みを列めの条件として 2 つのクエリ頂点 qα , qβ ∈ Nσ (q) に対してそれ挙する．その際，提案手法では 2 つのアイデアに基づいてマッ

ぞれ異なるデータ頂点をマッチさせられることを確認する．式

チング順序を決定する．本節ではその 2 つのアイデアをはじめ

2 の条件によって qα と qβ にそれぞれマッチし得るデータ頂点に述べ，続いてアルゴリズムの詳細を説明する．

が 1 つ以上存在することは確認できているため，qα または qβ

3. 2. 1 探索高速化のアイデアにマッチし得るデータ頂点が 2 つ以上あれば，qα , qβ にそれぞ

1 つ目のアイデアは低次数頂点の隣接頂点から優先してア

れ異なるデータ頂点を割り当てることができる．そのため条件|{ v ′ ∈ Nσ (v) | qα ∈ C[v ′ ] ∨ qβ ∈ C[v ′ ] }| >= 2 が追加されていクセスすることにより部分埋め込みの生成数を削減することる．ここで qα と qβ は，Nσ (q) の中で最も次数が高い 2 頂点をタ頂点の数が最も少ないようなクエリ頂点を順次選択する動選ぶ．なぜならば式 1, 2 ともに次数が高いクエリ頂点ほど C的なマッチング順序によって行われる．例えば図 1 において，から除外されやすい条件であり，そのような希少なデータ頂点

M = {(q1 , v2 ), (q2 , v3 )} であるとき q4 にマッチし得るデータ

2 つ以上に隣接する頂点もまた希少であるためである．

である．これは部分埋め込み M について，マッチし得るデー

頂点は v6 , v7 , . . . , v105 の 100 個である．従ってもし次に q4 の

この処理の最悪計算量は次のように考えられる．アルゴリズム

マッチングを行ったとすると，部分埋め込みも同じく 100 個

1 の 1, 2 行目では v ∈ VG と q ∈ VQ で 2 重のループが行われる．

(M ∪ {(q4 , v6 )}, M ∪ {(q4 , v7 )}, . . . , M ∪ {(q4 , v105 )}) 生成さループ内で使用する IsCandidate 関数はラベル σ ∈ ℓ(N (q))∑
に対する条件確認を含む． q∈V |ℓ(N (q))| <= 2|EQ | なので，1,れる．v3 が高次数の頂点であるため，このように大量の部分埋

2 行目の最悪計算量は O(|EQ ||VG |) である．同様に 4, 5 行目ではv ∈ VG と q ∈ C[v] で 2 重のループが行われる．|C[v]| <= |VQ |

みである．そのため，q3 のマッチングを次に行うほうが部分埋なのでループの回数は O(|VG ||VQ |) である．ループ内で使用なマッチング順序を使用することで部分埋め込みの生成数を削する HasCandidates 関数は，ラベル σ ∈ ℓ(N (q)) について

減することができる．

Q′

め込みが生じる．一方で q3 にマッチし得るデータ頂点は v5 のめ込みの生成数を少なく抑えることができる．このように動的

データ頂点 v ∈ Nσ (v) に対するループによって条件確認を行∑∑う． σ∈ℓ(N (q)) |Nσ (v)| <= |N (v)| かつ v∈VG |N (v)| <= 2|EG |なので，4, 5 行目の最悪計算量は O(|VQ ||EG |) である．よってから先にマッチングを行うことである．これによりマッチン

全体の計算量は O(|EQ ||VG | + |VQ ||EG |) となる．この計算量きる．具体的な説明のため，クエリ頂点 qi1 , qi2 , . . . , qik が環であれば，クエリグラフまたはデータグラフのどちらか片方の状につながった閉路をこの順序でマッチングする場合を考え

サイズが一定である限り，もう片方が大規模化したとしても線

る．最後に qik のマッチングを行う際，閉路における隣接頂形の計算時間増加で押さえることができる．既存手法の計算量

点 qi1 , qik−1 はマッチング済みであるため，qik にマッチする

O(|VQ ||VG |(dmax+ dmax)2.5 ) はグラフのサイズに対して線形Q
G

データ頂点は M [qi1 ] と M [qik−1 ] の両方に隣接していなけれより大きく計算時間が増加することに比べると，提案手法はよばならないという制約が生じる．すなわち，qik にマッチし得り大規模なクエリグラフおよびデータグラフに対応しやすい計

るデータ頂点の集合は M [qi1 ] と M [qik−1 ] の隣接頂点集合の算量となっていることが分かる．

交差 N (M [qi1 ]) ∩ N (M [qik−1 ]) と一致する．実世界のグラフ

2 つ目のアイデアはクエリグラフにおいて閉路を含む部分
グ候補の絞り込みが可能になり，部分埋め込みの数を削減で3. 1. 3 並列化の方針

は一般に疎であるため，特定の 2 頂点に同時に隣接する頂点

局所的な枝刈りと枝刈り情報の伝播のいずれにおいても，各はまれである．もしそのようなデータ頂点が存在しなければデータ頂点に対して条件式を適用し，その結果によってデータ

マッチング不可能ということなので，処理を中断しバックト

頂点自身の情報 (マッチング候補集合 C) を書き換える処理はラッキングを行う．両頂点に隣接するデータ頂点が存在した

容易に並列化することができる．具体的には 1 行目と 4 行目

としてもその数は M [qi1 ] および M [qik−1 ] の隣接頂点数以下

Algorithm 2 埋め込みの探索

チング開始点 qs を決定したら，qs と qs にマッチし得るデータ

入力: クエリグラフ Q，データグラフ G，マッチング候補頂点集合 C ，実数パ頂点の全ての組合せについて Match 関数を呼び出す．

ラメータ c ∈ (0, 1]

Match 関数はクエリ頂点 q ，データ頂点 v に加え，次にマッ

出力: 埋め込みの集合 M
1

K[v, q ′ ] = N (v) ∩ C −1 [q ′ ] for v ∈ VG , q ′ ∈ VQ

2

T = Q の 2-core に含まれる頂点

3

if T =| ∅ then

4
5と (部分) 埋め込み M を受け取り，埋め込みの集合を返却する．
もしマッチング (q, v) を M に追加することでマッチングが完

qs = argminq∈T C −1 [q]

了するならば，その埋め込みを返却する (9–11 行目)．

else

未マッチングの頂点が残っている場合は，次にマッチングを

qs = argminq∈VC −1 [q]Q∪
7 M = v∈C −1 [q ] Match(qs , v, ∅, ∅)s68

M [q] ← v

10

if |M | = |VQ | then11

return {M }

13
14
15
16
17
18
19
20
21

行うクエリ頂点 q∗ を選択する (12–18 行目)．q∗ としては現在の部分埋め込み M においてマッチング候補となるデータ頂点

function Match(q, v, F, M )912が最も少ないものを選びたい．そのために優先度付きキュー Fを用いる．F はマッチング済みクエリ頂点の隣接頂点それぞれに対するマッチング候補の数を保持している．12–14 行目は q

for q ′ ∈ N (q) \ dom(M ) doの隣接頂点を新しく F に追加すると共に，マッチング候補の数′

P = N (q ) ∩ dom(M )′チングを取るクエリ頂点を決定するための優先度付きキュー F|P |−1

F [q ] ← (c/2)′′′

minq′′ ∈P K[M [q ], q ]を更新する．q によって新しく追加されるクエリ頂点，すなわ
ちマッチング済み隣接頂点が q のみであるようなクエリ頂点 q ′if dom(F ) ∩ T =| ∅ then′q∗ = argminq′ ∈dom(F )∩T F [q ]elseq∗ = argminq′ ∈dom(F ) F [q ′ ]F から q∗ を削除()∩
V∗ = q′ ∈N (q∗ )∩dom(M ) N (M [q∗′ ]) ∩ C −1 (q∗ ) \ dom(M )∗∪return v∗ ∈V∗ Match(q∗ , v∗ , F, M )の場合，マッチング候補の数は q の隣接頂点のうち q ′ にマッチし得るものの数である．しかし複数のマッチング済み頂点に隣接し交差によって発見されようとしているクエリ頂点，すなわ′
ち |P | >= 2 であるような q の場合は見積もりの数を使用する．
実際に交差を取ればマッチング候補集合と要素数が分かるが，他のクエリ頂点がマッチング不可能だった場合に交差の結果がであるため，マッチング候補の数を減らすことができる．例
えば図 1 において M = {(q1 , v2 ), (q2 , v3 ), (q3 , v5 )} という部分
埋め込みがある状態において，q4 にマッチする頂点の集合は

N (M [q2 ]) ∩ N (M [q3 ]) = N (v3 ) ∩ N (v5 ) = {v105 } より 1 つまで絞り込むことができる．そのため v3 と v5 の隣接頂点を一つずつ選択して部分埋め込みを生成するよりも高速である．

使われず，計算が無駄になってしまうためである．q ′ にマッチ
(
)
∩
′′
−1 ′
[q ] は次のし得るデータ頂点の数
q ′′ ∈P N (M [q ]) ∩ C
式によって見積もる：( c )|P |−12

min K[M [q ′′ ], q ′ ].

q ′′ ∈P(4)

ただし c ∈ (0, 1] は実数のパラメタ，K[v, q ′ ] は v の隣接頂点の3. 2. 2 埋め込み探索アルゴリズム

うち q ′ にマッチし得るものの数である．式の意味について P

以上のように動的な順序で探索を行うためのアルゴリズムをの要素数を変えながら説明する．まず P = {qi } のとき，式 4

アルゴリズム 2 に示す．アルゴリズムは 1–6 行目で以降の計算

は K[M [qi ], q ′ ] となり，見積もりでない実際のマッチング候補

頂点のペア 1 つを埋め込みに追加し，再起呼び出しを行うこと数を表す．次に P = {qi , qj } のとき，式 4 は(c)
min(K[M [qi ], q ′ ], K[M [qj ], q ′ ])2

でバックトラッキングに基づくサブグラフマッチングを行う．

となる．これは 2 つの隣接するデータ頂点 M [qi ] と M [qj ] のなおアルゴリズム中で使用している C −1 [q] は q にマッチし得

うち，q ′ のマッチング候補である隣接頂点が少ない方の要素数

るデータ頂点の集合 { v ∈ VG | q ∈ C[v] } である．

に c/2 をかけた値となる．c/2 は交差を取った後の隣接頂点集に必要な前準備を行ったあと，7 行目で関数 Match を呼び出す．関数 Match は 1 回の呼び出しごとにクエリ頂点とデータ(5)

前準備における重要な処理はマッチング開始点 qs の選択 (3–6

合に残る要素の割合と考えることができる．また c はデータグ行目) である．マッチングを開始する頂点の数は少ない方が部

ラフ G のクラスタ係数に相当しており，既存の推定手法によっ

分埋め込みの生成数を少なくすることができるため，マッチンて高速に求めることができる [14]．従ってサブグラフマッチン

グ候補となるデータ頂点の数が最も少ないクエリ頂点をマッチ

グの実施時に自動的に求めることも可能である．P が 3 要素以

ング開始点として選択する．この際閉路に含まれる頂点から先上の場合も同様に，q ′ のマッチング候補である隣接頂点が最もにマッチングを行うため，クエリグラフの 2-core 構造を利用少ないものに交差の回数だけ c/2 をかけた値となる．

する．2-core に含まれる頂点は互いに 2 本以上のエッジで接続

マッチング候補数を更新した後，マッチング候補数が最小でされているため，その 2 つの隣接頂点がマッチング済みとなあるようなクエリ頂点を発見する (15–18 行目)．この際，2-core

れば交差によってマッチング候補を得ることができる．2-coreに含まれる頂点で未マッチングのものがある場合は優先的に選は次数 1 の頂点をクエリグラフから取り除く操作を繰り返す

択する．その後実際に隣接頂点の交差をとり，関数 Match をことで得ることができる．その結果を用いてマッチング開始点

再帰的に呼び出す．

を 2-core に含まれる頂点から探す．ただし，クエリグラフが2-core 構造を含まない場合は全てのクエリ頂点から探す．マッ3. 2. 3 並列化の方針
埋め込みの探索の並列化は Cilk [2] 等を用いて関数 Matchの呼び出しを並列化することにより可能である．しかしながら計算コストの小さい関数呼び出しを並列化するとオーバーヘッ
ドが大きくなってしまう．そこで未マッチのクエリ頂点数およ

表 2 提案手法と既存手法のクエリ処理速度．クエリ名のカッコ内は頂点数．数値の単位は queries per second (QPS)．
クエリ

GraphQL

QuickSI

TurboISO

BFS (4)2919.143665.27

14043.16

6357.88

BFS (6)

1804.63

1731.52

DNF

4359.75以上のような手続きによって，高次数頂点に隣接する大量のBFS (8)1314.79

334.587108.223364.74

候補頂点に対するマッチングを動的なマッチング順序によって

BFS (10)1038.14

DNF

DNF

2978.83

避けつつ埋め込みを探索する．

BFS (12)783.93

DNF

DNF

605.11

BFS (14)372.63

DNF

3136.861653.72

び優先度付きキュー F に含まれる頂点のマッチング候補数から計算コストを見積もり，一定の閾値を超えた場合に並列化する．

4. 評

価

本節では提案手法の性能を既存手法と比較するとともに，マッ
チング順序の最適化と候補頂点の枝刈りによる探索空間の削減
効果を評価する．実験には提案手法の逐次処理版プロトタイプ

提案手法

パス (4)

2994.448314.83

21331.37

5734.06

パス (6)

1917.06

5275.7917216.29

4272.02

パス (8)

1406.62

3248.1811084.05

3402.75

パス (10)1070.58

2174.057578.222639.71

パス (12)887.40561.075154.192545.50

パス (14)723.49318.923030.60

2223.82実装を用いる．性能比較は次の 3 つの手法と行う：QuickSI [12],GraphQL [7], TurboISO [6]．QuickSI と GraphQL は様々なサブグラフマッチングアルゴリズムに関する性能調査 [9] において最も高い性能を示した手法である．TurboISO は BFS
によるグラフ要約を行う近年の手法として選択した．QuickSIと GraphQL の実装は文献 [9] の著者より入手し，TurboISOの実装も著者 [6] より入手した．これらは全て逐次処理を行う手法である．実験に用いたマシンは CPU として Intel Corei7-5600U を搭載し，16GB のメモリを持つ．グラフデータは
既存研究 [1, 6, 7, 9, 11] で広く利用されている yeast を用いる．

yeast は 3112 頂点，12519 エッジ，71 種類の頂点ラベルを持つタンパク質相互作用ネットワークである．クエリグラフは既
存研究 [1, 6, 9, 11] に倣い，データグラフからランダムに連結成分を抽出する．本論文では次の 2 種類のクエリを生成した．
（ 1 ）BFS: ランダムに選んだ点から BFS を行い，訪問した頂点から誘導されるグラフ．閉路を含むものやツリーな
ど，様々な形状が現れる．
（ 2 ）パス: 一本道で閉路を含まない開いたパス．
それぞれの種類のクエリについて，頂点数 4, 6, 8,10,12,14 のものをそれぞれ 1000 パターンずつ生成する．以降ではそれら

1000 パターンの平均値を報告する．またクエリによっては膨大な数の埋め込みが存在し列挙に極めて長い時間を要する場合があるため，文献 [6] と同様 1000 個の埋め込みを発見した時点で探索を打ち切る．提案手法のパラメータ (クラスタ係数) c としては yeast のクラスタ係数 0.108 を使用した．

4. 1 クエリ処理速度
最初に提案手法のクエリ処理速度を評価する．表 2 は提案手法および既存手法の処理速度を 1 秒あたりのクエリ処理数(queries per second, QPS) で示したものである．“DNF” (donot finish) は 1000 クエリの処理を 1000 秒以内に完了しなかったことを表す．提案手法は既存手法と比べ特に BFS クエリにおいて高い性能を示している．また BFS クエリとパスクエリの両方においてクエリ頂点数に対する性能低下が緩やかである．QPS では全体として TurboISO が最高性能をマークしているクエリが最も多いものの，TurboISO は BFS の 6 頂点で一度 DNF になったあと 8 頂点および 14 頂点で再び高い処理性能を見せるという不安定な結果になっている．いずれの手法も全く同じクエリグラフのセットを使っているにもかかわらずTurboISO だけがこのような振る舞いを示していることから，

TurboISO は特定のクエリ対して極端に性能を低下させる場合があるのではないかと推測される．提案手法も BFS の 12 頂点と 14 頂点の間で処理性能が逆転する振る舞いが見られるものの，総合的には安定した挙動を見せている．

4. 2 部分埋め込みの生成数
以上のように提案手法は安定した性能を示すことが確認された．ここからはその理由を理解するため，提案手法のみに着目して詳細な調査を行う．なお以降で使用する機能を制限された提案手法では 10 頂点以上のクエリを処理するために長い時間を要するため，4, 6, 8 頂点のクエリのみ使用する．
サブグラフマッチングでは部分的な埋め込みを生成しながらバックトラックによって探索を行うため，部分埋め込みの生成数が性能の指標となる．部分埋め込みには最終的に完全な埋め込みとして抽出されるものと，途中でマッチング不可能である
ことが分かり無駄になるものの 2 種類がある．前者を減らすことはできないが，後者は枝刈りや効率的なマッチング順序で減らすことができる．そこで本節ではアルゴリズム 2 の関数

Match の呼び出しのうち，生成された埋め込みが完全な埋め込み結果に結びつかなかったものの回数を数える．
比較は提案手法のアプローチを有効にした場合と無効にした
場合の 4 パターンで行う．1 つ目に，候補頂点の枝刈り (3. 1
節) と動的なマッチング順序による探索 (3. 2 節) の両方を行う
ものを「提案手法」と呼ぶことにする．2 つ目に，候補頂点の枝刈りのみ行うものを「枝刈り」と呼ぶ．枝刈りを行わない場
合，任意のデータ頂点 v について C[v] は v とラベルが一致す
る全てのクエリ頂点を含む．3 つ目に，動的なマッチング順序のみ用いるものを「順序最適化」と呼ぶ．最適化を行わない場
合もマッチング開始点は同様に選択するが，動的なマッチングは行わずクエリグラフ上の深さ優先探索の訪問順でマッチングを行う．4 つ目に，枝刈りと順序最適化のどちらも行わない場
合を「ベースライン」と呼ぶ．このベースラインは既存手法で言えば VF2 [3] に相当する．
実験結果を表 3 に示す．ベースラインと比べ，提案手法は無駄になる部分埋め込みの数を大幅に減少させていることが分かる．特に 8 頂点のパスでは 4 桁減少させている．さらに枝刈りと順序最適化の結果について見ていくと，それぞれの効果の大小関係はクエリによって異なっている．BFS クエリでは，4 頂

表3

マッチングに失敗した部分埋め込みの生成数．

クエリ

ベースライン

BFS (4)211.55

BFS (6)枝刈りいる．特にマッチングに失敗した部分埋め込みの数 (表 3) にお

順序最適化

提案手法

70.31

163.4032.56

4587.291504.06

501.6841.49

BFS (8)110040.92

42604.63

1122.11157.68

処理 (アルゴリズム 1, 3–9 行目) が行われた回数も調査したが，パス (4)

80.69

0.27

63.82

0.22

いずれのクエリの場合も 3–5 回であり，クエリ毎の傾向は見らパス (6)

374.901.71

189.842.18

パス (8)

11624.19

8.95

709.37

2.49

れなかった．グラフ直径などデータグラフ側の性質に依存して

表 4 枝刈り後に残る候補頂点の総数．カッコ内は「ラベルのみ」に対する残存候補頂点数の割合．

いてパスクエリはゼロに近い数値を示しているため，限界に近い程度まで候補頂点の枝刈りを行えているといえる．繰り返しいる可能性がある．

5. 関 連 研 究

クエリ

ラベルのみ

局所

伝播

サブグラフマッチングはアルゴリズムの改良と並列化というBFS (4)1299.60

1126.23 (86.67%)

298.13 (22.94%)

2 つの方向性で高速化されてきた．特にアルゴリズムの改良に

BFS (6)

1962.27

1629.85 (83.06%)

293.75 (15.00%)

BFS (8)2630.472146.51 (81.60%)

292.08 (11.10%)

パス (4)

1282.401128.03 (87.96%)

299.13 (23.33%)

枝刈りという 2 つのアイデアの組合せがよく研究されている．

パス (6)

1972.30

1659.76 (84.15%)

401.68 (20.37%)

そこで本節ではまず既存のアルゴリズムをマッチング順序最適

パス (8)

2672.012195.40 (82.16%)

498.34 (18.65%)

化と枝刈りの観点から俯瞰し，最後に並列処理手法を紹介する．

おいては主にマッチング順序の最適化とマッチング候補頂点の

5. 1 マッチング順序最適化点のときは枝刈りのほうが部分埋め込みの生成数が少なく，6

最も古いサブグラフマッチングアルゴリズムと言われる Ull-

頂点と 8 頂点では順序最適化のほうが少ない．これは 4 頂点のmann [17] はクエリグラフで与えられたままの順序でマッチン時に順序最適化の効果が弱いというよりも，枝刈りの効果が高グを行う．VF2 [3] はクエリグラフで最初に現れる頂点から順いのだと考えられる．枝刈りでは隣接頂点のラベルがクエリ頂に，マッチング済みのクエリ頂点と隣接するクエリ頂点を順に点とマッチするかどうかを検査するため，直径 2 で閉路を含ま選択する．QuickSI [12] はさらにラベルの出現頻度を考慮し，ないクエリであれば枝刈りの段階で厳密なマッチングを取るこより頻度が小さい (希少な) ラベルを持つクエリ頂点から優先とができる．例えば次数 3 の頂点 1 つと次数 1 の頂点 3 つから的にマッチングを行うことで探索を削減する．TurboISO [6] はなるツリー型のクエリは直径 2 なので，次数 3 の頂点の隣接関

neighborhood equivalence class (NEC) ツリーと呼ばれる構造係を検査するだけでマッチするかしないかを厳密に判定するこへクエリグラフを要約する．NEC ツリーでは同じ頂点群に隣とができる．しかし頂点数が増えてくると枝刈りだけでは厳密接する頂点が 1 つの頂点へとまとめられており，複数のクエリにマッチを取ることができなくなり，代わりに順序最適化の効頂点に対するマッチを一度に行うことができる．マッチング順

果が強く現れてくる．例えばラベル a, b, c から成る三角形の序に関しては，マッチング開始点をデータ頂点にマッチさせた

クエリに対してラベル c, a, b, c, a のデータ頂点から成る開い

のち，そこから BFS を行って各 NEC 頂点に対応するデータ

たパスはマッチしないが，これを枝刈りでは検出することがで頂点数を計測し，探索範囲が少なくなる順序で NEC ツリーをきない．以上のような効果により，提案手法の部分埋め込み生マッチさせる．BoostISO [11] はデータグラフに関しても隣接成数は枝刈りと順序最適化のいずれよりも小さくなっている．

頂点の包含関係に基づく圧縮を TurboISO に対して適用し，計一方，パスクエリではサイズに関わらず枝刈りのほう部分埋算を削減している．さらに CFLMatch [1] はクエリグラフ中のめ込みの生成数は少ない．枝刈りでは閉路の存在を確認できな

密に結合された構造 (コア) に探索空間を大きく削減する効果がいが，パスは閉路を含まないためこの欠点が問題になりにくい．

あることに着目した．具体的にはクエリグラフのコアからマッ

逆に閉路であってはならないところが閉路になっていたケース

チングを行い，その後他の末端構造のマッチングを行うことにが部分埋め込みの生成数に現れていると考えられる．

より，マッチし得ない箇所の計算を早期に打ち切る．

このように，枝刈りと順序最適化のどちらも探索空間の削減

以上の中に 1 頂点のマッチングごとに動的に順序を生成するに貢献している．特に閉路を含まないクエリでは枝刈りの効果

手法は存在しない．TurboISO 以前の手法は 1 つの固定されたが強く表れ，閉路を含むクエリでは順序最適化の効果が大きい

マッチング順序をグラフ全体に対して使用している．TurboISO

ことが分かる．提案手法では 2 つのアプローチを組み合わせる

以降の手法はマッチング開始点をマッチさせてからその他のクことによりどちらのクエリにも対応することができる．

エリ頂点のマッチング順序を決定しているため，その意味では

4. 3 候補頂点枝刈りの効果

動的にマッチング順序を生成している．しかしながら 1 頂点毎

次に候補頂点の枝刈りによって C に含まれるクエリ頂点の数のマッチングで順序を生成しているわけではない．これに対しが減少した割合を求める．結果を表 4 に示す．
「局所」は 3. 1. 1て提案手法では現在進行中のマッチングの状況に応じて探索範

節にある隣接頂点の情報を用いた局所的な枝刈りを，「伝播」は囲が小さくなるように動的にマッチング順序を変更している．

3. 1. 2 節にある枝刈り情報の伝播を意味する．ベースラインでこれにより高次数のデータ頂点に遭遇した際に生じる部分埋めあるラベルの一致のみを用いる枝刈りと比べ，局所枝刈りでは込みの数を抑える．またクエリグラフ中の密に接続された構造

13–18%の削減率に留まっている．クエリグラフが小さいため，

は閉路を含むため CFLMatch と同じ構造に着目していること

隣接頂点数だけで枝刈りできるケースが少なかったものと考えになるが，提案手法は隣接頂点集合の交差でマッチング候補頂られる．しかし伝播を行うことで全体の 77–90%を削減できて点を抽出する点が異なる．

5. 2 マッチング候補頂点の枝刈り
GraphQL [7] と SPath [19] は我々の提案手法でも用いているように，隣接頂点におけるラベルの出現回数をクエリ頂点[3]とデータ頂点の間で比較することによる枝刈りを導入した．

GraphQL はさらに簡易的なサブグラフマッチングを行うこと[4]でマッチング候補頂点を削減する．SPath は事前計算において2 ホップ以上先の隣接頂点まで含めてラベルの出現回数を数え[5]ておくことで枝刈りの効果を向上させている．
提案手法は GraphQL および SPath と近いアプローチをとっ[6]ている．しかしながら提案手法は 2 つの点で異なる．まずそれらの既存手法と異なり，ユーザーによる指定が必要なパラメー
タがない．このパラメータは最適値の発見が難しい上に性能への影響が大きいことが知られている [6]．さらに計算量の小さな枝刈り判定方法を用いることでより短時間に多くの枝刈りを[7]実現している．

5. 3 並列サブグラフマッチング
STwig [15] は分散メモリ環境を対象とした並列アルゴリズムである．クエリグラフを STwig と呼ばれる深さ 1 のツリー構造[8]へ分解し，STwig 毎に並列にマッチングを行った後に，STwig間で同一でなければならない頂点がマッチするよう結合を行う．

STwig は GPU 向けの改良研究 [16] においても基礎となっている．また Gao ら [5] は分散メモリ環境において動的に変化するグラフ向けの近似サブグラフマッチングアルゴリズムを提案

[9]

している．
並列化のアプローチはアルゴリズム毎に大きく異なるが，共通して重要なのはスレッドまたはプロセス間で共有されるデー[10]タの操作を減らすことである．提案手法においてはマッチング
候補頂点の枝刈りを各データ頂点に対して独立に行っているた
め，並列化が容易である．

6. 結

[11]

論

サブグラフマッチングは様々な場面で利用されるが，NP 困難に属し高速化が課題となっている．そこで本論文では次の 2[12]

つのステップから成る高速なサブグラフマッチング手法を提案する．まずステップ 1 ではデータグラフの各頂点について繰り[13]

返し処理によってマッチング候補頂点の枝刈りを行う．そしてステップ 2 では部分埋め込みの生成数を小さく保つようにマッ
チング順序を動的に生成しながら埋め込みを発見する．実験で[14]はこれら 2 つのステップが部分埋め込みの生成数を大幅に削減
し，既存手法の実装に比肩する性能を示すことを確認した．
今後の課題としては更なる評価の実施が挙げられる．

[15]

CFLMatch [1] など最新の手法との性能比較のほか，提案手法の並列処理効率についても調査する．また動的なマッチング[16]

順序の効果を確認するため，次数分布の異なる複数のデータグ
ラフを用いた実験を行う．

[17]
[18]

文

献

[1] F. Bi, L. Chang, X. Lin, L. Qin, and W. Zhang. Eﬃcient Subgraph Matching by Postponing Cartesian Products. Proceedings of the 2016 ACM SIGMOD Conference
on Management of Data, 1:1199–1214, 2016.
[2] R. Blumofe. Cilk: An Eﬃcient Multithreaded Runtime[19]

System. Journal of Parallel and Distributed Computing,37(1):55–69, aug 1996.
L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.
A (sub)graph isomorphism algorithm for matching large
graphs, 2004.
Y. Fang, W. Lin, V. W. Zheng, M. Wu, K. C. C. Chang,and X. L. Li. Semantic proximity search on graphs withmetagraph-based learning, 2016.
J. Gao, C. Zhou, J. Zhou, and J. X. Yu. Continuous patterndetection over billion-edge graph using distributed framework, 2014.
W.-S. Han, J. Lee, and J.-H. Lee. TurboISO: Towards Ultrafast and Robust Subgraph Isomorphism Search in Large
Graph Databases. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data,
SIGMOD ’13, pages 337–348, New York, NY, USA, 2013.
ACM.
H. He and A. K. Singh. Graphs-at-a-time: Query Language
and Access Methods for Graph Databases. In Proceedingsof the 2008 ACM SIGMOD International Conference on
Management of Data, SIGMOD ’08, pages 405–418, New
York, NY, USA, 2008. ACM.
Q. Hu, S. Xie, J. Zhang, Q. Zhu, S. Guo, and P. S. Yu.
HeteroSales: Utilizing Heterogeneous Social Networks to
Identify the Next Enterprise Customer. In Proceedings ofthe 25th International Conference on World Wide Web,
WWW ’16, pages 41–50, Republic and Canton of Geneva,
Switzerland, 2016. International World Wide Web Conferences Steering Committee.
J. Lee, W.-S. Han, R. Kasperovics, and J.-H. Lee. An Indepth Comparison of Subgraph Isomorphism Algorithms in
Graph Databases. Proceedings of the 39th international
conference on Very Large Data Bases, pages 133–144, 2012.
Y. Park, D. Reeves, V. Mulukutla, and B. Sundaravel. Fast
Malware Classification by Automated Behavioral Graph
Matching. In Proceedings of the Sixth Annual Workshop
on Cyber Security and Information Intelligence Research,
CSIIRW ’10, pages 45:1—-45:4, New York, NY, USA, 2010.
ACM.
X. Ren and J. Wang. Exploiting Vertex Relationships in
Speeding Up Subgraph Isomorphism over Large Graphs.
Proc. VLDB Endow., 8(5):617–628, 2015.
H. Shang, Y. Zhang, X. Lin, and J. X. Yu. Taming Verification Hardness: An Eﬃcient Algorithm for Testing Subgraph
Isomorphism. Proc. VLDB Endow., 1(1):364–375, 2008.
H. Shiokawa, Y. Fujiwara, and M. Onizuka. Fast Algorithm
for Modularity-Based Graph Clustering. In Proceedings of
the Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI 2013), pages 1170–1176, 2013.
J. Shun and K. Tangwongsan. Multicore Triangle Computations Without Tuning. In Proceedings of the IEEE International Conference on Data Engineering (ICDE), pages
149–160, 2015.
Z. Sun, H. Wang, H. Wang, B. Shao, and J. Li. Eﬃcient
Subgraph Matching on Billion Node Graphs. Proc. VLDB
Endow., 5(9):788–799, 2012.
H.-N. Tran, J.-j. Kim, and B. He. Fast Subgraph Matchingon Large Graphs using Graphics Processors, pages 299–315.
Springer International Publishing, Cham, 2015.
J. R. Ullmann. An Algorithm for Subgraph Isomorphism.
J. ACM, 23(1):31–42, 1976.
Y. Yuan, G. Wang, J. Y. Xu, and L. Chen. Eﬃcient Distributed Subgraph Similarity Matching. The VLDB Journal, 24(3):369–394, 2015.
P. Zhao and J. Han. On Graph Query Optimization in Large
Networks. Proc. VLDB Endow., 3(1-2):340–351, 2010.