グラフをトーラスとか射影平面に描画するアルゴリズムの話

入力として与えられたグラフをsphereとかtorusとか射影平面(N1)にembedできるかどうかを判定し、できるならば具体的に一つembeddingを出力せよという話。nは頂点数。基本的にかなり大雑把な話しかしないので雰囲気だけつかんでくれたらと思う。

K5とK_3,3が平面的グラフの禁止マイナー(obstructionと呼ぶらしい)であるというKuratowskiの定理はあまねく知れ渡っていることであるが、実はTorus上で考えるとこの二つのobstructionはどちらもembeddできることが分かる。ちなみに後で出てくるが、N1描画の時の禁止マイナーなグラフは全部で103種類存在する。

- sphere ... O(n)のアルゴリズムがある。実装されてる。

- N1

   - O(n) ... 複雑すぎて実装むりぽ。

   - O(n^2) ... MR Algorithmと呼ばれるものがある。O(n)を簡単にしたもの。実装済み。

- torus

   - O(n) ... あまりにも複雑。当然実装はされていない。

   - O(n^3) ... JM Algorithmと呼ばれているものがある。めちゃ複雑。実装したよ、ていう人が過去にいたけどそれダウト、って言う人もいる。

   - 2^O(n) ... NM Algorithm 及び Woodcock's Algorithmが有名。Woodcockの方が定数倍的な意味で早いが実装は十分複雑。どちらも実装はされてるぽい(?)

ここに出てきた固有名詞のついてるアルゴリズムはどれも "embedding extension"と呼ばれるアプローチを取っている。

"embedding extension"とは、入力されたグラフGのある部分グラフを"frame"と呼び、基本的には記号Kで表す。まずこれをtorusまたはN1上にframeをembedするところから始まる。

例えばframeとしてはK5やK_3,3と位相同型なグラフを採用することが多い(これらはtorusにもN1上にもembed可能)

このembeddingは定数通りしかないため、それらを全列挙し、各embeddingに対してグラフの残りの部分(K-bridgeと呼ばれる)のembeddingを試してみて、うまくいくものがみつかったらそれを返すというものである。

frameとして簡単なグラフ(例えばただの閉路とか)を採用すれば実装は楽になるが時間計算量は高くなり、複雑なグラフ(K5とか)を採用すれば場合分けがやばいけど時間計算量は落ちる。そこにtrade offの関係がある。

- N1にembedする場合(NM Algorithm)

　frameとしてK5もしくはK_3,3と位相同型なGの部分グラフを採用する。これらのN1上へのembeddingはそれぞれ27、6通りしかない。そして残りの部分を頑張る。

　一般に、曲面にグラフをembedした場合は幾つかの辺で囲まれた面ができる。具体的には、曲面からグラフの線分をハサミで切り取り除いたものを考え、そのそれぞれの連結部分のことを"face"と呼ぶ。

　まずframeを選びN1上にembedしたら幾つかのfaceができ、残りの部分(K-bridge)をどのfaceにembedすれば良いか、という問題が生じてくる。しかし、基本的にK-bridgeを埋め込むことができるようなfaceは高々3通りしかなく、しかも3通りのfaceがあるようなbridgeは定数個しかないことが知られている。そして残りのbridgeについては高々2通りしかなく、その割り当ては2-SATで解ける。そこでこの定数個の3通りの割り当てを全列挙し、それぞれの場合に対して2-SATのインスタンスを生成し、解けば良い。この2-SATはclauseがO(n^2)個あるので、全体としてこの2-SATはO(n^2)で解けるのでNM-AlgorithmはO(n^2)で出来てしまう。

- Torusにembedする場合(NM Algorithm , Woodcock Algorithm)

　NM Algorithmはframeとして閉路を採用する。 グラフの中にK5またはK_3,3と位相同型な部分グラフを見つけこれをKとする。さらにKの中から部分グラフK'をとる。(KがK5ならK'はK4, KがK_3,3ならK'はK_2,3)とする。 このK'には実は"ある良い性質"を持った閉路が必ず一つ以上存在することが分かっていて、その「良い性質を持った閉路」をframeとして採用する。直感的に言うとトーラスの筒のところを一周させるようにframeをembedする。もしグラフがTorus上embeddableならばこのようにして列挙した閉路で探索していくと必ずうまくいくものが見つかるということが保証されている。続きの話を直感的に説明すると、この閉路によってトーラスを切り、筒状の立体を得る。そして残りの部分をこの筒状のfaceに頑張ってembedする。

　しかしN1では各faceに対してその境界を見てみると同じ頂点が2回現れることがない。しかしTorusでは2回現れることがありうる。この違いによってbridgeをfaceに割り当てた後でもembedの仕方が何通りか存在してしまい、計算量が膨れてしまう。ここにN1とTorusの大きな違いがある。

