擬似クリークを列挙する 多項式時間遅延アルゴリズム 宇野 毅明 　（国立情報学研究所 　　　　　　　　＆総合研究大学院大学） 2007年3月9日 第111回アルゴリズム研究会

問題定義と動機

密な部分構造 ・ グラフから密な構造を見つけ出す、という手法は、データマイニングやデータ工学を始めとする情報学の分野で非常に基礎的であり、多くの研究で用いられている （クラスタリング・webコミュニティー、 グループ化、カテゴリー発見．．．） ・ 従来、密な構造としてクリーク（特に極大）が重宝されてきた 　 　クリーク・極大クリークは、十分速く列挙できるようになった ・ 次のステップとして、よりモデルを豊かにするため、あるいはエラーやあいまいさ、不完全さに対して頑強な結果を得るため「クリークっぽいもの」の発見が注目されつつある （いくつもの重なり合う極大クリークが１つになる、データにノイズやエラーがあっても大丈夫）

対象： データの関連を現すグラフ （データの項目が頂点、関係のある、類似する項目間に枝） 応用：クラスタリング 対象：　データの関連を現すグラフ （データの項目が頂点、関係のある、類似する項目間に枝） 互いに背反だが、 立場が同じ項目のグループ 類似する、あるいは互いに 関連するグループ ・ データの種類・規模で大きさが変わる ・ 通常、それほど密ではない（次数高々100） ・ 局所的に密な部分が存在 ・ パワー則、スモールワールドが成り立つことが多い

Web コミュニティ発見 Webコミュニティ： 内容や嗜好が似ているweb サイトの集合 だろう　　 （リンクは、似た内容・嗜好のページに貼られるから） サイト サイト ラーメン 好き ラーメン 命 趣味バイク ホンダ バイク好き カワサキ 博多 ラーメン 札幌 ラーメン バイク万歳 ヤマハ バイク人生 ・ ごみページを除いた後のグラフの大きさは100万～1億程度 ・ 平均次数10程度、パワー則が成り立ち、局所的に密

対象： 単語ネットワーク （単語が頂点、単語AとB を組合せて 複合語ができるとき、枝を張る） 類義語群の発見 対象：　単語ネットワーク （単語が頂点、単語AとB を組合せて 複合語ができるとき、枝を張る） 関東 関西 中国 北陸 地方 地区 電力 2部クリークの片側が、 似た意味を持つ単語の集合 ・ 大きなものでも、15万語程度 ・ 通常、それほど密ではない（次数高々200） ・ 局所的に密な部分が存在 ・ パワー則、スモールワールドが成り立つ

対象： 論文・アブストラクトグラフ （論文が片側の頂点、単語がもう 片側の頂点で、論文のアブストラクト が単語を含むときに枝を張る） 類似論文のグループ化 論文A 論文B 論文C 論文D 語1 語2 語3 対象：　論文・アブストラクトグラフ （論文が片側の頂点、単語がもう 片側の頂点で、論文のアブストラクト が単語を含むときに枝を張る） 語：　研究分野を表す単語群 論文：　その分野の論文のグループ ・ 大きなものでも、10万語程度 ・ 通常、それほど密ではない（平均次数高々200） ・ 局所的に密な部分が存在 ・ パワー則、スモールワールドが成り立つ

与えられたグラフの擬似クリークを全て見つける問題を扱う 擬似クリーク（密部分グラフ） ・ 頂点部分集合 S に対して、S の枝密度を (S の頂点誘導グラフの枝数) (|S|-1)|S| /2 - S がクリーク  枝密度は 1 - S が独立集合  枝密度は 0  S の枝密度が高ければ、クリークに近くなる クリークの枝数 頂点の組のうち結ばれているものの割合 閾値 θに対して S が擬似クリーク  (Sの枝密度) ≧ θ 与えられたグラフの擬似クリークを全て見つける問題を扱う

