超グラフ中に含まれる非巡回部分超グラフの効率良い列挙

(1)

超グラフ中に含まれる非巡回部分超グラフの効率良い列挙

◯和佐州洋¹，有村博紀¹，宇野毅明²，平田耕一³

1. 北海道大学大学院情報科学研究科 2. 国立情報学研究所

3. 九州工業大学大学院情報工学研究院

(2)

超大規模超グラフの存在

•

関係データベースのスキーマ

•

_{購買バスケットデータ}

•

文献データの共著関係

興味深い部分構造が欲しい

背景

(3)

問題: 非巡回な部分超グラフの列挙

与えられた超グラフHに含まれる，

連結かつ非巡回な部分超グラフを列挙せよ．

e

5

e

¹

e

⁶

e

³

e

⁴

e

²

1 3 6

4 5

10 7 8

9 2

入力超グラフH Hの連結かつ非巡回な

部分超グラフすべて

列挙

(4)

超グラフ

超グラフ H = (V, E)

•

頂点集合V = {1, ... , n}

•

超辺集合E = {e1, ... ,em}

超グラフのサイズ ||H||:

• Eの全超辺の頂点数の和

部分超グラフS

• Eの部分集合である超辺集

合S Eをいう．

• Sが誘導する超部分グラフ

を表す．

入力超グラフ H = (V, E)

e

5

e

¹

e

⁶

e

³

e

⁴

e

²

1 3 6

4 5

10 7 8

9

2

(5)

超グラフ

超グラフ H = (V, E)

•

頂点集合V = {1, ... , n}

•

超辺集合E = {e1, ... ,em}

超グラフのサイズ ||H||:

• Eの全超辺の頂点数の和

部分超グラフS

• Eの部分集合である超辺集

合S Eをいう．

• Sが誘導する超部分グラフ

を表す．

入力超グラフ H = (V, E)

e

5

e

¹

e

⁶

e

³

e

⁴

e

²

1 3 6

4 5

10 7 8

9 S 2

(6)

超グラフの連結性

超辺eとfが隣接

•

eとfが空でない交わりe f を持つ．

超辺eとfが連結

•

eからfへ長さ0以上の隣接した超辺列が存在する．

超辺集合Sが連結

•

すべての2つの超辺が互いに連結していること．

e

5

e

¹

e

⁶

e

³

e

⁴

e

²

1 3 6

4 5

10 7 8

9 2

入力超グラフ

H = (V, E)

(7)

超グラフの巡回性

ベルジュ閉路

•

_系列π=(e1, v1, ..., ek, vk)

•

e1, ..., ekは互いに異なる超辺

•

_v1, ..., vkは互いに異なる頂点

•

各i = 1, ..., kについて，頂点vi

はeiとei+1に共通に含まれる．

ただし，ek+1 = e1とする．

超辺集合Sがベルジュ非巡回

• Sが長さ2以上のベルジュ閉路

を含まないこと．

e

5

e

¹

e

⁶

e

³

e

⁴

e

²

1 3 6

4 5

10 7 8

9 2

入力超グラフ

H = (V, E)

(8)

ベルジュ閉路の例

e

⁵

e

¹

e

²

1 3 6

5

8 9 2

e

5

e

6

10 8

9 2

長さ3の閉路

長さ2の閉路

定義よりこれも閉路！！

（注意：超グラフの他の巡回のクラスでは

e

5

e

¹

e

⁶

e

³

e

⁴

e

²

1 3 6

4 5

10 7 8

9 2

入力超グラフ

H = (V, E)

(9)

超グラフの非巡回性の階層

様々な非巡回超グラフのクラスが定義されている．

一般から特殊へ．

•

α-非巡回（一番広いクラス）

•

_β-非巡回

•

γ-非巡回

•

ベルジュ非巡回（一番狭いクラス）

(10)

問題: 非巡回な部分超グラフの列挙

e

