August 2016

4vol.

JST ERATO

Kawarabayashi Large Graph Project

NEWSLETTER

研究総括よりE ve rg re e n研究総括

河原林 健一Ken-ichi Kawarabayashi

先日某 番 組で「My Little Lover」の結 成 20 周 年 記 念コン
サートを放送していた。あまりテレビをまじめに見るほうではないのだが、このコンサートは不覚にも？1 時間ほど観てしまった。My

Little Lover が最も売れていたのは、おそらく1995～7 年であり、その頃は自分も二十歳前後の学部生だった。どうもその頃が懐かしくて聞き入ってしまったのだと思う。あの頃は、Glay、スピッツ、シャ乱Ｑ、Mr.Children、そして小室ファミリーが全盛だった。

20 年前からトップ歌手で、過去 20 年間トップで輝き続けている歌手はそう多くはない。実際思いつくのは B’zくらいである（ちなみに私は B’zをBe there から聴いている）。研究の世界でも、20 年間世界の一線で活躍している研究者は非常にまれである。
おおよそ15 年前、私がポスドクだったころ、世界の様々な研究機関を訪問する機会があり、多くのポスドクや学生と知り合う機会があった。その頃から優秀な人や、その後大きな研究成果を挙げた学生とも知り合った。その頃知り合った若手研究者の多くは、若い頃から世界的な研究成果をあげていた。そのうち何人が現在でも世界の一線で活躍しているか？残念ながらほんの一握りである。世界的研究者の元で学位を取った学生でも多くが「ドロップアウト」し、現在研究活動をしていない。長年アカデミアにかかわっているとわかるのだが、年齢を重ねていくと、人の価値観は徐々に変わっていく。また研究よりも、教育、マネージメントなどに時間を多く使わないといけない状況も理解できる。
過去 10～15 年間で、音楽の世界も信じられないくらい変わっ

国立情報学研究所 情報学プリンシプル研究系 教授／ビッグデータ数
理国際研究センター センター長。専門分野は離散数学におけるグラフ彩色問題、グラフ構造理論とアルゴリズム、ネットワークフローとパス問題。
主な受賞に、日本数学会 2015 年度日本数学会春季賞［2015］、第 9 回日本 学 術 振 興 会 賞、第 9 回日本 学 士 院 学 術 奨 励 賞［2013］、ACM-SIAM
Symposium on Discrete Algorithms（ SODA 13 ）Best Paper Award［2013］、公益財団法人船井情報科学振興財団 船井学術賞船井哲良特別賞（アルゴリズム的グラフマイナー理論の研究とその応用）［2011］がある。

たと思うが、情報系の研究分野は信じられないスピードで進化した。当該分野にかかわっている研究者にとっても、信じられないそれこそが相手側に対する最高の「リスペクト」を生むのだろう。

スピードでの変化である。10～15 年間世界の一線で活躍してい研究者の人生は非常に長い。自分の経験から言うと、若いこる研究者は、このスピードでの変化の「最先端」に位置しながらろに研究業績をあげることも重要だが、研究に対する情熱をどの常に新しい問題と向き合い、研究成果を挙げてきた（B’z のようように長年保つか？という方がもっと重要に思う。年齢を重ねてに）。当然ながら、長年の苦労、苦闘、努力の上で成り立ってきいき、そして多くの人生経験をしながら、研究を長年続けていく努た研究業績である。

力こそが「リスペクト」に値するのだと思う。

10～15 年間一線で活躍している研究者同士の関係も、不思

ところで、My Little Lover は、元「夫 婦」のユニットである。

議なことに徐々に変わってくる。私には「ライバル（敵？）」でかつ、今回の 20 周年記念コンサートでは元夫婦二人とも非常に楽しん

ほとんど会話を交わしたことのない研究者が何人かいたのだが、でいるようであり、息もあっていたように思う。傍から見ると元夫