擬似クリークに関わる既存の結果 ・ １つ見つけるのは簡単  空集合、１頂点の集合、枝の両端点が必ず擬似クリークになる ・ 大きさ k の擬似クリークを見つける問題はNP完全  θ= 1 とすると、大きさ k のクリークを見つける問題になる ・ 最も枝密度の高い頂点数 k の部分グラフを見つける問題はNP完全 － O(|V|1/3-ε) の近似率のアルゴリズムがある 　　－ 最適解がある程度濃い、とい条件では O((n/k)ε) 近似 [鈴木徳山] 　　－ 枝数が Ω(n2) ならPTASがある[Aroraら] ・データマイニングなどの分野で、擬似クリークを発見するアルゴリズムはいくつか提案されているが、いずれも完全性がなく、列挙問題として捉えている研究はない

分割法によるアプローチは困難 ・ 列挙アルゴリズムの基本的な構築の仕方として、分割法（分枝限定法）がある ・ 各反復で、ある頂点を含むものと 含まないものに解集合を分割し、 できた集合が空でなければ、 再帰的に列挙を行う v1 v1, v2 解があるか判定 する問題がNP完全

与えられたグラフ G と閾値 θ、頂点部分集合 U に対して、U を含む擬似クリークが存在するかどうかを判定 する問題はNP完全である 困難性の証明 Theorem 1 　　　　　　　与えられたグラフ G と閾値 θ、頂点部分集合 U に対して、U を含む擬似クリークが存在するかどうかを判定 する問題はNP完全である 証明: 大きさkのクリークの存在判定を帰着 2|V|2 個の頂点を追加し、Uとする |V|2 -1 |V|2 θ= +ε 入力グラフ G=(V,E) ・ (U + クリーク) のみが擬似クリーク ・ 大きくなると枝密度が真に増加） ・ εを適当に設定すると、大きさが k 以上のクリークのみが擬似 クリークになる 枝密度 = |V|2 -1 |V|2

????? 果たして本当に困難か？ ・ この証明は「とても濃い」グラフの判定問題が難しいことを 証明しただけ  密度が中くらいのところについては、良くわからない  出力多項式時間アルゴリズムはできるかもしれない θ= 1 θ= 0 出力多項式時間 計算時間が入力の大きさと出力の大きさに対して多項式 困難 簡単 ????? 簡単

多項式時間（遅延）アルゴリズム

・ 列挙する対象の間に、非巡回的な親子関係を定義 逆探索法によるアプローチ ・ 列挙する対象の間に、非巡回的な親子関係を定義 objects 親子関係が導く根付き木を深さ優先探索することで列挙 探索は、再帰的に子どもを見つけることで行えるので、子どもを見つけるアルゴリズムがあれば十分

・ v*(K) ： G[K] の最小次数頂点の中で最小添え字のもの ・ 擬似クリーク K の親を K＼v*(K) で定義 擬似クリークの親 ・ v*(K) ： G[K] の最小次数頂点の中で最小添え字のもの ・ 擬似クリーク K の親を K＼v*(K) で定義 K K の親 ・ K の枝密度 ＝ G[K] の平均次数 ÷(|K|-1) ・ 親は、K から最も枝密度の薄い部分を取り除いたものなので、 やはり擬似クリークになる ・ 親は大きさがちょうど１小さい　　親子関係は非巡回的

子どもの発見 ・ 擬似クリークの親は、頂点を１つ取り去って得られる  擬似クリークの子どもは頂点を１つつけることで得られる 　　（子どもの候補 |V| 個しかない） ・ K∪v が K の子どもである  　 ① 擬似クリークであり 　② K∪v の親が K （つまりはv*(K∪v) = v ） ・ この条件を各頂点について素朴に評価するとO(|V|+|E|) 時間 ・ もう少し速くしましょう

子どもである条件 ・ degK(v): v に隣接する K の頂点の数  degK(v) がある一定値以上であるときのみ、 K∪v は擬似クリークになる （① の条件） ・各反復でdegK(v)を更新し（O(deg(v)) 時間）、その値ごとに分類しておくことで、 ① の条件を満たすものを１つあたり定数時間で見つけられる ・②の条件 v*(K∪v) = v も、degK(v)の値で場合分けするとクリア 　－ degK(v) < K の最小次数  K∪v は必ず Kの子ども 　－ degK(v) > K の最小次数＋１  K∪v は Kの子どもでない

