December 2017

7vol.

JST ERATO

Kawarabayashi Large Graph ProjectNEWSLETTER

研究総括よりERATO 河原林巨大グラフプロジェクト 2012－2017━ 民主党、SMAP はなくなり、AKB、EXILE はまだまだ健在 ━研究総括
本 ERATOが正式に始まったのは 2012 年 10 月1日。早いもので、すでに 5 年が経ち、今年度が最終年度になった（重点期間があと1 年あるため、来年度も規模縮小ながら継続予定である）。5 年前は、民主党政権（当時の文科大臣は田中真紀子氏）であった。その後の 5 年間でIT分野を含め、時代は大きく変わった。政治の世界では“民主党”は現在存在しない。芸能の世界では SMAP は解散してしまった。IT 分野では「ユビキタス」という言葉は現在“終わった”バズワードとされ、「IoT」という名に変わった。人工知能ブームの再来は本 ERATO 発足時にはまだ始まっておらず、2013 年の終わり頃から始まった。当然、深層学習の本格的なブレークも本 ERATO 発足後である。データサイエンスも同様である。
5 年前、もうそろそろ終焉を迎えるのではと思われていたものの、今でも健在なものはたくさん存在する。IT 分野において、ビッグデータは一時のバズワードだと思われていたが、まだまだ使われている。思えばプロジェクト発足時、プロジェクト名を「ビッググラフ」か「巨大グラフ」とするかで悩んだ。前者だとビッグデータというバズワードが消えた瞬間に、本 ERATOも単なる一時のブームに終わるように思われるので、当時の JSTプロジェクト担当の南さんと“巨大”の方が良さそうですね、ということで決めたのを鮮明に覚えている。ただ、今となってみればビッグデータブームがここまで続いたのであれば、ビッググラフでも良かったかもしれない。芸能界では、AKBとEXILE は、5 年前からブームの終焉を予期する人が大勢いたものの、現在も健在である（特に前者は、欅坂、乃木坂などができ、勢いが増しているように思う）。
果たして、この 5 年間で消え去ったものと、今でも健在であるものの違いはなんであろうか？AKB、EXILEを例に取ると、彼らは手を変え、品を変えサプライズを起こし続けている。しかしながら、SMAP や民主党は、“勤続疲労”ともいうべき症状をきたし、世の中にインパクトを与えるサプライズを起こせなくなったからではないだろうか？5 年という期間は、今振り返ると短かったように思えるが、プロジェクトが始まった当初はとても長いように思えた。当初は「自分もいろいろなサプライズを起こそう！」という情熱を持っていた。しかしながら、IT 系の時代の流れは芸能界と同様に非常に早いため、時代の先端を切り開きかつ研究コミュニティにサプライズを与えるためには、相当量のエネルギーが必要である。
自分は、ERATO の総括としてこの役目を果たそうと思ってきたが（達成できたかどうかは疑問であるが）、この情熱とエネルギーを5 年以上維持するのは正直難しい。勤続疲労なしでプロジェクトに取り組むという意
味では、ERATO の 5 年間はちょうど良い長さであったように思う。
本 ERATO のサイクルは今年度で終わる。プロジェクトの評価はもうすぐ下される（すでに予備評価は下されている）。しかしながら、本当の評
価は今ではなく、5 年後、10 年後に下されるべきであろう。本 ERATO の一番のレガシーは、プロジェクトから巣立った「人」である。本 ERATO に2017.8.3～4

ERATO 感謝祭 SeasonⅣ（学術総合センター）

河原林 健一Ken-ichi Kawarabayashi

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

参加した研究者は、グループリーダ、サブリーダを含め、今後に全盛期を迎える若手研究者ばかりである。今後の IT 分野に彼らがどれくらい貢献したか？で評価は下されるべきであると思う。
「人を育てた」と言い張るプロジェクトは、典型的な失敗プロジェクトだと言われている。しかし、このプロジェクトがこのような見方を変えることができればと思う。実際、この 5 年間に ERATO に関わった多数の若手研究者が良いポジションを得ているのを見ると、“so far so good”のように見える。5 年後、10 年後の彼らを見るのが本当に楽しみである。
最後になったが、本 ERATO で行ったことの大部分は、積極的に関わってくれた若手研究者と、それを陰で支えてくれた（HQを含めた）事務局のお陰だと思う。改めて御礼を申し上げたい。このような環境の下で研究総括ができたのは本当にラッキーであった。

2017.11.7

GL 集合写真（学術総合センター）

グループ代表者より
グラフ・ネットワークにおける理論と最適化グループ