最近お互いに「リスペクト」を感じられる関係になってきた。互い婦は「冷え切った関係」ではなく「20 年間のお互いの労をねぎらに長年の苦労と健闘を称えあう要素が強いのだと思う。そもそもうような関係」のようにも見えた。

10 年以上もライバル関係？であり続けること自体がまれであり、

2016.3.4 成果報告会（学術総合センター）

研究紹介

グラフのハミルトン閉路とその応用

通常、ネットワークは、頂点集合と 2 頂点間を結ぶ辺の集合の対として定義されるグラフという形でモデル化されます。そのため、このグラフ上のさまざまな良い構造が、直接的にネットワーク設計等へと応用されています。私は、この良い構造の代表例である「ハミルトン閉路」を見つけるアルゴリズムについて、研究しています。
図のように、グラフの全頂点をちょうど一度ずつ通り元の頂点に戻る構造を、そのグラフのハミルトン閉路と呼びます。簡単な構造ですが、（1）理論的に面白い性質を持つこと、（2）応用上の都合が良いこと、の二つの理由から、さまざまな研究がされています。例えば、平面上のグラフに対し、ハミルトン閉路を利用して頂点を彩色する方法が 4 色定理との関連から指摘されており、また、効率的なデータ構造の構築や DNA 配列の解析などもハミルトン閉路を用いて行われています。
このように、非常に有用な構造である一方で、与えられたグラフにハミルトン閉路を見つけることは簡単ではないことが分かっています。
（実際に、難しい問題とされて）そのため、グラフのクラスを制限しいる NP- 完全と呼ばれるクラスに属しています。
その性質を用いることで、効率的にハミルトン閉路を見つけることが必要になります。
私は、平面上のグラフや特定の構造を禁グラフ・ネットワークにおける理論と最適化グループ

小関 健太
Kenta Ozeki

国立情報学研究所 特任助教
2009 年 3 月、慶應義塾大学大学院基礎理工学研究科 博士課程修了。2009 年 4 月から2012 年 10 月まで日本学術振興会特別研究員 PD。同年 11 月より現職。グラフのハミルトン閉路を見つけるア

止したグラフなど、さまざまな条件下でハミルトン閉路を見つけるアルゴリズムを提案しています。

ルゴリズムとその応用に関心を持つ。

高速なSATソルバの研究開発

真（True）か偽（False）のどちらかが入るn 個の変数が論理和と論理積で連結された論理式 F（x1, x2, … , xn）があり、この論理式 Fを真にするような変数の割り当てが存在するか調べたいとします。単純にやるなら、n 個の変数に真か偽の値を適当に割り当て、逐一 Fが真になるかどうか調べていけば良いのですが、この場合最悪だと2n 回の調査が必要になり、nが 50を超えると高性能なコンピュータを用いても手が付けられないくらいの計算時間になります。
この問題は充足可能性問題（SAT 問題）と呼ばれ、計算機科学の中でも重要な問題として知られていて、この SAT 問題を高速に解くために多くの研究者が SATソルバの研究開発を行っています。現実世界の様々な問題が SAT 問題に変換可能で、身近な例だと数独等のパズルの求解、産業界だとCPU や OS の開発に SATソルバが使われています。
私の研究は、SAT 問題をグラフとして考え、そのグラフから得られるPageRank やコミュニティ構造等の特徴量を利用した SATソルバの研究開発です。数万以上の変数から構成されるSAT 問題がなぜ高速に解けるのか？という疑問の答えの一つに、変数同士が密に関係しているという、問題の構造をSATソルバが利用していることが考えられてグラフマイニング&WEB&AIグループ

薗部 知大

Tomohiro Sonobe

国立情報学研究所 特任研究員
2013 年 3 月、東京大学大学院情報理工学系研究科博士課程修了。東京大学大学院特任研究員を経て 2014 年 4 月より現職。
逐次・並列 SAT ソルバの研究開発に従事。