　Woodcock AlgorithmはframeとしてK_5またはK_3,3と位相同型な部分グラフを採用する。embedの仕方とかも全通り列挙してあとはNM Algorithmと同じようなことをやる。

　JM法は理論的には多項式時間O(n^3)で解けるアルゴリズムである。これは、冒頭で言った103種類のobstructionと位相同型なグラフをframeとして採用するらしい。そしてembeddingを全通り試して上手いことやるとO(n^3)で解けるらしいが定数倍などもかなりヤバイらしい。

ちょっと詳細を省きすぎてしまった感があってアレなのでそのうちグラフのembeddingの基本的な事柄について丁寧な記事を書きたい。ところで平面性判定や平面embeddingがO(n)でできるという事実に驚いた。

Graph Golf参加記

　NII主催のグラフコンペティション Graph Golfに助教とM2の先輩と僕の3人チームで参加して優勝し、12/10に札幌で開かれたCANDAR'15にて講演をしました。(めっちゃ高そうな盾とかもらいました！！！)ということでGraph Golfの問題内容や背景、および僕らのとった手法の概略について適当に書いていきます。

前提知識として知っておいてほしい単語は以下の2つくらいです。

• グラフ(点と点が繋がってるアレのこと)
• 次数(頂点に繋がってる辺の本数のこと)

問題内容
　自然数nとdが与えられる。頂点数nでどの頂点の次数もd以下であるようなグラフのうち
1. 直径
2. ASPL
が小さいものを構成せよ。ただし直径が小さい方良く、直径が同じで会った場合はASPLで比較する。

Graph Golfのページを見ればわかるのですが実際には与えられるnとdは決まっていて、このようになっています。

グラフの直径(diameter)は最短経路長のうち最大のものです。

ASPL(Average Shortest Path Length)というのはその名の示す通り最短経路長の平均の値のことで、要するにワーシャルフロイド法などで求めた全点対の距離の平均の値のことを指します。

＊表の各セルのパーセントのところはASPLには理論的に下限があって、その下限に対して今得られているベストなグラフには何パーセントの誤差があるのか、というのを表しています。

問題背景
　この問題は元々はOrder/degree Problemとして有名な問題で、今まで特に有効な手法などは与えられていませんでした。もともとグラフの頂点数(order)、直径(diameter)、次数(degree)の間には関係があって、３つのうち二つを固定してもう一方を最適化するという研究はあって、中でも一番有名なのは直径と次数を固定して頂点数を最大にするDegree/diameter Problemというものです。これについてはCombinatorics Wikiが詳しいです。
　今回のOrder/degree Problemの実用上の応用としてはネットワークトポロジーの設計ひいてはスーパーコンピュータの設計にあります。いわばCPUがn個あってそれぞれはd個のケーブルでつなげることができるとした時に平均ホップ数をできるだけ小さくしたいという設計思想があるわけです。

基本手法
　ナイーブな手法について説明します。まず初期グラフ(n頂点d-regularなランダムグラフ)を生成します。d-regularというのは全ての頂点の次数が等しくdであるという意味です。
　ここで、今持っているグラフから辺を2本選び、それぞれをa-b, c-dとします。その辺を図のようにa-c, b-dとつなげ変える操作をswitchと呼びます。

今持っているグラフに対してswitch一回によって得られる新しいグラフを近傍(neighbor)と呼ぶことにします。この操作によってグラフのどの頂点も次数が変化しないことがわかるので、元のグラフが次数制限を満たしていればその近傍もまた次数制限を満たしていることは明らかです。
　次に今持っているグラフの評価関数(evaluation function) f(G)を定義します。ここではそのグラフのASPL値を評価関数として採用しましょう。
　そうすると、一つの素朴な反復アルゴリズムを与えることはできます。初期グラフからスタートして近傍を取り、評価してその評価値が何かしらの条件(例えば今持っているグラフの評価値より良いなど)を満たしていた時に解を更新していくというものです。
　このように近傍を探索して解を更新していくアルゴリズムの枠組みを局所探索(local search)と呼び、特に評価値が良くなったら即更新、というものを貪欲法(greedy)と呼びます。また、今回のswitchのように2本のエッジを付け替えるものを近傍として定義したgreedyのことを2-opt法と呼び、主に巡回セールスマン問題(TSP : Traveling Salesman Problem)に対する一つの手法として有名です。
　これ以上更新が行えなくなった時の解のことを局所最適解と呼びます。評価関数が凸だったら局所最適解が全体の最適解であることが保証されるのですが、今回はそういうわけではありません。したがって、初期解の場所によっては悪い局所最適解に行き着くこともありうる、という問題点をこの局所探索ははらんでいます。
　さらに、この局所探索は評価関数の呼び出しを非常に大きな回数行います。したがって評価関数の時間計算量が大きな障害になります。今はASPLを評価関数として用いているので時間計算量は各頂点からのBFSによってO(VE)=O(n^2 d)だけかかります。これでは到底現実的な時間では良い解を得ることはおろか局所最適解を得ることすら困難です。
　ということで、この2点をどう克服したかについて簡単に紹介しようと思います。

