March 2017

5vol.

JST ERATO

Kawarabayashi Large Graph ProjectNEWSLETTER

感謝祭 & WINTER FESTA

研究総括より研究総括

河原林 健一Ken-ichi Kawarabayashi

本プロジェクトは「公式」行事として、感謝祭（８月）とWINTERFESTA（12 月）を毎年開催している。それぞれの趣旨についてもう一度ここで述べたいと思う。
感謝祭では、当該年度に発表される「優れた」研究論文を一堂に集めて、当該研究者に発表してもらっている。感謝祭を開始した当初は、本プロジェクトの研究者のみに講演をしてもらっていたが、現在は、本プロジェクトの研究者を含め、日本中の研究者に講演いただいている。
ここでキーワード「優れた」について、少し補足したい。
「優れた」研究成果とは、本プロジェクトが情報系であるので、所謂各分野の「トップ会議」に採用された論文を中心に選んでいる。ここで重要なのは、研究者の「名前」では全く選ばず、論文だけで判断している点である。その結果、講演者はほぼ全員 20 代、30代となっている（トップ会議の発表者の平均年齢と変わらなくなっている）。
感謝祭の様に、15～20 本のトップ会議だけの発表を行う研究集会は、日本ではおそらく皆無であろう（MIRU、IBIS などの国内情報系の主要会議等でも、トップ論文発表のセッションは存在するが、、）。多くの若手研究者が、感謝祭の発表から刺激を受け、トップ会議に通すことができるような仕事を多数行ってほしいと思う（そして翌年の感謝祭で発表してほしい！）

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

WINTER FESTA は、情報系の「国内学会」の枠を超えた「レベルの高い」研究集会を意図している。情報系は、決して一つとは、研究の質が保証されることである（他分野の価値基準がわの学会で閉じているわけではない。本プロジェクトをみても、情報からない以上、交流相手の価値観を信じる必要があるため）。こ

処理学会、電気通信学会、人工知能学会、言語処理学会、れらの点を考慮して、現在の日本の情報系の主要大型プロジェ

OR 学会、応用数理学会、物理学会、数学会、応用物理学会

クトを会するイベントを企画することにした。

等を主戦場としている研究者がいる。これらの学会は、それぞれ両イベントとも、研究コミュニティに受け入れられてきたと思う。

独立に活動しており、会員同士の交流は多いとは言えない。しか両方とも、講演依頼、または参加依頼を断られることは全くないしながら、明らかに研究対象に重複があるので、研究交流が必（むしろ「売り込み」すらある）。また両イベントの参 加 者 数も要であると長年感じてきた。またこのような研究交流で重要なこ200～300 人であり、回数を重ねるごとに上昇傾向にある。主催者（？）として、研究コミュニティへのアピールは十分に行われたと自負している。
当然ながら課題もある。WINTER FESTA は、大型プロジェクト関係者のみが発表可能になっているので、部外者にとっては参加しにくい研究集会なのかもしれない。感謝祭は、論文発表分野でややバイアスがあるのかもしれない。そして最も大きな課題
は、本プロジェクト終了後に両イベントを継続できるかである。

2017 年度、そしておそらく2018 年度までは両イベントとも、本プロジェクトが主催できると思うが、その後はどうするかはまだ決まっていない。とはいえ、両イベントとも、誰かに引き継いでもらいSeason 10, Episode 10を目指してほしいと思う。
2016.12.22～23 情報系 WINTER FESTA Episode2（学術総合センター）

研究紹介

安定な状態を計算する
アルゴリズム雑誌や新聞、テレビ CM などの広告枠を売りたい人と、広告枠を買いたい客が何人かいるとします。売る側は、それぞれの広告枠を誰にいくらで売るかを決めます。
売る側は当然収益を大きくするように割当と価格を決めたいわけですが、問題は客がそれぞれ広告枠に対する希望をもっているため何も考えない売り方では客が不満をもつということです。商品に対して自分が感じる価値以上の金額を出す人はおそらくいないでしょう。また、他の人に割当てられた広告枠がどうしても欲しい人は妨害行動に出るかもしれません。客が不満をもたない中で収益を大きくするには、どのような割当と価格付けをすれば良いでしょうか？
私の研究では、人々が自分の利益を最大化するように行動する状況で、誰も不満をもたないような「安定した」状態を制約にもつ最適化問題を扱っています。安定した状態を考慮した最適化は、今後何が起きるかの予測も可能にするため重要です。
しかし、その解の計算を単純に行う（前述の例では、全ての割当と価格付けを試す）と膨大な計算時間がかかってしまいます。私は、このような問題に対して効率良く解を計算することを目指しています。特に前 述 の 問 題でグラフ・ネットワークにおける理論と最適化グループ