5

e

¹

e

⁶

e

³

e

⁴

e

²

1 3 6

4 5

10 7 8

9 2

超グラフH Hの連結かつ非巡回な部分超グラフすべて列挙

与えられた超グラフH=(V, E)含まれる，

連結かつ非巡回な部分超グラフ

（超辺の集合）Sを列挙せよ．

(11)

列挙アルゴリズムの計算量

12

Computational Complexity of Data Mining Algorithms

12

!  Output-polynomial (OUT-POLY)

" Total time = poly(N, M)

!  polynomial-time enumeration, or amortized polynomial-delay

(POLY-ENUM)

" Amotized delay is poly(Input), or

" Total time = M·poly(N)

!  polynomial-delay (POLY-DELAY)

" Maximum of delay is poly(Input)

Complexity of enumeration algorithms

" Idea: Measure the computation time per solution

+ polynomial-space (POLY-SPACE)

Output size M

Delay D

Input

Input size N

Total Time T Algorithm

Outputs

Time

(12)

研究目的

連結かつベルジュ非巡回な部分超グラフの列挙問題を考察する．

多項式遅延・多項式領域の効率のよい

列挙アルゴリズムを与える．

(13)

主結果

与えられた入力超グラフに対して，その連結かつベルジュ非巡回なすべての部分超グラフを列挙する多項式遅延・多項式領域アルゴリズムを与えた．

詳細

•

逆探索手法 [AF93]

•

ベルジュ最大還元系列（本稿で導入）

•

家系木上のバックトラックアルゴリズム．

[AF93] Avis, D. and Fukuda, K.: Reverse search for enumeration. DAM, 65:21‒46, 1993.

(14)

•

Lovász, L: Matroid matching and some applications. J. Comb. Theory, Series B 28(2), 208-236, 1980.

極大α-非巡回部分超グラフの多項式遅延列挙アルゴリズム

•

Daigo, T., and Hirata, K.: On generating all maximal acyclic

subhypergraphs with polynomial delay. In Proc. SOFSEM 2009, LNCS 5404, 181-192, 2009.

グラフ中のk-部分木のO(k)遅延列挙アルゴリズム

•

Ferreira, R. , Grossi, R. , and Rizzi, R.: Output-sensitive listing of

bounded-size trees in undirected graphs. In Proc. ESAʼ11, LNCS 6942, 275‒286, 2011.

木中のk-部分木のO(1)遅延列挙アルゴリズム

•

Wasa, K., Uno, T., Arimura, H.: Constant time enumeration of bounded- size subtrees in trees and its application. In Proc. COCOONʼ12, LNCS 7434, 2012.

(15)

•

Lovász, L: Matroid matching and some applications. J. Comb. Theory, Series B 28(2), 208-236, 1980.

極大α-非巡回部分超グラフの多項式遅延列挙アルゴリズム

•

Daigo, T., and Hirata, K.: On generating all maximal acyclic

subhypergraphs with polynomial delay. In Proc. SOFSEM 2009, LNCS 5404, 181-192, 2009.

•

• 本研究の貢献：

ベルジュ非巡回部分超グラフの多項式遅延・多項式領域列挙

アルゴリズムを初めて与えた．

(16)

アルゴリズム

(17)

復習：逆探索法

{ 1, 2, 3, 4 }

^{の部分集合を列挙}

例:

・親は最大の要素を除いた部分集合

・子は部分集合中の最大要素より大きい要素を加えた部分集合

・根は空集合!

{1} {2}

{3} {4}

{1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4}

{1, 2, 3, 4} {1, 2, 3}

{1, 2, 4}

{2, 3, 4} {1, 3, 4}

[AF93]: Avis, Fukuda, Reverse Search for Enumeration, Discrete Applied Mathematics, 1993.

逆探索法[AF93]は，オブジェクトを列挙するための手法である．

オブジェクトとオブジェクトの間に親を定義する．