垣村 尚徳

Naonori Kakimura

グループリーダ
慶應義塾大学 准教授
2008 年 3 月、東京大学大学

院情報理工学系研究科 博士
課 程 修 了。2017 年 4 月より
現 職。組 合せ最 適 化、特に離散構造に着目したアルゴリズム設計に興味を持つ。

5 年前は「ビッグデータ」という言葉が注目され始めた頃だった。そのような中、河原林 ERATOプロジェクトが立ち上がり、小林さんと一緒に、組合せ最適化やグラフ理論を情報科学の諸分野に拡げることを目指してグループを作ることになった。
発足当初は通信ネットワークやネット広告などの勉強会を手探りで始めた。その甲斐あってか、これらの分野に関連して、最大流最小カット定理の拡張（小林 - 大槻、INFOCOM 2014）や整数格子上の劣モジュラ関数のアルゴリズム（相馬 - 稲葉 垣村 - 河原林、ICML 2014）など、各人が持つ理論的な知見を活かした成果が生まれた。その後も福永さんを始めとする研究員が中心となり、人工知能や機械学習の国際会議で多くの成小林 佑輔

果を発表することができた。個人的にも以前から興味があった数理科学の他分野への応用に挑戦でき、また多くの方々と共Yusuke Kobayashi

同研究する機会に恵まれ、充実した 5 年間であった。研究員・グループサブリーダ
筑波大学 准教授
2010 年 3 月、東 京 大 学 大 学感謝申し上げたい。

院情報理工学系研究科 博士
課 程 修 了。2010 年 4 月から2015 年 3 月 ま で 同 助 教、2015 年 4月より現職。組合せ最適化、グラフアルゴリズム、離散構造、特に効率的に解ける問題の限界に興味を持つ。

RAを始め本グループに関わってくださった皆様にこの場を借りて
本 ERATO のように理論研究者が組織立って応用分野に取り組むことは、最近では珍しくないが当時は先駆的なものだったと思う。修了した RA の多くは企業や大学で研究を続けており、ERATO 感謝祭や学会で顔を合わせることも多い。本グループに関わった皆さんが理論的な素養を活かして様々な分野で活躍していくことを願っている。

（記：垣村）

グラフマイニング &WEB&AIグループ
2013 年 2 月より本 ERATOプロジェクトに参画し、2016 年 3 月までの約 3 年間、特任助教として NII に勤務した。河原林研究総括に初めて会ったのは2012 年の年末。当時の私は学振 PD の最後の年で、次の進路をどうするか悩んでいた。学振 PDを継続し当時の環境のまま続けるか、環境を変えるか。そんな時に本プロジェクトに誘っていただき環境を変えることを選択したが、結果的にはその時点でのベストな選択ができたと思っている。
本 ERATOプロジェクトで、私は参画当初からグループのサブリーダとしてグループの陣営を整えることに力を注いだ。本 ERATO では企業とのコラボレーションをはじめとしてたくさんのプロジェクトにかかわることができた。うまくいったもの

林 浩平

もうまくいかなかったものもあるが、結果として私を含め、本グループの多くの論文が NIPS、ICML、KDD、WSDM、IJCAI、AAAIといった、いわゆる人工知能

Kohei Hayashi

系のトップ国際会議に採択されるという成果を挙げることができた。またプロジェ

グループサブリーダ / 産業技術総合研究所 研究員
2012 年 3 月、奈良先端科学技術大学院大学情報科学研究科博士課程修了。 2016 年 4 月より現職。機械学習全般、特にベクトでの活動を通じて自分が扱えるトピックの「幅」を大きく広げることができ、今イズ確率モデルに興味を持つ。の自分の大きな財産となっている。
河原林研究総括はいうに及ばず、ERATO 在籍中から現在に至るまで多くの方々にお世話になった。特に、企業との共同研究に際したくさんのアドバイスをいただいた今井研究総括補佐、グループの業績報告の際に大変お世話になった安藤研究推進主任、煩雑な事務手続きをいつも笑顔で引き受けていただいた事務局の皆様、そして WEB&AIグループの皆様に深く感謝申し上げたい。