澄田 範奈
Hanna Sumita

国立情報学研究所 特任研究員
2015 年 3 月、東京大学大学院情報理工学系研究科博士課程修了。2015 年 4 月より現職。安定性に着目した組合せ最適化問題

は、簡 単に解を計算することが理 論上難しいのですが、近似的に良い解を計算する高速アルゴリズムを提案しています。の研究に従事｡

機械学習モデルを人間にわかりやすく

私は機械学習モデルがデータから獲得した法則性を人間にわかりやすいように解釈する方法について研究しています。近年の機械学習技術の発展は目覚ましく、画像認識や言語翻訳など様々な問題において高い性能が得られるようになりました。この高い性能の背後には、機械学習モデルがデータから暗黙的に獲得した何らかの法則性が潜んでいます。このような暗黙的な法則性を人間が理解することができれば、より高度なデータ分析や意思決定へと応用できます。例えば「モーターから異音がするときは故障の可能性が高い」という法則性が得られれば、故障に先んじて保守点検をすることができます。
機械学習モデルからこのような法則性を明示的に取り出すことは必ずしも簡単なことではありません。現在、機械学習でよく使われている手法は深層ニューラルネッ
トやランダムフォレストなどの複雑なモデルです。これらのモデルの中身はブラックボックスになっていて、モデルがデータからどのような法則性を学習したのか人間には理解できません。私は特にランダムフォレストに着目して、そこから人間にわかりやすい簡便な法則性を抽出する方法の研究に取り組んでいます。

グラフマイニング&WEB&AIグループ

原聡

Satoshi Hara

国立情報学研究所 特任助教
2013 年 3 月、大阪大学大学院工学研究科博士後期課程修了。
同 年 4 月から 2016 年 3 月まで IBM 東 京 基 礎 研 究 所 研 究 員。
2016 年 4 月より現 職。特 徴 選 択など、機 械 学 習 技 術を使ったデータからの知識発見に興味を持つ。

人口の増減というと、都道府県・市区町村といった行政区分を単位として語られることが多いと思います。しかし、移動や出生・死亡といった人口変化をもたらすイベントは、行政区分の境界線に規定されるとは限りません。
総務省が提供する『地域メッシュ統計』は、日本全体を約 500ｍ四方のセルで区切りその内部での居住者数と世帯数を記録しています。我々は、このデータを用いて、図のような居住クラスターを抽出し、その内部での人口変化に注目しました。こ

居住クラスターの空間的特徴と人口変動との関係のような自然発生的に形成されたクラスターは、個人の居住地選択やその地域の社会経済的要因など様々な情報が集約された帰結であるとみなせ、うまく特徴を抽出できれば人口変動の予測に活かせる可能性があります。
統計的な手法を用いたところ、幾つかの空間的特徴量（たとえば、クラスターの形状の複雑さを定量化したもの）が、クラスター内人口密度や性比といった基本的な情報に匹敵するくらい人口増減と関係することがわかりました。今後は、他の国や地域についても分析して知見の頑健性を検 証するとともに、クラスターの成長・縮 小 過 程 についても分析していきたいと考えています。

複雑ネットワーク・地図グラフグループ

関口 卓也

Takuya Sekiguchi国立情報学研究所 特任研究員
2012 年 3 月、東京工業大学大学院社会理工学研究科博士課程修了。日本学術振興会特別研究員を経て、2016 年 4 月より現職。進
化ゲーム理論、集合的意思決定、空間データ分析に関心を持つ。