GPGPUによるASPLの評価
　特にトピックとしてあげるまでもないのですが、ASPLの評価をGPGPUを使って並列化しました。隣接行列のk乗の(i,j)成分はiからjへの長さkのパスの本数を意味しています。したがって隣接行列を2乗、3乗、・・・としていき初めて(i,j)成分が非ゼロになった時のkの値がi-j間の最短経路長になります。実際は累乗の計算はグラフの直径と同じ回数まで求めればよく、あとは行列積をCUDAで書けばOKです。しかも今回は隣接行列がsparse行列(非ゼロ成分の個数が少ない)なので、その点をうまく利用することができます。

ASPLの近似
　このトピックがこの記事のメインとなります。要するに長い時間をかけてASPLを計算するのではなくその近似値を高速に評価しよう、という話です。実はO(1)時間の評価関数を考えました。
　まず前提としてグラフの直径を3に限定します(それ以外の直径のグラフに関してはGPGPUで頑張りました)。Graph Golfでいうとn=10000, d=64といった大規模なグラフをターゲットにします。
　ここで発想のモチベーションがいくつかあるので書いておきます。

• 「switchというちょっとの変化をちょっとの時間で捉えよう」という思想。
• 評価関数自体を求めるのではなく、switchによる評価関数の差分を何かしらのテーブルを使って求めよう。
• 小さい閉路があると望ましくない。

三番目は、辺の本数が決まってる→無駄な辺をなくしたい→同じ頂点対に対して短いパスが多くなったら困る→小さい閉路をなくしたい
というところから来ています。ここでグラフの頂点vを適当に一つとってきてvからBFSでグラフを展開してみましょう。このような感じになります。

　一番上がv、その下の段にはvと隣接している頂点(当然d個)、さらにその下にはvからの距離が2の頂点(個数はグラフに依存。多いほどASPL的に良い)、最後にvからの距離が3の頂点が並んでいます。ここで、もしグラフ(直径は3)に三角形四角形が存在しないと仮定しましょう。すると、距離2の頂点の個数はd(d-1)となり最大になります。したがってASPLの下界を達成し最適なグラフとなります。また、vを含む三角形や四角形があると距離2の頂点数がその分減ってしまい、結果としてASPLに悪影響をおよぼしてしまいます。つまり、グラフの三角形の四角形を減らせば良い、ひいては三角形の個数と四角形の個数を評価関数に採用すれば良さそうじゃね？となってくるわけです。そこで三角形の個数を△、四角形の個数を口として、評価関数を以下のように定義しました :

f(G) = 3△+2口

　3と2がでてくる理由はこの図のように

• 三角形が一つあると(i-j),(j-k),(k-i)の3つのペア
• 四角形が一つあると(a-c),(b-d)の2つのペア

に影響を与えるからです。また、実は直径3のグラフのASPLというのは

　このような関係が成り立つことが証明できます。つまり上で定義したfを減少させるというのはASPLの上界を下げるということにつながります。

O(1)時間で評価

　ASPLはグラフに含まれる三角形と四角形の個数を使って近似でき、それを評価関数に採用すれば良いという話をしました。ここでは、switchによる三角形と四角形の個数の増減をO(1)で評価する方法について説明します。まず前処理として、以下の三つをテーブルとして持ちます。

• A[][] : 隣接行列
• A2[i][j] : iからjへの長さ3のパスの本数
• A3[i][j] : iからjへの長さ3のパスの本数(ただし同じ辺を二度以上通らないパス)

　こうすると、例えばグラフに辺i-jを追加した時に増える三角形の個数はA2[i][j]で取得でき、逆に辺i-jを削除した時に減る三角形の個数もまたA2[i][j]で取得できます。

　四角形の場合もそれぞれA3[i][j]で取得できます。

　　　　　　　

　目標はswitch後の△と口の増減です。そして今持っているのはswitch前のグラフについてのテーブルです。switchという操作はa-b , c-dの削除およびa-d, b-cの追加と捉えることができます。まず三角形についてですが、a-bとc-dを削除する時は大丈夫でしょう。しかしそのあとa-dとb-cを辺を追加する時にはテーブルではa-bは繋がったままの値しか取得できないので、A2[a][d]で増えると想定している三角形の中にはa-bを利用しているものもあります。実際はこれらの三角形は増えることはないので、その分、つまりa-b, a-dを利用する三角形の個数をカウントして引かなければいけません。実際これはA[b][d]と等しくなります。四角形について考えるとさらにややこしくなります。