います。この構造をグラフ理論の 観 点からとらえ、SATソルバの高速化に取り組んでいます。

ネットワークでの経路探索の問題を考えます。図 A においてスタートからゴールまで到達する経路はあるでしょうか。
（すぐにあると言えますね。
）また、そのような経路は何通りあるでしょうか。これらの問題は大きなネットワークに対しても計算機を使えば早く解くことができるでしょう。
この問題に条件を追加します。図 B のネットワークは、分岐点に番号がついておネットワーク探索と充足可能性問題

り、赤と青の道がちょうど一本ずつ出ています。さて、同じ番号の分岐点からは同じ色の道を使わなければならないとしたら、スタートからゴールまでの経路はあるでしょうか。すぐに思いつく方法は、すべての色の選び方（図 B では 16 通り）を試すという方法です。この方法では、番号の種類が 1 増えると選び方は 2 倍になり、大きなネットワークでは計算機で解いてもなかなか止まりません。
この問題は、「分岐プログラム」という計算モデルに対する「充足可能性問題」と呼ばれています。私はこの問題に対して、単純な方法（すべての選び方を試す）より高速に解く方法を研究しています。
理論計算機科学で重要な問題である「充足可能性問題」を、ネットワークの性質を利用して高 速に解くことができるかが、最も興 味のあるところです。

多種多様なネットワーク構造は、産業界や学術研究だけでなく、一般的な日常生活の中でもごく自然な形で現れます。例えば、道路網、上下水道、あるいは送電網など、それぞれの分野において異なるネットワーク構造が利用されていますが、これらは節点と節点の間に「もの（フロー）」を送るという、共通の目的をもっています。このうち最も一般的なのは、ネットワークを流れるフローの量を最適化すると言う問題です。近年、そのようなフローの耐性と持続性に関する研究に、理論および実践の両面から関心が寄せられています。私が研究しているネットワーク阻止問題およびそれに関連する問題は、複雑ネットワーク・地図グラフグループ

照山 順一

Junichi Teruyama

国立情報学研究所 特任研究員
2013 年京都大学大学院情報学研究科博士課程修了。同年 4月より現職。充足可能性問題や大規模ネットワークに対するアルゴリズムの開発に興味を持つ。

攻撃に対する耐性をもつネットワーク構造の研究

攻撃や障害が発生する状況下で効率的なフローを求めるという問題であり、直接応用に役立てることができます。しかし、残念ながらこの種の問題はすべて、NP 困難という難しい問題であることが知られています。
私の研究目的は、様々な種類のネットワーク構造に対して最適解ないし近似解を求めるアルゴリズムを設計することです。これらのアルゴリズムの特徴は、ネットワーク構造への攻撃を前提として、新たなネットワークの構成の費用および既存のネットワーク維持の費用の最適化を、フローの効率性を保ちながら攻撃の規模に応じつつ可能にするという点です。これらのアルゴリズムによって得られる耐性をもったフローは、フローに関する古典的な研究成果と同様に広範な応用例をもちます。2 次元や 3 次元上のグリッド構造、完全ネットワーク、そしてランダムな構造をもつネットワークにおいては、実験例の97% において最適解を求めることができました。また、巨大なネットワークや複雑なネットワークを対象として、二段階最適化法や局所探索法を用いて近似解法を設計しました。

ネットワーク・アルゴリズムグループ

Jean-François Baﬃer
ジャン フラン ソワ バ フィエ

国立情報学研究所 特任研究員
2015 年 3 月、東京大学大学院情報理工学系研究科博士課程修了。同年 4 月より現職。グラフアルゴリズムを設計すること、特に、攻撃に対する耐性をもつネットワーク構造の研究に関心を持つ。

リサーチアシスタントたちは今… 1
2012年10月のプロジェクト発足以来、現在まで述べ64人（現役16名、OB・OG 48名）もの学生の皆様にResearchAssistant またはProject Assistantとして参加していただいています。OB・OGの中から各グループを代表してお１人ずつコメントをいただきました。