複雑ネットワーク・地図グラフグループ
本グループの基本的な路線は「実ネットワークに対する高速・高精度なアルゴリズムを数理的・ネットワーク科学的考察に基づき開発すること」であった。プロジェクトの初期は、多くの重要な問題に対して初等的な手法しか存在せず、幾らでも研究すべきことがあり、実際に数多くの良い論文を出すことが出来た。このような実りある研究が出来たのも、偏に本グループの優秀なメンバーと、その体制の構築に尽力された河原林研究総括のおかげである。この場を借りて感謝申し上げたい。
個人的な思い出としては、毎週のグループセミナーの後に、メンバーで NII 近くの中華料理店「川府」で晩ご飯を食べたのが忘れられない。ほぼ全てのメニューを食べ尽くしたと思う。この夕食会のおかげでメンバー同士の距離が近くなり、研究も円滑に進むようになった。また合宿中に結婚の報告をしたり（させられたり）、家族を連れて合宿に参加したのも良い思い出である。
プロジェクトも 5 年が経過し、最近は心から解きたいと思う問題も減ってきたので、グループの使命も終わりつつあると感じる。勝負の世界の一流の人が皆言うことであるが、勝ち続けるには時流に合わせて自分も変化し続けなければならない。深層学習に代表されるように、研究の世界も 5 年が経つと大きくトレンドが変化しているので、自分自身のこれまでの強みを活かしつつ、新しい分野に飛び込んでいく勇気が必要かなと思う。
本プロジェクトはもうすぐ終わりを迎えるが、そこで得た経験や繋がりは残る。自分自身も含め、本グループを巣立ったメンバーが、これからも各々の分野で良い仕事をすることが、プロジェクトを支えて下さった方々に対する恩返しになるのだと思う。

吉田 悠一Yuichi Yoshida

グループリーダ / 国立情報学研究所 准教授
2012 年 3 月、京都大学大学院情報学研究科 博士課程修了。
2012 年 4 月、国立情報学研究所 特任助教。2015 年 4 月より現職。理論的及び実用的に高速なアルゴリズムに興味を持つ。

ネットワーク・アルゴリズムグループ
私が担当するNARC は、東北大学の情報科学研究科のネットワーク・アルゴリズムセンターを対応させて、応用研究も目論んでスタートした。ところが、ビッグデータ利活用プロジェ
クトや渡辺新学術領域研究、さらには ImPACT のデータ解析も同時進行で、各先生にこれ以上協力を頼めない状況である。そこで、ミッションを国際化に変えて、「計算幾何中心に若手の優秀な外国人研究者を集めて、ビジターをたくさん呼ぶ」ということにした。管理能力の高い塩浦さんを実質のグループリーダ、陽気な Matiasを人集め担当にして、6 人の研究者を雇い、世界の 70 以上の研究機関の 100 人以上の研究者との共同研究を行い、世界中の俊英と知り合えて楽しかったし、役目は努めたと思っている。ただ、ポリコムセミナーだと気合いが入りにくく、仙台―東京の交流はもっとうまくできたかなという反省はある。

徳山 豪

Takeshi Tokuyama

グループリーダ
東北大学 教授
1985 年 3 月、東京大学理学系研究科数学専攻 博士課程修了。1999 年 9 月から東北大学大学院情報科学研究科 教 授。理 論 計 算 機 科 学やデータ科学から数学全般にかけて、アルゴリズムに関する理論に従事する。

塩浦 昭義

Akiyoshi Shioura

さて、河原林さんは若い時からカリスマ性があった。管理統括能力は不明だったが、苦にはしないとは思っていて、「新たな ERATO 統括の候補にだれがいいでしょうか」というJST の相談に、真っ先に顔が浮かんだのが 6 年前である。KKカリスマは研究カルチャーを変革し、本当に優れたプロジェクトを実現したと思っている。成果はもちろん、多数の若手人材を輩出した。彼らが次世代のカリスマになってくれることを待望する。
（記：徳山）

グループサブリーダ
東京工業大学 准教授
1997 年 3 月、東京工業大学
大学院情報理工学研究科
博 士 課 程 中 退。2015 年 4月より現職。離散最適化の理論とアルゴリズムの研究に従事する。

5 年 間の振り返り

2013.3.12 キックオフミーティング（学術総合センター）

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

2017.9.8 中間報告会 2017（JST 東京本部別館）

プロジェク ト の 運 営 を 支 え て早いもので、本プロジェクト発足から5 年が経ちました。当初はこもあり、本当に「やりがいのある」お仕事でした。総括はもちろんののような大変なプロジェクトとは夢にも思わず、無我夢中で裏方仕事こと、総括を支えるグループリーダ、サブリーダの皆様、その他たくさをこなし、あっという間に時が過ぎてしまったというのが正直なところんの皆様のご協力があってこそやり遂げることが出来たとしみじみ感です。多い時で50 名の研究員とリサーチアシスタント、研究協力者じています。
今後、日本の情報基礎分野がますます盛り上がり、本プロジェクトを含めると70 名近くの皆様と関わりました。プロジェクトに関わってに関わった研究者の皆様が世界の中で光り輝く活躍を続けられるよ