　調整が必要なのでデバッグとかはかなり大変なのですが、このようにすれば個数の上限をO(1)で評価することが可能になります。

　最後にテーブルの書き換えについての話をします。解を更新するとグラフ自体も変化するためテーブルの値も動的に書き換えなければいけません。詳細は省きますがA2の書き換えはO(d)、A3の書き換えはO(d^2)でできます。

焼きなまし法

　ここまででO(1)で評価できる近似について述べました。これを使うとn=10000 d=64のグラフでも、いろいろなテクニック(多くの三角形四角形に含まれてる順で近傍を探していく)を使えば、3時間ちょっとで局所最適解にたどり着きます。しかしやはりより良い解を得るためにgreedyではなく焼きなまし法を使うことができます。実際Graph Golfの問題に置いては焼きなまし法はかなり有効で、greedyで得られる局所最適解と比べてかなり良いグラフを得ることができると経験的にわかっています。実際私たちも一位をとったほとんどのグラフは焼きなまし法で得ることができました。

まとめ

• 三角形と四角形の個数でASPLを近似できる
• この事実を使うとO(1)の評価関数を設計できる
• 焼きなまし法は強い
• 北海道は寒い

発展

　実は、直径が3のグラフのASPLの近似はさらに良いものがあります。というか結構簡潔で美しい等式が証明できます。(それは三角形四角形の個数以外にも幾つかの図形の個数を用いるのでO(1)で評価できるとは限りませんが...)

　この辺の細かいことは論文に書こうと思っています。

東大受験記

2015年の夏に
東京大学大学院情報理工学系研究科数理情報学専攻
を受験したので書いてみようかなと思いました。2015年1月から振り返ります。

1月 : 親に東大行ってみたいと伝える。
2月：春休み突入。なんか友人の一人が線形代数勉強してるとか言っててこわ・・・と思いながら自分も線形代数の復習を始める(斎藤正彦の本)
3月：おもむろにTOEFLを調べた結果、どうやらパスポートが必要だということに気づく。そしておもむろに自分のパスポートの期限が切れていたことに気づく。
4月：新学期に入り線形代数の勉強に飽きる。パスポートを作る。初めて都庁に行った。議員になりたいと思った。パスポートを作って満足し、TOEFLの申し込みをどんどん先延ばしにする。
5月：いつまでにTOEFL受ければいいのかを考え始める。調べた結果かなりヤバイということに気づく。慌てて申し込む。
6月：Graph Golfというコンペティションが始まり、熱中する。TOEFLを受けてあまりの難しさに抱腹絶倒する。Graph Golfに熱中する。
7月：過去問に取り掛かる。おもむろに絶望する。現実逃避にGraph Golfを頑張る。TOEFLのスコアレポートが東大に届いていないことが判明。おもむろに絶望する。
8月：なんとかTOEFLが間に合う。過去問に取り掛かるものの半分も解けないことに気づく。現実逃避にGraph Golfを頑張る。

試験1日目(共通数学)：
　完全に諦めてもう試験をばっくれてしまおうと思ったもののさすがに良心が痛むので記念受験しに行く。とりあえず休憩時間は「夜は短し歩けよ乙女」を読む。問題を読んでおもむろに解く。

試験2日目(専門数学)：
　1日目で思ったより答案が埋められたので受験会場に行くことを決意。「夜は短し歩けよ乙女」を読む。問題を読む。すると競プロとかでよく眼にするデータ構造に関する問題が出題されているのを見て勝利の予感を感じる。おもむろに手を動かして気づいたら他の問題の答えが出来上がっていたことに気づく。
　試験終了間際になって色々ミスをしていたことに気づくものの、当初の想定よりもかなり出来が良かったので嬉しく思った。しかし受かるとは思えなかった。

口頭試問：
　どうせ落ちると思っていたので「夜は短し歩けよ乙女」を携えながら普通の私服で会場に向かう。すると周りの人がみんなスーツでビビる。

合格発表：
　なんかTwitterみたらTLで合格番号の紙の画像が貼られていたのを見つける。なぜか自分の番号が載っているのを確認。一応自分の目で確認する。最後に自分の指導教員が自分の第一志望の先生であることを確認して喜ぶ。

教訓：
・割とかなり早い段階から準備していたがTOEFLの申し込みが非常に遅れてしまったことが非常に悔やまれる。
・そもそもTOEFLの対策を全くしなかったというのは論外だと思う。
・過去問が解けないからと言って無意味に絶望してもしょうがない。
・ダメ元でも受験会場には行ってみるべき。
・東工大よりも喜ぶ親戚は多い。

やっていてプラスになったなと思ったこと：
・線形代数(斎藤正彦)
・東工大の院試の過去問(割とかなりやってて、東工大を解けるようになるために色々勉強しようと思って色々勉強したら色々知識が増えた)
・「エレガントな問題解決」(オライリーの本)