伊藤 伸志

河田 祐樹

現在：NEC データサイエンス研究所 研究員
旧：グラフ・ネットワークにおける理論と最適化グループ RA（RA 期間：2013 年 5 月～2015 年 2 月）

現在：（株）リクルートホールディングス Indeed エンジニア
旧：複雑ネットワーク・地図グラフグループ RA（RA 期間：2013 年 4 月～2015 年 2 月）

私は現在、機械学習・予測に基づく数理

私は現在 Indeed という60カ国 28 言語に最適化の研究をしています。私の研究では、対応する求人検索サービスの会社で、ソフト実社会で収集されるビッグデータを活用して分ウェアエンジニアとして働いています。広告出析・予測を行い、それをもとに最適な判断や計画を導きだす汎用稿の自動化を行うチームに所属し、様々なデータから広告の価格的な人工知能の技術を開発しています。具体的な応用例のひとの調整を行うアルゴリズムや、新たな広告を自動生成するシステム

つとして、小売店舗での商品仕入れ・値引き・広告などの戦略の開発などを行っています。Indeed では多くのテストやログを分の決定があります。店舗で日々収集される商品購買記録から将来析し、開発のサイクルを素早く繰り返すことでよりよいサービスを作の商品需要を予想し、それをもとに今後の戦略を決定することはることを目指しています。これは複雑ネットワーク・地図グラフグルー

普通は人手で行われますが、我々の技術ではこの一連のプロセスプで取り組んできた、実験の結果から理論的解析を行い、その解をコンピュータが自動的に実行し、かつ人間には発見できなかった

析からよりよいアルゴリズムを開発するというサイクルと非常に近い効果（利益）の大きな戦略の導出を可能にします。ここで、より良と感じています。

い戦略を探索するとき素朴な計算方法では数年単位の時間がかまたアルゴリズムという面では、今年から ACM-ICPC という国際かりますが、数理最適化の技術を活用することでそれを数秒にまで大学対抗プログラミングコンテストの日本リージョンの審判団に加削減できることを発見しました。この発見には、河原林巨大グラフわりました。当プロジェクトの関係者も多く参加しており、彼らと共プロジェクトでの他の研究者との交流・議論を通じて、学生時代に大会の運営を手伝い、アルゴリズムに興味を持つ、さらにはそのに得た経験や数理の基礎力が大いに活かされています。

研究に携わる学生を増やすことができればよいと考えています。

今後もプロジェクトでの経験を活かし、数理を実社会に役立てる研究をしたいと考えています。

小西 卓哉

畑中 達彦

現在：国立情報学研究所 特任研究員
旧：グラフマイニング &WEB&AIグループ RA（RA 期間：2013 年 7 月～2015 年 2 月）

現在：東北大学 大学院情報科学研究科
博士課程 1 年（日本学術振興会特別研究員）
旧：ネットワーク・アルゴリズムグループ RA（RA 期間：2014 年 11 月～2016 年 2 月）

私は博士後期課程から本プロジェクトにRAとして参加しました。研究員の方々にアドRAとしてプロジェクトに参加していた時は、バイスをいただきながら、Web 検索で使われ主にグラフアルゴリズムの研究をしていまし

る検索クエリの研究に取り組みました。当時、奈良先端大に在た。退職後は東北大学の博士課程に進学し、日本学術振興会学していたため、普段は Skype 経由のミーティングでしたが、研究特別研究員 DC1として引き続き研究に従事しています。その内容が大詰めを迎えた時期には、2 ヶ月ほどNII に滞在できたため、研はプロジェクトで取り組んでいたものの発展形ということもあり、当究の細部についても相談しやすかったと思います。研究を進める時の研究活動がダイレクトに活かされていると感じます。また、報中で、大学の研究室とは違う視点からアドバイスをもらうことがで告会での数々の研究発表を通じて多くの研究者の方々と交流できき、専門知識以外でも多くのことを学ぶ機会になりました。

