Improved Techniques for The K-clique Densest Subgraph Problem
この記事は演習3今井研(大規模アルゴリズム選択)の活動記録です。後輩のために先に演習3について少し解説します。演習3は希望研究室(希望が通るかは抽選)3つを1ヶ月ずつ巡って研究を体験する講義です。各研究室あたり4週間の期間がありますが、初週にテーマ決め、第４週に最終発表があるため、活動期間は実質3週間ほどとなります。僕は
- 第１週: 論文を読む(論文はD3の方に推薦していただいたものを読みました)
- 第２週: 実装, 追加のリサーチ
- 第３週: 既存手法の改善
のスケジュールで進めました。 僕の前の期間に今井研演習3で大規模アルゴリズムを選択した友人は、 第２週で既存手法のメモリ使用量を改善し、 第３週で実行時間を爆速にしたそうです。 何れにしても、早めに論文の内容把握と実装を終えて色々と実験できる環境を作ることが大事かなと感じました。他の講義の課題が3年に比べると少ないので比較的ゆとりを持って楽しめます。
Abstract
グラフによって表現できる関係で特徴付けられた集合から密な部分グラフを取り出すタスクは広い応用で重要になります。例えば、DNAのモチーフ検索[2]、social net[3]などに応用されています。 ただし、一般に最大クリークを取り出すことはNP困難であり、現実的な時間で計算することができません[4]。そこで、計算可能な範囲で異なる定式化が多く試みられてきました。その中でも特に、Densest Subgraph Problem[5]は多項式時間で計算可能な定式化として応用されてきました[6]。そして近年、新たな定式化としてK-clique Densest Subgraph Problem[1]が提案されました。この定式化には、1. 多項式時間で厳密解を求められること、2. Densest Subgraphに比べてよりクリークに近い部分集合を取り出せるという特徴があります。この記事では、この定式化の既存の厳密解法、近似解法を、現実のインスタンスに対して実行時間、使用メモリの双方の関点から改善する手法を提案します。
Introduction
無向単純グラフ$G$の頂点集合$V(G)$の部分集合$S$によって誘導されるグラフに含まれるk-Cliqueの数を$c_k(S)$とします。この時、Sのk-clique密度を$\tau_k(S) = c_k(S)/|S|$で定義します。K-clique Densest Subgraph Problemは、グラフ$G$が与えられた時、最大のk-clique密度を達成する頂点集合の部分集合Sを発見する問題として定義します。特に、k=3の場合をTriangle Densest Subgraph Problem (TDS)と呼びます。[1]では、これに対し、多項式時間厳密解法と$1/k$-近似解法を与えています。その中から特に2つをここに記します。以下ではTDSに対して解説しますが、一般のk-cliqueに対して拡張可能です。
先に厳密解法の概要を述べます。ここでは、[9]によって改善されたものを記します。まず、三角形数え上げアルゴリズム[7][8]を用いて全ての三角形を列挙します。続いて、次のような2部グラフ$H$を構成します。$V(H) = {s}\cup{t}\cup V(G)\cup E(G)$。$H$には以下のように容量付き有向辺を加えます。
- $s$から全ての$V(G)$の頂点$v$へ$v$が属する三角形の数と同じ容量を持った辺
- 全ての$V(G)$の頂点$v$から、$v$を加えると三角形をなす辺$e\in E(G)$への容量$1$の辺
- 各辺$e\in E$からその端点$v,w$への容量無限の辺
- 各頂点$v\in V(G)$から$t$への容量$3\alpha$の辺
この$H$に対し、$s, t$の最小カットが$({s}$,${t}\cup V(G)\cup E(G))$になることと三角形密度$\alpha$以上の頂点集合が存在しないことが同値であることが示されます。これを利用して2分探索をすることで厳密解を求めます。頂点集合は最小カットから復元可能で、また、2分探索は$O(\log V)$で終わることが示されます。全体の計算量は$\tilde{O}(c_3(V)^2)$程度になります。また、$O(c_3(V))$程度のメモリを消費します。 続いて、近似解法について述べます。まず、全ての頂点が属する三角形の数を数えます。続いて、最も属する三角形の数が少ない頂点を除きます。この時、この頂点を端点に持つ全ての辺の対を調べることにより、残った頂点の属する三角形の数を更新します。頂点数が3未満になるまで繰り返し、最も三角形密度が高かった時点での頂点集合を出力します。これは$1/3$-近似解法となることが示されています。計算量は$\tilde{O}(nm)$程度です。また、一般のk-clique Densest Subgraph Problemでは、$1/k$-近似解法が提案されています。
Related Work
厳密解法のスキームに対し、samplingを用いて考慮する三角形の数を減らしつつ計算する方法が提案されています[9]。この手法では、TDSでは数十倍、より大きなkでは一万倍ほどの実行時間の高速化と、サンプリングの採択率に比例するメモリ消費量で近似解を求めることができます。しかし、サンプリングの採択率の2乗に反比例する確率で近似精度が保たれないといった欠点があります。提案手法では、厳密解法は厳密解法のまま、また、近似解法は近似率を下げることなく実行時間とメモリ使用量を改善します。
Proposed Method
密な部分グラフであると思われる部分のみを調べれば良いという直感を元に、考慮する頂点、辺、k-cliqueを削減することで高速化を行います。そのために、いくつかの補題を証明します。
Lemma 1:
最適解のk-clique密度がD以上である時、最適解には属するk-cliqueの数がD未満の頂点は含まれない。
proof:
$S$を任意に選んだ最適解とする。$S$の中に、属するk-Cliqueの数が$d’ < D$の頂点$v$があったとする。特に、$v$が属する三角形のうち全ての頂点がSに含まれるものの数を$d(\leq d’)$とおく。この時、仮定より$d\leq d’< D \leq \frac{c_k(S)}{|S|}$が成立するので、
$\begin{align}
\frac{c_k(S)}{|S|}-\frac{c_k(S-{v})}{|S|-1}
&= \frac{c_k(S)}{|S|}-\frac{c_k(S)-d)}{|S|-1}
&= \frac{|S|d - c_k(S)}{|S|(|S|-1)}
&< 0
\end{align}$
これは$S$が最適解であることに矛盾する。
Lemma 2:
最適解には1つの連結成分に含まれるものが存在する。
proof:
最適解$S$が辺で結ばれない$S=S_1+S_2$という2つの成分に分解できたとする。一般性を失わず、$\frac{c_k(S_1)}{|S_1|}\leq \frac{c_k(S_2)}{|S_2|}$と仮定して良い。この時、
$\begin{align}
\frac{c_k(S)}{|S|}-\frac{c_k(S_1)}{|S_1|}
&= \frac{c_k(S_1)+c_k(S_2)}{|S_1|+|S_2|} - \frac{c_k(S_1)}{|S_1|}
&= \frac{|S_1|c_k(S_2)-|S_2|c_k(S_1)}{|S||S_1|}
&\leq 0
\end{align}$
$S$の最適性より、$S_1$も最適解。$S$に含まれる頂点は有限かつ$|S_1|<|S|$であるので、$S_1$に対して以上の議論を繰り返し適用することにより、最適解であるような連結成分を得る。
上の2つの補題により、一度k-cliqueの数え上げを行い不要な頂点を除いた後で連結成分分解を行い、連結成分ごとに最小カットを考えれば十分であることが考えられます。この不要な頂点の除去は定数回繰り返すことでさらに効果を高めることができます。この手法により、同時に考慮する頂点、辺、k-cliqueを削減できるため、実行速度とメモリ消費量が共に改善されることが期待されます。また、2分探索のフェーズでの最大値は、既存手法の$\frac{(V-1)(V-2)}{6}$[1]より改善することができます。
Lemma 3:
各頂点が属するk-cliqueの数の最大値を$M$とする。この時、最適解のk-clique密度は$\frac{M}{k}$以下。
proof:
$S$を任意の最適解とする。$S$の各頂点が$S$内で属するk-cliqueの数の和は高々$M|S|$である。これはk頂点分の重複を許しているため、$c_k(S)$は高々$\frac{M|S|}{k}$。よって、$S$のk-clique密度は高々$\frac{M}{k}$。
続いて、近似解法について解説します。既存の手法では頂点を除くたびにk-cliqueの数え直しを行います。しかし、k-cliqueを数え上げた時に各頂点が属するk-cliqueを各頂点に保存しておけば、k-cliqueの数え上げを除いた実行時間はおおよそ$\tilde{O}(c_k(V))$となります。ただし、メモリも$O(c_k(V))$消費してしまいます。そこで、近似解法も２分探索のスキームに当てはめることで考慮するk-ciqueの数を減らすことを考えます。
Lemma 4:
属するk-cliqueの数が$\alpha$未満の頂点を除いてから各連結成分に対して$1/k$-近似解法を適用し、得られたk-clique密度が最大の部分グラフのk-clique密度が$\alpha/k$以上であったとする。この時、この部分グラフは$1/k$-近似を達成する。
proof:
最適解のk-clique密度が$\alpha$以下であるならば主張は明らか。そうでない場合を考える。この時、lemma1, 2より、ある連結成分が存在し、そこにこの最適解が含まれる。これに対して$1/k$-近似解法を適用しているので、得られた部分グラフは$1/k$-近似を達成している。</p>
よって、閾値$\alpha$を$\alpha=(\alpha+min)/2$のように減らしながらlemma4の条件が満たされるまで無駄な頂点の除去、連結成分分解、高速な$1/k$-近似解法を繰り返せば全体の実行時間と消費メモリが改善されることが期待されます。また、既存の高速化手法[9]は2分探索のスキームを要求するため既存の近似解法に対しては適用できませんが、この新たな近似解法では容易に組み合わせることができます。
Experiments
実験は1台のマシン上でIntel Corei7 6700Kで行いました。時間の計測はボトルネックとなる2分探索のwhile loopに入ってから抜けるまでを計測しています。また、実験は全てk=3の場合のみで行なっています。三角形の数え上げには[10]、フローにはDinic’s Algorithm[11]を用いました。[9]のようにPush Relabel Algorithm[12]を用いなかった理由は僕の怠惰以外にはありません。
datasetは以下の7つを用いました。karate[13], C-elegans[14], polblogs[15], CA-HepTh[16], soc-slashdot0902[17], dblp[18], web-Google[19]。
速度:
| dataset | V | E | 三角形数 | 既存厳密(ms) | 提案厳密(ms) | 既存近似(ms) | 提案近似(ms) |
|---|---|---|---|---|---|---|---|
| karate | 35 | 78 | 45 | 2 | 0 | 0 | 0 |
| C-elegans | 131 | 687 | 639 | 60 | 42 | 2 | 1 |
| polblogs | 1,224 | 16,715 | 101,043 | 9,397 | 2,329 | 377 | 35 |
| CA-HepTh | 9,877 | 25,973 | 28,339 | 1,841 | 112 | 104 | 3 |
| soc-slashdot0902 | 82,168 | 504,230 | 602,592 | 137,071 | 12,410 | 23,906 | 116 |
| dblp | 317,080 | 1,049,866 | 2.22438E+06 | 165,402 | 6,243 | 9,026 | 278 |
| web-google | 875,713 | 4,322,051 | 1.33919E+07 | / | 72,152 | 251,130 | 564 |
同時に考慮した三角形の数の最大値:
| dataset | 三角形数 | 提案厳密 | 提案近似 |
|---|---|---|---|
| karate | 45 | 28 | 16 |
| C-elegans | 639 | 547 | 326 |
| polblogs | 101,043 | 62,451 | 27,461 |
| CA-HepTh | 28,339 | 4,960 | 4,960 |
| soc-slashdot0902 | 602,592 | 213,490 | 101,234 |
| dblp | 2.22438E+06 | 240,464 | 240,464 |
| web-google | 1.33919E+07 | 134,076 | 38,319 |
出力された解の三角形密度の3倍:
| dataset | 提案厳密 | 提案近似 |
|---|---|---|
| karate | 8.0041 | 8 |
| C-elegans | 19.4999 | 18.7059 |
| polblogs | 986.471 | 882.405 |
| CA-HepTh | 465 | 465 |
| soc-slashdot0902 | 2383.6 | 2172.52 |
| dblp | 6328 | 6328 |
| web-google | 1337.45 | 1334.17 |
使用メモリ(psコマンドで見た概算):
| dataset | 既存厳密 | 提案厳密 | 既存近似 | 高速近似 | 提案近似 |
|---|---|---|---|---|---|
| web-google | 10.4 GB(途中で打切) | 3.65 GB | 336 MB | 3.65 GB | 384 MB |
各手法の比較(厳密解法, datasetはdblp):
| 項目 | naive | 連結成分分解のみ | 頂点の除去のみ | 提案手法 |
|---|---|---|---|---|
| 速度(ms) | 150,563 | 171,394 | 9,393 | 6,286 |
| 同時に扱った三角形数 | 2.22438E+06 | 2.22438E+06 | 412,164 | 240,464 |
各手法の比較(近似解法, datasetはweb-Google):
| 項目 | naive | 連結成分分解のみ | 頂点の除去のみ | 提案手法 |
|---|---|---|---|---|
| 速度(ms) | 81,181 | 84,312 | 9,393 | 6,286 |
| 同時に扱った三角形数 | 1.33919E+07 | 1.33563E+07 | 189,442 | 38,319 |
| 出力の三角形密度*3 | 1262.28 | 1253.04 | 1253.04 | 1334.17 |
他のデータセットでも提案手法を適用すると近似精度が向上しました。解の候補となるものが多くなることや同時に一つの連結成分しか考えないことなどが寄与していると考えられます。
Conclusion
K-Clique Densest Subgraph Problemに対し、それを改善する手法を提案し、それが現実のインスタンスに対して高速かつ省メモリに動くことが実験により実証しました。今後の課題として、グラフのクラスを制限した際の計算量のより良い上界、近似解法での閾値の減らし方の工夫、近似解法とgraph sparsifier[9]とを組み合わせた際の精度保証などがあります。
Acknowledgement
この分野の論文や概念を多く紹介していただいた今井研D3の大阪さんにお礼申し上げます。
References
[1] C. E. Tsourkakis. The K-clique Densest Subgraph Problem. In WWW 2015.
[2] E. Fratkin, B. T. Naughton, D. Brutlag, S. Batzoglou. Motifcut: regulatory motifs finding with maximum density subgraphs. Bioinformatics, 22(14):e150–e157, 2006
[3] A. Gionis, F. Junqueira, V. Leroy, M. Serafini, I. Weber. Piggybacking on social networks. Proceedings of the VLDB Endowment, 2013
[4] Karp, Richard M. Reducibility among combinatorial problems. In Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations, New York: Plenum, pp. 85–103, 1972
[5] A. V. Goldberg. Finding a maximum density subgraph. Technical report, University of California at Berkeley, 1984.
[6] E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. In
SODA, 2002.
[7] A. Itai and M. Rodeh. Finding a minimum circuit in a
graph. SIAM Journal on Computing, 7(4):413–423,
1978.
[8] A. Bjo ̈rklund, R. Pagh, V. Williams Vassilevska, and U. Zwick. Listing triangles. In Proceedings of 41st International Colloquium on Automata, Languages and Programming (ICALP), 2014.
[9] M. Mitzenmacher, J. Pachocki, R. Peng, C. E. Tsourkakis, and S. C. Xu. Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling.
[10] N.Chiba and T.Nishizeki. Arbocity and subgraph listing algorithms. In Society for Industrial and Applied Mathematics 1985.
[11] E. A. Dinic. Algorithm for solution of a problem of maximum flow in a network with power estimation. Doklady Akademii nauk SSSR. 11: 1277–1280. 1970.
[12] A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. In Journal of the ACM (JACM), 35(4), pages 921–940, 1988.
[13] http://konect.uni-koblenz.de/networks/ucidata-zachary
[14] https://snap.stanford.edu/data/C-elegans-frontal.html
[15] https://networkdata.ics.uci.edu/data.php?id=102
[16] https://snap.stanford.edu/data/ca-HepTh.html
[17] http://snap.stanford.edu/data/soc-Slashdot0902.html
[18] https://snap.stanford.edu/data/com-DBLP.html
[19] http://snap.stanford.edu/data/web-Google.html