くださった方々のご活躍は嬉しい限りです。
日々の補佐業務に加えて、在日英国大使館、在日フランス大使館

う心よりお祈り申し上げます。また、プロジェクトの発足当初より支えとの共催行事、研究紹介映像制作、研究成果報告会、予備評価報てくださったJSTプロジェクト担当の南様、吉川様、佐藤様、NII の告書作成、果ては主催行事として感謝祭、WINTER FESTAを毎皆様、各種業者の皆様、そして今井研究総括補佐、安藤研究推進

年開催するようになり、どこまで広がるのだと嬉しくもあり、時に苦しく主任を始めとするHQ の皆様に感謝申し上げます。

（記：津島）

参画研究員の延べ人数（2017 年 12月1日現在）
研究員
ＲＡ
合計

2012 年度
81523

2013 年度
1831492014 年度
2127482015 年度
2422462016 年度
2218402017 年度
1917352017 年度に行われたJST の予備評価においては、全体構想、研究成果、科学技術への貢献、社会・経済への貢献、若手研究者支援、アウトリーチ活動に関して高い評価をいただきました。
（総合評価 A+）

主要な研究成果2017 年 9月～2018 年 2月 国際会議発表論文

論文名Polylogarithmic approximation for minimum
planarization (almost)
Theoretically and Empirically High Quality Estimation ofCloseness Centrality
Eﬃcient Sublinear-Regret Algorithms for Online Sparse
Linear Regression with Limited Observation
Fitting Low-Rank Tensors in Constant Time著 者
Ken-ichi Kawarabayashi, Anastasios Sidiropoulos

会議名
FOCS2017, Berkeley, CA, USA,
October 15-17
Shogo Murai
ICDM2017, New Orleans, LA, USA,
November 18-21
Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro NIPS2017, Long Beach, CA, USA,Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
December 4-9
Kohei Hayashi, Yuichi Yoshida
NIPS2017, Long Beach, CA, USA,December 4-9
Ken-ichi Kawarabayashi, Benjamin Rossman
SODA2018, New Orleans, LA, USA,
January 7-10
Nobutaka Shimizu
SODA2018, New Orleans, LA, USA,
January 7-10
Ryusuke Takahama, Yukino Baba, Nobuyuki Shimizu, AAAI2018, New Orleans, LA, USA,
Sumio Fujita, Hisashi Kashima
February 2-7
Satoshi Hara, Masakazu Ishihata
AAAI2018, New Orleans, LA, USA,February 2-7
Atsushi Miyauchi, Tomohiro Sonobe,
AAAI2018, New Orleans, LA, USA,
Noriyoshi Sukegawa
February 2-7
Shota Saito, Hideyuki Suzuki, Danilo Mandic
AAAI2018, New Orleans, LA, USA,
February 2-7
Danushka Bollegala, Yuichi Yoshida,
AAAI2018, New Orleans, LA, USA,Ken-ichi Kawarabayashi
February 2-7

A Polynomial Excluded-Minor Approximation ofTreedepth
The Diameter of Dense Random Regular Graphs
AdaFlock: Adaptive Feature Discovery for
Human-in-the-loop Predictive ModelingApproximate and Exact Enumeration of Rule Models
Exact Clustering via Integer Programming and Maximum
Satisﬁability
Hypergraph p-Laplacian: A Diﬀerential Geometry View
Using k-way Co-occurrences for Learning WordEmbeddings

お知らせ 当プロジェクトより以下の方が転出されました。
原聡

氏 名特任助教

Jean-François Baffier 特任研究員
福永 拓郎
照山 順一
阿部 真人

特任准教授
特任研究員
特任研究員

転出時期

2017 年 9 月
2017 年 9 月
2017 年 10 月
2017 年 10 月
2017 年 12 月

転 出 先
大阪大学 産業科学研究所 助教
日本学術振興会 博士研究員（活動拠点：東京工業大学）
科学技術振興機構 さきがけ研究者 / 理化学研究所 革新知能統合研究センター 研究員
関西学院大学大学院 理工学研究科 博士研究員
理化学研究所 革新知能統合研究センター 特別研究員

イベントの様子2017.8.3～4

ERATO 感謝祭 SeasonⅣ（学術総合センター）2017.9.8

中間報告会（JST 東京本部別館）

発行：大学共同利用機関法人 情報・システム研究機構 国立情報学研究所 ビッグデータ数理国際研究センター〒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