親を持たないオブジェクトを根とする．

根から家系木を探索し，解を列挙する．

(18)

アルゴリズムの概要

家系木上を探索することで，非巡回部分超グラフを列挙する．

入力超グラフ H = (V, E)

e

5

e

¹

e

⁶

e

³

e

4

e

²

1 3 6

4 5

10 7 8

9

2

(19)

定義：超辺集合Sの葉

超辺eで，Sからそれを取り除いて得られる部分集合S-{e}と，e自身の共有する頂点がただひとつであるような超辺

葉葉

e

⁶

葉

e

³

e

⁴

e

²

1 3 6

4 5

10 7 8

9

(20)

ベルジュ還元系列

与えられた部分超グラフSから出発し，葉を 1つずつ取り除いて空集合を得る．

定理2：Sが連結かつ非巡回

Sは空集合で終わるベルジュ還元系列を持つ．

S

空集合

除去

除去除去

(21)

定理2の証明のアイディア

補題6：Sが連結かつ非巡回ならば，

葉eが少なくとも1つ存在する．

葉eが存在する

連結かつ非巡回連結かつ巡回

葉eが存在しない

e

6

e

4

e

2

1 3 6

4 5

10 8

9 e

5

e

¹

e

²

1 3 5 6

8

9

2

(22)

ベルジュ還元系列

基本アイディア：空集合からスタートし，ベルジュ還元系列を逆向きにたどって，超辺を追加し，連結かつ非巡回な超辺集合Sを列挙する．

問題点：与えられたSに対して，ベルジュ還元系列が複数存在する！！

S

空集合

除去

除去除去

(23)

解決方法

Sの最大還元系列：途中の各超辺集合で，最大の

葉を取り除くように制限して得られた系列．

性質：Sに対して，最大還元系列は一意．

列挙では，最大還元系列をたどればよい．

S

空集合

除去

除去除去

(24)

家系木

入力超グラフH中の連結かつ非巡回な超辺集合すべてを頂点として含む根付き木F(H)

根は空集合．

逆向き辺：超辺集合 S = R-{e} が超辺集合Rの親であるのは，Rの超辺eがRの最大の葉であるとき

定理3：家系木F(H)は，連結

かつ非巡回である（定理2よ

り）．

(25)

列挙アルゴリズム

家系木上をバックトラックし，

すべての連結かつ非巡回な超辺集合を列挙する．

根から出発する．

現在の親（サイズ k の超辺集合）

Sに，新しい超辺eを追加して，

子（サイズk+1の超辺集合）

R = S

{e} を生成する．

生成された子は，連結かつ非巡回であることが保証されている

（定理1）．

(26)

主結果

定理4：

入力超グラフH=(V,E)に含まれる，すべての連結かつベルジュ非巡回な部分超グラフSを，O(||E ||)領域を用いて，解1つあたり O(||E ||+m|| S N( S )||) 時間で出力する．

ベルジュ非巡回部分超グラフの多項式遅延・多項式領域の列挙アルゴリズムが得られた！！

nは頂点数で，mは超辺数，||E|| はHのサイズ．S N(S)は

Sとそれに接する全超辺集合で，||S N(S)|| = O(||E||)．

(27)

高速化：改良版アルゴリズム

定理5：

入力超グラフH=(V,E)に含まれる，すべての連結かつベルジュ非巡回な部分超グラフSを，O(||E ||)前処理時間とO(||E||)領域を用いて，解1つあたり

O((|f| + |N(f)|)log m) = O((n + m)log m)時間

で出力する．ここに，N( S )は S のすべての超辺の隣接超辺全体の集合を表す．

nは頂点数，mは超辺数，||E|| はHのサイズ．

fは繰り返しで，Sに新しく追加された超辺

(28)

まとめ

連結かつ非巡回な部分超グラフの列挙問題を考察した

•

