Blog
吉田です。弊社では主に研究開発に携わっていますが、最近は顧問的なポジションになっている気がします。
普段は国立情報学研究所 (NII)という所で研究していて、よく論文を国際会議に投稿するということをします。
先日、CIKMという会議の結果が帰ってきて、今年開催される国際会議の結果が全て出そろったので、思い出話をしてみたいと思います。
紹介する論文の順番は、各会議が開催された(る)順です。
所々、専門用語を説明なしに使っていますがご容赦ください。
Yoichi Iwata and Yuichi Yoshida, Exact and Approximation Algorithms for the Constraint Satisfaction Problem over the Point Algebra. (STACS’13)
初めて東大の岩田君と書いた論文です。
岩田君は弊社でインターンやアルバイトをしていました。
丁度この話をし始めた頃は、NP困難問題を正確に解くアルゴリズムでいくつかブレイクスルーが有って盛り上がっていました。
例えば彩色問題に対するO(2^n)時間アルゴリズムや、ハミルトン閉路に対するO(1.657^n)時間アルゴリズムなどです。
岩田君に彩色問題のO(2^n)時間アルゴリズムを教えてもらった所、結局大事なのは、色を一つずつ追加していくときに「今の色とそれ以外の色」の二つしか区別していないことだと気づきました。
なので「今の色と未来の色と過去の色」の三つしか区別しない問題持ってきたら面白いこと言えるのではないか？ということで考え始めたのが始まりです。
そう考えた時に思いついたのが論文のタイトルにある「Constraint satisfaction problem (CSP) over the point algebra」です。
簡単に言うと、n個変数が与えられて、変数間に”<“とか”≠”の様な制約が与えられるので、変数に整数を入れて、出来るだけ沢山の制約を満たして下さいという問題です。
これだと「今の値と未来の値と過去の値」の三つしか区別しないので上手く行くはずだと思いました。
自然にやるとO(3^n)という計算量になるのですが、岩田君が謎の行列積による高速化をしてくれて良い話になりました。
最終的には近似アルゴリズムも作ったりして論文としてまとめました。
このCSP over the point algebraが取り除く変数や制約の個数kをパラメータとしてFPT、つまりf(k)poly(n)時間で解けるかは、良い未解決問題だと思います。
Ken-ichi Kawarabayashi and Yuichi Yoshida. Testing Subdivision-Freeness: – Property Testing Meets Structural Graph Theory –. (STOC’13)
NIIの河原林先生と去年の4月からぼちぼち研究していた問題です。
論文が完成したのは11月頭でした。
性質検査(Property testing)というのは私の学生時代からの専門分野で、入力がある性質を満たすかそれには”ほど遠い”かを高速に(高い確率で)判定する、という枠組みです。
“ほど遠い”という概念を入れることで、入力サイズに関係ない”定数時間”で検査できるようになったりします。
グラフの性質検査はよく研究されていて、”ほど遠い”の定義にもいくつか流儀が有ります。
その中でこの論文では疎なグラフに適用しやすいモデルを使っています。
理論屋さんなので性質検査の研究のゴールは定数時間で検査できる性質の必要十分条件を得ることなのですが、このモデルではまだそこまで出来ていません。
なので具体例を集めることが大事ということで、河原林先生の得意分野であるグラフマイナーと関連した、Subdivision-freenessという性質が定数時間で検査出来ることを示しました。
河原林先生にsubdivisionに関する性質を教えてもらえながら、それをつなぎ合わせるというスタイルで研究をしていたのですが、その様子がまるでオラクルにアクセスしているみたいで面白かったです(オラクルは理論計算機科学でよく出てくる概念で、それを現実世界で使っているのが面白い)。
グラフはホワイトボードに絵を描きやすくて、きっとこうだろうという直感は簡単に得られるものの、それをきちんと証明するのが大変でした。
締め切り直前の海外出張中に飛行機の中で必死に証明を作っていた覚えがあります。
STOCと言うのは理論業界最高峰の会議なので、これに通ってくれて本当に良かったです。
Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida, Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling. (SIGMOD’13)
東大の秋葉君と岩田君との共同研究で、僕のデータベースデビュー論文となりました。
秋葉君も弊社でインターンやアルバイトをしていました。
リンク先の秋葉君のブログが詳しいですが、内容は「グラフの頂点間の最短距離を実用上効率的に答える効率的なインデックスの構築方法を提案した」というものです。
世の中のグラフの性質を見てみると、基本的に複雑ネットワークと道路ネットワークの二つに大別されます。
この論文で扱っているのは前者で、複雑ネットワークの性質を上手く利用しながら、非常に単純な手法で既存の手法の数百倍のサイズのグラフを扱うことが出来るようになりました。
この論文で気に入っているのは、何故提案手法が上手く行っているかの考察が出来たことです。
複雑ネットワークはcore-fringe構造というのを持ち、多くの頂点間の最短パスはcoreを通り、fringeは木構造に近いことが知られています。
しかもcoreはまた再帰的にcore-fringe構造を持ちます。
この構造があるから我々の手法は効率的であると上手く説明することが出来ました。
個人的には入力やアルゴリズムに対して理解を深めることで、理論と実験のサイクルを回すことが大事だと思っているので、どうしてもこういった考察はやりたいと思っていました。
多くのデータベースの論文は、実験して速くなったから良いでしょと言うスタンスなので、これが査読でどれだけプラス評価を得たかは分かりませんが、個人的な満足度は高いです。
あとこの話は一般受けが良いので、一般人に自分の研究の説明をするときはついついこの話をしてしまいます。
NIIのオープンハウスでポスター発表した時も色んな人に興味を持って貰えました。
Karl Wimmer and Yuichi Yoshida, Testing Linear-Invariant Function Isomorphism. (ICALP’13)
また性質検査です。
まず定義ですが、ブーリアン関数\(f,g:\mathbb{F}_2^n \to \mathbb{F}_2\)が同型であるとは、ある行列\(A \in \mathbb{F}_2^{n \times n}\)が存在して、\(f(x)=g(Ax)\)であることを指すことにします。
今回扱った問題は以下のようなものです。
まずブーリアン関数fがオラクルとして与えられます。これはxを指定するとf(x)を出力してくれる箱が存在すると思って貰えれば良いです。
次に別のブーリアン関数gが与えられます。
こちらはオラクルではなく、完全に見ることができます。
この時にどんなgであれば「fがgと同型であるか、同型からはほど遠いか」を定数時間で検査できるでしょうか？
この問題に対するほぼ完全な解を与えたのがこの論文です。
結果を一言で述べると「gのスペクトルノルムが小さい時」なのですが、まぁ説明は止しましょうか。。。
去年FOCSという会議で、「fとgが同型とはxのビットを入れ替えて同じ関数になること」という定義で似た結果を出しました。
なので同型の定義に行列を使うバージョンでも結果が出せるかなと思って始めた研究です。
割とサクサク終わりました。
始めたのは今年の冬ですが、実働期間は二ヶ月ぐらいだったように思います。
この論文は経緯が面白いです。
最初に別の女性研究者と研究を始めていて、彼女が今回の共著者であるKarlに声を掛けて共同研究することになりました。
僕とKarlは、その時はメールやskypeでしか話していません。
最終的に論文は完成したのですが、彼女自身は引っ越しや転職なども重なり貢献が少ないということで、著者から抜けてしまいました。
なので一度もKarlとは会っていないのに、二人の共著論文が完成してしまいました。
Arnab Bhattacharyya and Yuichi Yoshida, An Algebraic Characterization of Testable Boolean CSPs. (ICALP’13)
これも性質検査の話です。
ここのところCSP(制約充足問題)に凝っていて、CSPと性質検査で何かしたいと思って始めた話です。
具体的には、(ブーリアン)CSPの入力が与えられ、それに対する変数割り当てがオラクルとして与えられるので、その変数割り当てが充足解かを検査するという問題を考えています。
この論文では、どんなCSPで有れば、定数時間で可能、定数時間では不可能だが準線形時間では可能、準線形時間では不可能(=線形時間必要)を、完全に特徴付けることに成功しています。
この研究のスタートは結構古くて博士三年の時だったと思います。
イタリアの性質検査やストリーミングアルゴリズムに関するワークショップに参加したのですが、
その時にArnabにこんな問題解いてみない？と持ちかけたのが始まりだったと思います。
その時は遠足中のバスの中でずっと考えているArnabを見て、やはり海外の研究者(彼はMIT出身)はやる気が違うなぁと思っていました。
それから暫く疎遠になっていたのですが、何故かまた突然メールのやりとりが再開して、大体三ヶ月ぐらいで完成しました。
証明は簡単と言えば簡単ですが、個人的には面白い帰着が作れたなと思っています。
Arnabはその後も奥さんと（新婚旅行も兼ねて？）日本に二週間ぐらい滞在したりしており、割と頻繁に会っています。
奥さんが「地下鉄に夜12時ぐらいに乗ってもビジネスマンらしき人が一杯乗っているのはおかしい。家庭はどうしているんだ。」と言っていたのが印象的でした。
Danushka Bollegala, Mitsuru Kusumoto, Yuichi Yoshida, and Ken-ichi Kawarabayashi, Mining for Analogous Tuples from an Entity-Relation Graph. (IJCAI’13)
ダヌシカさんがERATO河原林巨大グラフプロジェクトのセミナーで発表する機会があり、その後に解きたいと思っている問題を紹介してもらいました。
それは面白いということで、京大の楠本君に実験してもらい、ダヌシカさんに原稿を書いて頂き、投稿したらIJCAIに通ってしまったという論文です。
僕の貢献は極小であると言わざるを得ない。
ダヌシカさんの研究に対する貪欲な姿勢が、自分もそうあって良いんだという安心感を与えてくれました。
Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida, Linear-Time Enumeration of Maximal k-Edge-Connected Subgraphs in Large Networks by Random Contraction. (CIKM’13)
Yosuke Yano, Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida, Fast and Scalable Reachability Queries on Graphs by Pruned Labeling with Landmarks and Paths. (CIKM’13, short)
この二つも秋葉君のブログが詳しいです。
前者はグラフをk枝連結極大部分グラフに分割する話(よくk枝連結成分と書かれているが違うものを指すはず。。。)、後者はSIGMOD’13の最短路クエリを改造して、有向グラフの到達性クエリに答える効率的なインデックスを構築する話です。
どちらも（有るとすれば）僕の貢献は、ラフなアイデアを聞きかじって、更なるヒューリスティクスを考えたり理論的に解析したりしたことです。
前者のアルゴリズムは僕の大好きなKargerのアルゴリズムに似ているということで、結構解析を頑張り、ヒューリスティクスは単なるヒューリスティクスではなくて理論的にも性能が上がることなどを示しました。
ところが査読では「解析が難しすぎる」とネガティブな意味で言われちょっと残念な気持ちになりました。
解析が難しいけど実装は簡単なアルゴリズムを作るのが我々研究者の使命だと思うのだけどなぁ。
後者はThorupの平面グラフに対する到達性クエリの手法に似ていたので、その証明を読んだり周りの文献を調べていたら、割と簡単に任意のH-minor-freeグラフに対して効率的に動作することが示せました。