私はアルゴリズム、グラフ理論、および計算幾何学に興味を持って研究しています。本プロジェクトでは、ユークリッド空間上の物体をデジタル化する際に、ユークリッド幾何のような性質を満たすようにするにはどうしたらよいか、という課題に取り組んでいます。現在、アナログなデータの多くはデジタル化されるようになりました。たとえば、画像は数値データを縦横に並べた行列で表現され、ＰＣなどの画面にはピクセルの集まりとして表示されます。デジタル空間での幾何計算のための精緻な体系をつくるには、ユークリッド幾何における公理系と同様の公理系を確立することが望まれます。それによって、デジタル空間での正確な計算が可能になると考えています。この問題に取り組む上での最初のステップは、まっすぐな線分について調べることです。過去のいくつかの研究において、デジタル線分の精緻な体系を定める5 つの公理が既に確立されています。これら5 つの公理に加えて、デジタル線分は普通の意味での線分に似ていることが望まれます。それが出来ると、デジタル線分の定義を自然な形で拡張することによって、ユークリッド幾何における凸な物体や星形の物体などの他の幾何図形を、デジタル空間においても定義できるようになります。
デジタル線分の一つの応用先は、医療画像における腫瘍や心臓などの画像の切り出しです。腫瘍や心臓は１つの星形の物体もしくは 2 つの星形の物体の併合として近似的に表現できます。そのため、デジタル線分の研究成果が応用できるわけです。いくつかの医療画像は立体画像として、ボクセル (voxel）によって表現できますが、3 次元以上の次元のデジタル空間においてどのようにデジタル線分を定義すべきか、ほとんど分かっていません。
それゆえに、私の研究では、高次元におけるデジタル線分の精緻な体系の満たすべき性質について理解すること、および通常の線分とデジタル線分の見かけがどの程度異なるのか3 次元デジタル空間における評価すること、に焦点を当てています。
デジタル線分の具体例

整合性の取れた
デジタル線分の研究

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

Man Kwun Chiu
マン クァン チュウ

国立情報学研究所 特任研究員
2014 年 1 月に香港科技大学においてコンピュータ理工学の博士号を取得。その後、同大学のポスドクとして勤務。 2015 年 7月より現職。現在の研究テーマは整合性の取れたデジタル線分、およびその他の計算幾何学の諸問題。

リサーチアシスタントたちは今… 22012 年 10月のプロジェクト発 足 以 来、現 在まで 述 べ 68 人（現 役 18 名、OB・OG 50 名）もの 学 生 の 皆 様にResearch AssistantまたはProject Assistantとして参加していただいています。OB・OG の中から4 人の方にコメントをいただきました。

大槻 兼資

川本 達郎

現在：株式会社 NTT データ数理システム 研究員
旧：グラフ・ネットワークにおける理論と最適化グループ RA（RA 期間：2013 年 1 月～ 2014 年 8 月）

現在：産業技術総合研究所 人工知能研究センター 研究員
旧：複雑ネットワーク・地図グラフグループ RA（RA 期間：2012 年 11 月～ 2014 年 3 月）

私は現在、主に数理最適化に関わる実務“投票クラスタリング”という、大衆の主観を行っています。具体的には、積み荷安定性（感想・感覚）をグラフに変換し、それをクラなどの制約を満たしながら荷物を上手にトラッスタリングすることで集約するシステムを作クに詰め込んでいく“積み付け問題”や、荷物の集積所から何台り、研究しています。
「人間にはできるけど、計算機には難しい」

かのトラックを使って各顧客に荷物を配送するときにどのトラックがどという作業はたくさんあります。一方、人間が行う場合「作業量の顧客をどの順番で回ればよいかを求める“配送計画問題”などは限られる・動作が決定論的ではない」という問題もあります。に取り組んでいます。こうした実務では、ほとんどのケースで高速に両者はトレードオフであり、人間と計算機の作業の上手いバラン動作するアルゴリズムを考案するといった、数理的感覚に立脚したスをとるというのが、投票クラスタリングの考え方です。このトレー技能が大きな改善をもたらすことが多々あり、河原林巨大グラフプドオフは、グラフのスパースネスとして現れます。スパースグラフ

ロジェクトにおいて大規模な道路ネットワーク上で実際上高速に動の構造検出性能は、近年主に統計物理と理論計算機科学で作するアルゴリズムを開発・実装した経験が大いに活きています。

研究が進んでおり、これが核となっています。河原林 ERATO は、また最近は、機械学習系のプロダクト開発や研究活動にも関わ定期ミーティングや関係者の方々との議論を通じて、私の視野をり始めました。こうした活動においてはプロジェクトの関係者と交流物理以外へと大きく広げてくれました。今後、背後の理論研究する機会もあり、大変刺激的な日々を送っています。今後、プロとともに、投票クラスタリングが様々な場所でインフラとなるようにジェクトでの経験や、プロジェクトを通して得た人脈を活かして、有発展させていきたいです。

意義なプロダクトの開発や研究活動を行いたいと考えております。

平原 秀一

現在：東京大学 大学院情報理工学系研究科
博士課程 1 年（日本学術振興会特別研究員）
旧：グラフ・ネットワークにおける理論と最適化グループ RA（RA 期間：2014 年 6 月～ 2016 年 2 月）

福田 俊

現在：大日本印刷株式会社
旧：ネットワーク・アルゴリズムグループ RA（RA 期間：2013 年 4 月～2015 年 2 月）

私は現在、大日本印刷株式会社でビッグ河原林 ERATO プロジェクトには修士課程データを活用した新たなマーケティングの取りの 2 年間 RAとして在籍していました。現在組みを行っています。例えば、私達が行っては東京大学の博士課程に進学し、日本学術振興会特別研究員いる取り組みの一つに、生活者の価値観に着目した「生活者（DC1）として計算量理論の研究をしています。最近、アメリカのDNA®・商品 DNA」があります。これは生活者の価値観を独自ラトガース大学に一ヶ月半、イギリスのオックスフォード大学に一ヶの手法で判別するもので、購買行動等とかけ合わせて、生活者を月間訪問する機会を得て、現地の教授と共同研究をしていましより深く理解することを可能にし、得意先企業のマーケティング活た。ERATO プロジェクトに参加することによって、近い分野の研動にご活用いただいています。大日本印刷は、印刷以外にも幅究者と意見交換することができたり、知的好奇心をそそるような発広い分野で事業を展開しており、このような企業のマーケティング表を聞く機会を得ることができました。また、感謝祭で 2 度も自分支援にも取り組んでいます。の研究成果を発表させていただく機会を得ました。いずれの機会購買行動等のビッグデータを分析する際は、ロジックの組み方ででも、一流の研究者からフィードバックをいただくことができました。

分析にかかる時間が大きく変わります。それらを扱う上で、河原林

このプロジェクトの重要な点は、世界を舞台に活躍している国内巨大グラフプロジェクトを通じて学んだ数理最適化の考え方が役にの一流の研究者が一堂に会する場を提供していることです。私も立っており、今後も、プロジェクト参加の経験を日々の仕事で活か彼らのように世界を舞台に活躍し、人類に少しでも貢献できる研していきたいと考えています。

究をすることを目標に精進したいと思っています。

主要な研究成果

2016 年 8月～2017 年 2月 国際会議発表論文

論文名Dynamic Inﬂuence Analysis in Evolving Networks

著 者
Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida,Ken-ichi Kawarabayashi

会議名VLDB2016, New Delhi, India,Sep 5-9

Fully Dynamic Betweenness Centrality Maintenance on Takanori Hayashi, Takuya Akiba, Yuichi Yoshida
Massive Networks

VLDB2016, New Delhi, India,
Sep 5-9

The Constant Inapproximability of the Parameterized Yijia Chen, Bingkai Lin
Dominating Set Problem

FOCS2016, New Brunswick, NJ, USA,Oct 9-11

Te sti n g A s s i g n m e nt s to C o n st ra i nt S ati sfa c ti o n
Problems

Hubie Chen, Matt Valeriote, Yuichi Yoshida

FOCS2016, New Brunswick, NJ, USA,Oct 9-11

Exponential Lower Bounds for Monotone Span Programs

Robert Robere, Toniann Pitassi, Benjamin Rossman, FOCS2016, New Brunswick, NJ, USA,Stephen A. CookOct 9-11

How to determine if a random graph with a ﬁxed Felix Joos, Guillem Perarnau, Dieter Rautenbach, FOCS2016, New Brunswick, NJ, USA,degree sequence has a giant component
Bruce ReedOct 9-11
Minimizing Quadratic Functions in Constant TimeKohei Hayashi, Yuichi Yoshida

NIPS2016, Barcelona, Spain,Dec 5-10

Budgeted stream-based active learning via adaptive Kaito Fujii, Hisashi Kashima
sub modular maximization

NIPS2016, Barcelona, Spain,
Dec 5-10

主要受賞

2016 年 8月～2017 年 2月

受賞年月

受賞者

2016 年 8 月
2016 年 9 月
2016 年 12 月

江崎 貴裕

Best Poster Award

受賞名

Asia-Pacific Econophysics Conference 2016

主催団体名

塩浦 昭義

第 6 回日本オペレーションズ・リサーチ学会 論文賞

日本オペレーションズ・リサーチ学会

河瀬 康志

Best Paper Awards

ISAAC2016

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

江崎 貴裕

名特任研究員Bruce Alan Reed 特任研究員
小関 健太

特任助教

転出時期

2016 年 12 月
2017 年 1 月
2017 年 2 月

転出先

国立研究開発法人 科学技術振興機構 さきがけ研究者

CNRS（Centre National de la Recherche Scientifique, France) 研究員
横浜国立大学 環境情報研究院 社会環境と情報部門

特任教員（准教授）

イベントの様子2016.8.9～10 ERATO 感謝祭 SeasonⅢ（学術総合センター）

2016.9.7～8 中間報告会（ラフォーレ倶楽部 伊東温泉 湯の庭）

2016.12.22～23 情報系 WINTER FESTA Episode2（学術総合センター）

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