超グラフには様々な非巡回性の定義があるが，ここでは，特にベルジュ非巡回性を考察した．

多項式遅延・多項式領域の効率のよい列挙アルゴリズム

を与えた．

今後の課題

・α-, β-, γ-非巡回超グラフのクラスへの拡張．

・異なる部分超グラフの定義への拡張（超辺から頂点を除去）．

・最適な遅延時間のアルゴリズム

・実装と実験

(29)

ご清聴ありがとうございました．

(30)

(31)

(32)

Alternative Output法の簡単な説明

出力する順序

0 -> 2- > 3 -> 4 -> 5 -> 1 -> 7 ->

8 -> 9 -> 11 -> 10 -> 12 -> 6 -> ...

出力の間隔が定数になる．

家系木上で，奇数深さでは行きがけ順，偶数深さでは帰りがけ順で，

解を出力する．

1

2 3 4 5

6 7 8

9 10 11

12 13

0

14

(33)

極大なベルジュ非巡回1つ求める

O(|V| + |E|)時間

(34)

非巡回部分超グラフ列挙問題

与えられた超グラフH=(V, E)含まれる，

連結かつ非巡回な部分超グラフ

（超辺の集合）Sを列挙せよ．

Hの連結かつ非巡回な部分超グラフすべて入力超グラフH

e

5

e

¹

e

⁶

e

³

e

4

e

²

1 3 6

4 5

10 7 8

9

2

(35)

•

Lovász, L: J. Comb. Theory, Series B 28(2), 208-236, 1980.

1つの極大α非巡回部分超グラフの多項式時間アルゴリズム

•

Hirata, K., Kuwabara, M., and Harao, M.: On ﬁnding acyclic

subhypergraphs. Fundamentals of Computation Theory, 491―503, 2005.

•

• ベルジュ非巡回部分超グラフ

の多項式遅延・多項式領域列

挙アルゴリズムはまだ知られ

ていない！

(36)

連結かつ非巡回な部分超グラフ

非巡回 = ベルジュ閉路を持たない

e⁵ e¹

e⁶

e³ e4

e2

v¹

v⁶ v3

v²

v4

v5

v¹⁰

v7

v⁸

v⁹

入力超グラフ

(37)

家系木を探索する

親の定義に基づいて，家系木を構築する．

→ 家系木の根から深さ優先探索して，列挙する．

(38)

MaxBorder(S)の決め方

葉と境界頂点を順序付辞書で管理する．

•

挿入と削除にO(log(m))時間

新しく追加する超辺だけに着目して，それに隣接する超辺との交点数計算する．

2 8 6 4

9 1 7

5

(39)

時間計算量の考察

葉と境界頂点を順序付辞書で管理する．

•

挿入と削除にO(τ(m))時間係るものを仮定．

新たに超辺fを追加した時，境界超辺集合B(S {f})と最大の葉を再計算する．

•

B(S {f})の再計算は，fに隣接するものだけでよい．

-

fに隣接する超辺をN(f)とする．

•

_{最大の葉はfになる．}

(40)

超辺―頂点行列

e

1

e

n

e

2

e

1

(41)

効率良いMaxBorderの管理

境界超辺と最大の葉でMaxBorderを管理する．

•

Sの境界超辺集合B(S)を順序付辞書で管理する．

B(S)

小大

最大の葉はdとeの間

d c

…MaxBorderに含まれる超辺

e f g h i

(42)

効率良いMaxBorderの管理

境界超辺と最大の葉でMaxBorderを管理する．

•

Sの境界超辺集合B(S)を順序付辞書で管理する．

B(S)

小大

最大の葉はeとgの間

B(S {f}) _c _d _e _f _h _i

fをSに追加

大小

…MaxBorderに含まれる超辺

e f g h d

c i

g

(43)

時間計算量の考察

e3

e1

e6

e5

e⁴ e² v1

v6

v³

v2

v⁴ v⁵