子どもである条件 (2) ・ S(K): K の最小次数の頂点を、添え字順に並べた列 ・ degK(v) ＝ K の最小次数 or ＋１  v が、 　　－ v より degK、添え字ともに小さい頂点はない 　　－ degK(u) ＝ degK(v) かつ添え字が v より小さい u 、および 　　　　degK(u) ＝ degK(v)-1 かつ添え字が v より大きい u 　　　　　は必ず v と隣接 ・ K の頂点を次数順・添え字順に見て、隣接リストをスキャンし、 　 K に含まれない各頂点に対して「隣接しない初めての頂点」 を見つける　　 それと、自分の添え字を比べればよい １反復のチェック・データ更新時間は O(Δ(Δ+log |V|)) となる

計算機実験

実装 実験環境： Pentium M 1.1GHz、256MBメモリ ＋ cywin ＆ C ・ 実装は、単純なものを用いた － degK(v) の更新とグループ分けはするが、並び替えはしない － degK(v)＝ Kの最小添え字 or ＋１ となる頂点に対して、素朴にチェックをする 　　 この条件を満たす頂点はそれほど多くないだろう 　　 隣接しない頂点がすぐ見つかって、頂点１つに対するチェックも結局は短時間でできるだろう

実験に用いたグラフ - 通常のランダムグラフ （確率 p で枝をはる） - 局所的に密なランダムなグラフ （自分と添え字が近い頂点のみに 　- 通常のランダムグラフ 　　（確率 p で枝をはる） 　- 局所的に密なランダムなグラフ 　　（自分と添え字が近い頂点のみに 　　　　確率1/2で枝を張る） 　- ランダムに作成したスケールフリーグラフ 　　（頂点を順に追加し、次数に比例する確率で 他の頂点を定数本選び、枝を張る） 　- 現実のデータ 　　（ソーシャルネットワークデータ）

・ 枝の確率が 0.1 で、頂点数が 200-2000。閾値は90%。時間は百万個あたり。クリーク列挙と比べると10倍程度遅い ランダムグラフ ・ 枝の確率が 0.1 で、頂点数が 200-2000。閾値は90%。時間は百万個あたり。クリーク列挙と比べると10倍程度遅い 次数が大きくなるにつれて、ほぼ線形に時間が伸びる

・ 自分の回り±30頂点に確率が 0.5で枝を張る ・ 100～25600 頂点、閾値は90%。同じくクリークより10倍遅い 局所的に密なランダムグラフ ・ 自分の回り±30頂点に確率が 0.5で枝を張る ・ 100～25600 頂点、閾値は90%。同じくクリークより10倍遅い 次数が変化しないので、時間は伸びない

・ 大きさ10のクリークに１つずつ頂点を加える ・ 次数に比例する確率で他の頂点を10個選び、枝をはる ランダムに作成したスケールフリーグラフ ・ 大きさ10のクリークに１つずつ頂点を加える ・ 次数に比例する確率で他の頂点を10個選び、枝をはる 時間は非常にゆっくりと増加

・ 論文の共著関係を表すグラフ ・ 頂点数は3万、枝数は12万5千、スケールフリー 現実問題 ・ 論文の共著関係を表すグラフ ・ 頂点数は3万、枝数は12万5千、スケールフリー 1個あたりの計算時間は閾値によらないようだ

・ 10000頂点の局所的に密なグラフで、閾値を変化させる 次数が小さくなると、候補が増えるため時間が増大

考察＋α ・ 実際の列挙の時間は、ひとつあたりほぼ定数時間 ・ 理論的なバウンド、最大次数の２乗よりはるかに小さい ・ なぜ現実的には速いのか？ 　－ データの更新の時間は、追加された頂点の次数に線形 　　　 degK を小さくする頂点の次数が大きいとは思えない 　－ 子どもかどうかチェックしなければならない頂点は少ない 　　　 子どもの数の定数倍

まとめ ・ 擬似クリーク（枝密度の高い部分グラフ）を列挙する初の多項式時間アルゴリズムを提案 ・ 分枝限定法的なアプローチは難しいであろうと思われることを、子問題がNP困難となることで証明 ・ 計算実験により、現実的な、疎なグラフに対して有効に働くことを実証 将来の課題： ・ 計算量と現実的な計算時間のギャップを、より良く説明できないか ・ 計算量は減らせないか ・ 困難性の証明を、より小さい閾値に適用できるよう、改良できないか ・ 極大な擬似クリーク、またはそれに類するものが効率良く列挙可能か