CIKM'13 に論文採択×2

執筆した論文が 2 本同時に国際学会 CIKM'13 (ACM International Conference on Information and Knowledge Management) に採択されました．CIKM は情報検索，データマイニング，データベースの３つの分野が合わさっている大きな会議です．Full paper での採択は競争が厳しく，去年の採択率は 13% だったのですが，今年はちょっと上がって 17% (=143/848) だったようです*1．今回の 2 本の論文は，1 本が Full paper としての採択になりましたが，もう片方は Short paper での採択になりました．

発表は，10 月末にサンフランシスコです．以下，2 本の論文を簡単に紹介します．

Linear-Time Enumeration of Maximal k-Edge-Connected Subgraphs in Large Networks by Random Contraction (Full paper)

研究室同期の岩田と NII の吉田さんとの共同研究です．極大 k 枝連結部分グラフを列挙するアルゴリズムです．言い方を変えると，頂点集合をサイズ k 未満のカットで分割します．

我々のアルゴリズムは，非常にシンプルな乱択アルゴリズムです．基本は，二頂点をランダムに縮約しながら，次数 k 未満の頂点を発見したらその頂点を切除する（元のグラフで対応する辺を除去する），これを何度か繰り返す，というだけです．これは，有名な Karger の最小カットアルゴリズムを，k 未満のカットを発見させることに特化させたものになります．ただ，最小カット問題では，ランダム縮約ベースのアルゴリズムは実用上は他の物より低速で，実際に使われることはありません．ランダム縮約が実際に実装され高い性能を出している点がこの論文の 1 つ面白い点になると思います．

実際には，そのアルゴリズムに，さらに少しのアルゴリズム的工夫と，高速な実装のための工夫をしています．理論的な解析がまた面白くて，まず Karger が行った解析と同様の解析でイテレーション回数を抑えられるのですが，その上で，グラフにちょっとした仮定を入れると，我々が加えたアルゴリズム的工夫が劇的にイテレーション回数を減らすということが証明できます．実験でのみならず，性能向上を理論的にもある程度説明できているのが面白いと思います．

極大 k 枝連結部分グラフは，興味深いことに，k-core というポピュラーな密部分グラフのモデルと深い関係があります．極大 k 枝連結部分グラフへの分割は，常に k-core への分割の細分になっています．k-core は多くの応用を持つため，極大 k 枝連結部分グラフの列挙も応用があると期待できます．

Fast and Scalable Reachability Queries on Graphs by Pruned Labeling with Landmarks and Paths (Short paper)

研究室の後輩の矢野君（主著者）と研究室同期の岩田と NII の吉田さんとの共同研究です．ついこの前に発表してきた SIGMOD'13 の最短路クエリの論文の続きで，SIGMOD'13 のエントリで最後に言及した後続研究の 1 つです．

到達可能性クエリは，与えられた有向グラフを前処理しておき，「2 点の間に有向パスがあるか否か」という質問に高速に答えるという問題です．最短路クエリ問題に含まれる問題ではありますが，ターゲットとするグラフの性質が異なることから，性能を出すことまで考えると自明な応用とは言い切れないものです．この論文ではまず，SIGMOD'13 論文の最短路クエリ手法 Pruned Landmark Labeling (PLL) について，到達可能性クエリのアルゴリズムとして性能を出すための少しの変更を議論しています．

さらに，到達可能性クエリでは最短路クエリと異なり距離を答えなくて良いという点を活用した，PLL の拡張である Pruned Path Labeling (PPL) という新しい手法を提案しています．基本的なアイディアとしては，「1 本のパスを決めたとして，各点 v から『パスのできるだけ上の頂点でどれに v から到達できるか』『パスのできるだけ下の頂点でどれからなら v に到達できるか』を知っておけば，そのパスを通るパスを持つ二点対については全て到達可能性が答えられるようになる」というものです．PLL ではラベルを付ける相手が頂点だったのに対し，PPL ではそれをパスに一般化しているということです．

こちらも，理論的解析も面白いです．SIGMOD 論文同様，PLL も PPL も木幅が制限されたグラフでの効率性は証明できます．しかし，PPL に限っては，さらに H-minor-free のグラフでの効率性も証明することができます．H-minor-freeness は木幅の制限より一般的な制限と言えるので，PPL は理論的にも PLL を改善しているということが言えます．

*1:ただ，分野によって競争の激しさが結構違うかもしれません．