v¹⁰

v⁷ v8

v9

1

0

e3

e1

e6

e5

e⁴ e² v1

v6

v³

v2

v⁴ v⁵

v¹⁰

v⁷ v8

v9

2 1

1 1

e3

e1

e6

e5

e² v1

v6

v³

v2

v⁴ v⁵

v¹⁰

v⁷ v8

v9

2

2 0 0

e2を追加

e3を追加

S S {e2}

S {e3}

交点数

(44)

時間計算量の考察

e3

e1

e6

e5

e⁴ e² v1

v6

v³

v2

v⁴ v⁵

v¹⁰

v⁷ v8

v9

1

0

e3

e1

e6

e5

e⁴ e² v1

v6

v³

v2

v⁴ v⁵

v¹⁰

v⁷ v8

v9

2 1

1 1

e3

e1

e6

e5

e² v1

v6

v³

v2

v⁴ v⁵

v¹⁰

v⁷ v8

v9

2

2 0 0

e2を追加

e3を追加

(45)

時間計算量の考察

•

B(S {f})の再計算は，fに隣接するものだけでよい．

-

fに含まれる各頂点xについて，xを含む超辺をみて高点数を数える．今までの交点数に，新しく計算した高点数を足し合わせる．

•

時間計算量はO((|f|+|N(f)|)τ(|E|))時間

-

fに含まれている頂点それぞれ1度，隣接する超辺を高々2度見ればよい．

-

τ(|E|)は順序付辞書の挿入と削除にかかる時間

(46)

単純に更新する

更新する際，一からMaxBorderを更新するとO(||E||)時間かかる．

•

Sと隣接する超辺をすべて見るため．

e

8

を追加

よく観察すると，e8

に隣接する超辺のみ変化している．

e

9

e

1

e

2

e

7

e

4

e

5

e

3

e

8

e

10

e

6

e

11

e

12

e

9

e

1

e

2

e

7

e

4

e

5

e

3

e

8

e

10

e

6

e

11

e

12

(47)

高速化：問題点

更新する際，一からMaxBorderを更新するとO(||E||)時間かかる．

•

Sと隣接する超辺をすべて見るため．

e

8

を追加 e

9

e

15

e

2

e

7

e

4

e

5

e

3

e

8

e

10

e

6

e

11

e

12

e

1

e

14

e

9

e

15

e

2

e

7

e

4

e

5

e

3

e

8

e

10

e

6

e

11

e

12

e

1

e

14

(48)

高速化：解決方法

境界超辺の集合B(S)を順序付辞書で管理

•

B(S)に追加・削除するのは，Sに追加した超辺fの隣接超辺

交点数の更新は追加する超辺fの隣接超辺g N(f) 時間計算量はO((|f|+|N(f)|)τ(m))時間

順序付辞書の更新に係る計算量

e

9

e

15

e

2

e

7

e

4

e

5

e

3

e

8

e

10

e

6

e

11

e

12

e

1

e

14 B(S)

e

1

e

7

e

8

e

9 e10 e14

(49)

第88回人工知能基本問題研究会, 沖縄県石垣市, 2013/01/24, 25

高速化

境界超辺の集合B(S)を順序付辞書で管理

•

B(S)に追加・削除するのは，Sに追加した超辺fの隣接超辺

交点数の更新は追加する超辺fの隣接超辺g 時間計算量はO((|f|+|N(f)|)τ(m))時間

48

e

9

e

15

e

2

e

7

e

4

e

5

e

3

e

8

e

10

e

6

e

11

e

12

e

1

e

14

e

1

e

7

e

8

e

9 e10 e14

e

9 e14

e

1

e

7 e12

e

8

をSに追加

-

gの交点数＝今までのgの交点数 + fとgの交点数

順序付辞書の更新に係る計算量

B(S)

B(S {e8})

超グラフ中に含まれる 非巡回部分超グラフの 効率良い列挙