たことは、研究だけでなく人生においても非常に貴重な経験だった

現在は本プロジェクトの研究員として Web データを中心に機械と思います。私が博士課程への進学を決めたのも、そういった方々学習とその応用について研究しています。RA の時と同じ研究分の活き活きと研究されてい野ということもあり、当時の経験がダイレクトに役立っています。

る姿に憧れたからです。将現在、機械学習技術は日進月歩で発展していて、同時に新たな来は、私が憧れた研究者

課題や期待される応用分野も増加しています。今後も、これまで像に少しでも近づけるようの経験を活かしつつ、こうした課題の解決に挑戦していきたいとに、そして私自身が誰かの考えています。

目標となれるように、より一層研究に励みたいと思います。

主要な研究成果

2016 年 3月～ 2016 年 7月 国際会議発表論文

論文名Poly-logarithmic Frege depth lower bounds via an
expander switching lemma

著 者
Toniann Pitassi, Benjamin Rossman,
Rocco A. Servedio, Li-Yang Tan

会議名STOC2016, Cambridge, MA, USA,Jun 18-21

Doubly Decomposing Nonparametric Tensor Regression

Masaaki Imaizumi, Kohei Hayashi

ICML2016, NYC, USA, Jun 19-24

Adaptive Budget Allocation for Maximizing Inﬂuence of Daisuke Hatano, Takuro Fukunaga,
Advertisements
Ken-ichi Kawarabayashi

IJCAI2016, NYC, USA, Jul 9-15

Eﬃcient Algorithms for Spanning Tree Centrality

IJCAI2016, NYC, USA, Jul 9-15

Takanori Hayashi, Takuya Akiba, Yuichi Yoshida

Identifying Key Observers to Find Popular Information in Takuya Konishi, Tomoharu Iwata, Kohei Hayashi, IJCAI2016, NYC, USA, Jul 9-15
Advance
Ken-ichi Kawarabayashi
Progressive Comparison for Ranking Estimation

主要受賞

Ryusuke Takahama, Toshihiro Kamishima,Hisashi Kashima

IJCAI2016, NYC, USA, Jul 9-15

2016 年 3月～ 2016 年 7月

受賞年月

受賞者

2016 年 3 月
2016 年 3 月
2016 年 6 月

秋葉 拓哉
畑中 達彦
秋葉 拓哉、矢野 洋祐

受賞名

主催団体名

2015 年度日本データベース学会 上林奨励賞
COMP-ELC 学生シンポジウム 最優秀論文賞
2015 年度人工知能学会 研究会優秀賞

日本データベース学会
電子情報通信学会
人工知能学会お知らせ 当プロジェクトより以下の方が転出されました。
氏

林 浩平

名

転出時期

特任助教

堀田 結孝

特任助教

高口 太朗

特任研究員

Benjamin Rossman 特任准教授

2016 年 3 月2016 年 3 月
2016 年 3 月
2016 年 6 月

転出先

産業技術総合研究所 人工知能センター 研究員
帝京大学文学部心理学科講師

情報通信研究機構 ユニバーサルコミュニケーション研究所
トロント大学研究員

Assistant Professor

イベントの様子2015.12.22～23 情報系 WINTER FESTA～基礎から変える情報分野～（学術総合センター）

2016.3.4 成果報告会（学術総合センター）

2016.5.27～28 国立情報学研究所オープンハウス2016（学術総合センター）

発行：大学共同利用機関法人 情報・システム研究機構 国立情報学研究所 ビッグデータ数理国際研究センター〒101-8430 東京都千代田区一ツ橋2-1-2 TEL：03-4212-2664
Mail：kk-erato-jimu@nii.ac.jp ホームページ：http://bigdata.nii.ac.jp/
facebook：https://www.facebook.com/kk.erato