August 2017

6vol.

JST ERATO

Kawarabayashi Large Graph Project

NEWSLETTER

研究総括より

Journey と glee、そして Szemeredi と数学研究総括

河原林 健一

つい先日、Journey の特集番組があり、現在の「再ブーム」についての解説もあった。Journey は、スティーブ・ペリー（現在は脱退している）のハイトーンボイスが耳に残る80 年代を代表するロックバンドである。
1981 年に発売したアルバム「エスケイプ」は 1000 万枚以上ものセール「Don'tスを記録し、全米チャート1 位を獲得した。このアルバムには、Stop Believin'」「Open Arms」といった彼らの代表曲が収録されている。
そして 1983 年発売のアルバム「フロンティアーズ」も600 万枚以上のセールスを記録し全米チャート9 週連続 2 位を獲得している（ちなみに同時期に発売されたマイケル・ジャクソンの「スリラー」は、全米チャート37週連続 1 位獲得。現在の世界記録である3000 万枚超のセールスを記録）。このアルバムには、今年の WBC（ワールドベースボールクラシック）の日本でのテーマ曲である「Separate Ways」も収録されている。
この Journeyが 10 年ほど前から再ブレイクしている。これは 2008 年にアメリカのＴＶ番組「glee」の影響が大きい。glee は、学園物の TVドラマであるのだか、ストーリー以上にパフォーマンスが注目を浴びた。実際
glee は、ミュージカル俳優やミュージシャンを配役に起用し、毎週何曲ものヒット曲のパフォーマンスを行った。そしてそのクオリティの高さは、エンターテインメントの世界で高く評価され、glee は世界ツアーを行うまでに至っている。そして「Don't Stop Believin'」は glee の代表曲で、若い世代が Journeyを聞くきっかけとなった。
数学界でも似たようなことが起こっている。Szemeredi の Regularity
Lemma は、ある整数論の結果を導くために、1975 年に Szemerediが証明したグラフ理論の道具である。Szemeredi の Lemma はグラフ理論の分野では非常に高く評価されていたが、2000 年くらいまでは、強力ではあるが、グラフ理論の一分野である「極値グラフ理論」の範疇のみに応用可能であると考えられていた。しかしながら2000 年以降、整数的組合せ論（Additive Combinatorics）における数多くのインパクトのある結」の理果、離散数学、統計学分野における「Graph Limit（Graphon）論発展、そして理論計算機科学分野の「Property Testing（性質検査）」の発展は、すべてSzemeredi の Regularity Lemmaから始まり、その背景にある「アイディア」と「精神」を引き継いでいる。そして Tao，Gowers，Alonなどの数学界の重鎮達は、Szemeredi の深遠な貢献を大絶賛してきた。
Szemeredi の Regularity Lemma は、発表当時、彼の先見性と深遠な貢献に数学界が追いつけなかったのだろう。また彼自体、非常に控えめな人格であり、講演も決してうまいわけではない（大半の聴衆は、5 分とついていけない。また彼の書いた文字はほぼ解読不能）。しかし2000 年以降 Szemeredi の先見の明と深い洞察に気づいた数学界はSzemeredi に対して最高級の栄誉を送っている（彼が受賞した国際賞 の 数 々は、ほとんどが 2008 年 以 降 である）。そして 2012 年、Szemeredi は「アーベル賞（数学界のノーベル賞）」を受賞した。
以上の例のように、昔の仕事の中には先人の「英知」が詰まっていKen-ichi Kawarabayashi

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

る。また彼らの先見性は、その仕事をじかに体験しなければ理解できない。
ある程度キャリアを積んだ自分は、今後先人の仕事に敬意を払いつつ、先人の「英知」を再ブレイクさせたいと思う。
現在は、研究費などの関係から成果をすぐに求められることが多い。
また「Deep Learning」などの分野は数週間、数か月単位での研究サイクルが必要で、瞬く間にほとんどの過去の仕事は忘れられてしまう。私のように若くない研究者は、このような分野で生きることはできないと思うので、今後は今すぐブレイクしなくても、数十年後にブレイクするような研究に取り組みたいと思う（長生きしないと自分の仕事の行く末は見ることができないが）。
最後に、自分の研究を引用してくれた、また参考にしてくれた研究者にも感謝するべきであろう。Szemeredi は「自分の仕事が評価されたのは、多くの研究者が自分の研究を生かしてくれたからだ。その研究者たちに感謝したい」とアーベル賞の受賞時に述べている。

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

研究紹介

パラメータ化近似
不可能性に対する新しい証明手法の開発計算困難な問題を扱うための理論として、パラメータ化計算量理論と近似アルゴリズム理論は両者ともに重要な役割を果たしています。たとえば、頂点被覆問題という組合せ最適化問題は NP 困難と呼ばれるクラスに属しており、グラフの頂点数 n の多項式poly(n) に依存する計算時間で解くことは難しいと考えられています。しかし、サイズ k 以下の解が存在するかは 2 k poly(n) 時間で判定できますし、最小サイズの 2 倍以内の大きさの近似解を poly(n) 時間で求めることが可能です。パラメータ化近似計算は上の 2 つのアプローチを合わせたものです。たとえば支配集合問題は、頂点被覆問題とは異なり、どんな関数 f を用いてもサイズ k 以下の解の存在を f (k) poly(n) 時間で判定できません。
また、最小サイズの定数倍以内の解をpoly(n) 時間で求めることもできません。そこで 2つのアプローチを合わせ、2 k poly(n) 時間で最小サイズ k の 2 倍以下の支配集合を求められるか、という疑問が自然に湧いてきます。
私の研究では、計算量理論の妥当な仮定のもと、このような計算をするアルゴリズムが存在しないことを示しました（FOCS2016）。これは二部クリークのパラメータ化近似不可能性の証明手法（SODA2015）の枠組みを拡げることで得られています。最終的には、より多くの最適化 問 題 の パラ
メータ化近似不グラフ・ネットワークにおける理論と最適化グループ

Bingkai Lin
ビン カ イ リン

国立情報学研究所 特任研究員
2016 年 3 月、東京大学大学院情報理工学系研究科 博士課程修了。2016 年 4 月より現職。最適化問題のパラメータ化近似不可能可能性を証明するための体系的な手法の構築を目指して、研 究に取り組んでいます。

性の研究に従事。

高次元データにおける確率密度関数の幾何的な構造の推定

近年、ビッグデータと呼ばれる高次元構造を有するデータが得られることが多くなり、その解析手法の確立が急務となっています。その中でも私は、確率密度関数の幾何的な構造の推定に着目して研究を進めています。確率密度関数の推定の際、カーネル密度推定と呼ばれる方法がよく利用されますが、確率変数の次元の増加に伴ってその推定精度が悪くなることが知られており、この現象は統計学では「次元の呪い」と呼ばれます。
私の研究では、（条件付き）確率密度関数を、分位点関数を経由してモデリングすることで次元削減を行い、「次元の呪い」を緩和して推定精度を改善する方法を提案しています。また、確率密度関数の幾何的な構造の推定に関して、現在は特に最頻値に着目して研究を進めています。確率密度関数の極大値を与える確率変数の値のことを最頻値といい、統計学において推定対象となる一つの特性値です。
また、最頻値は、期待値では捉えられない情報をもっていることが知られています。
他にも、確率密度関数にまつわる我々が知りたい幾何的な構造は色々とあるため、提案方法を
利 用したその推定法のグラフマイニング&WEB&AIグループ

大田 浩史
Hirofumi Ohta

リサーチアシスタント / 東京大学大学院 修士課程
2016 年 4 月から、東京大学大学院経済学研究科 統計学専攻に在学。 2016 年 12 月よりRA として河原林巨大グラフプロジェクトに参加。高次元統計学およびノンパラメトリック推定の研究に従事。

研究の発展が 期 待されます。

人を含めた生物は、分子・細胞・個体・集団・生態系といったあらゆる階層において要素が互いに作用し合う広い意味での社会を築き、生命としての機能を発揮するシステムであると言えます。近年、そのような社会における要素同士の関係性をネットワークとして表現し、その構造を特徴づけることで生命システムを理解する手法が発展したため、生命科学においてネットワークという視点は重要性を増してきています。

生物の社会をネットワークの視点から理解する

私は実際に、アリの巣における個体間の関係性をネットワークとして解析し、行動の数理モデルを構築することで、アリだけでなく、人を含めた動物の社会に共通の構造を明らかにしています。もう一つの研究として取り組んでいるのは、個体や細胞、分子がどのように動くかという問題です。そもそも、ネットワークの要素が作用し合うためには、空間の中で要素同士が出会うことが必要です。
そこで、要素がどのように動き、他の要素と出会うかという問題にも取り組み、最適な遭遇率をもたらす動きのパターンを明らかにしています。
これらの研究を通して生命現象を理解し、私達の実生活や社会に役立つ法則を見つけたいと思っています。

アリのネットワーク

私は幾何学的な「もの」を扱うアルゴリズムの設計に興味をもって研究を行っています。とくに、点集合、直線の集合、およびそれらの間の距離のような幾何的な構成要素に関する問題に取り組んでいます。私の研究目的は、そのような問題を解くためのアルゴリズムを構築する上で有用な幾何的性質を見い出すことです。
本プロジェクトで扱う巨大グラフには、有用な幾何情報が大量に含まれています。
例として、巨大なアドホックネットワークを用いてメッセージを送る状況を考えます。互複雑ネットワーク・地図グラフグループ

阿部 真人
Masato S. Abe

国立情報学研究所 特任研究員
2015 年 3 月、東京大学大学院総合文化研究科 博士課程修了。
2015 年 4 月より現職。生物ネットワーク、複雑系に関心をもつ。

アルゴリズム構築に有用な幾何学的性質を探る

いに近いノード間での通信は容易で、メッセージを短い時間で直接送信可能です。
一方、遠いノードの間でメッセージを送信する際には、ノード同士でのメッセージの伝達を繰り返す必要がありますが、その回数をできる限り少なくすることが望まれます。
また、ネットワーク上の指定された場所に、非常に多くのノードと接続しているハブが配置されており、ハブの間では、高速に通信することが可能です。したがって、遠いノードの間でメッセージを短い時間で送信するためには、如何にしてハブを有効活用するか、ということを検討する必要があります。以上の問題では、ノードの位置情報、ノード間の距離、およびノードをつなぐネットワーク上の最短パスなどのような幾何構造が現れ、その解析が重要となります。私は問題に対する効率のよいアルゴリズムの構築に向けて、問題に現れる幾何構造の研究を進めています。
通信ネットワークのイメージ

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

Matias Korman
マ ティア ス コ ル マン

研究協力者 / 東北大学 助教
2009 年 9 月、東 北 大 学 大 学 院 情 報 科 学 研 究 科 博 士 課 程 修了。その後、4 年間ヨーロッパの大学での研究員を経て、2013年に東北大学に戻り、巨大グラフ内の最短路のアルゴリズムについて研究を続ける。リサーチアシスタントたちは今… 32012 年 10月のプロジェクト発 足 以 来、現 在まで 述 べ 73 人（現 役 16 名、OB・OG 57 名）もの 学 生 の 皆 様にResearch AssistantまたはProject Assistantとして参加していただいています。OB・OG の中から4 人の方にコメントをいただきました。

丸茂 直貴

林 孝紀

現在：NTT コミュニケーション科学基礎研究所 研究員
旧：グラフ・ネットワークにおける理論と最適化グループ RA（RA 期間：2014 年 6 月～2016 年 2 月）

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

私は現在 NTT 研究所で、数理最適化と私は現在、世界最大級の求人情報検索

その機械学習への応用について研究していサービスを扱うIndeedという会社で、ソフトます。具 体 的には、スパース最 適 化 問 題

ウェアエンジニアとして働いています。社内

等、機械学習で現れる様々な非凸制約付き連続最適化問題

では検索結果の品質向上に取り組むチームに所属し、それぞれを、凸緩和せずに解く手法について研究しています。機械学習の求人がどのような仕事内容に対する募集なのかを分類するシ分野の国際会議に論文が採択されることを目標として研究をしてステムの開発に携わっています。仕事内容の分類結果は、ユーいますが、河原林プロジェクトの毎週のセミナーや日々の議論でザの検索クエリに対する求人情報のマッチングなどに使用されて得た関連分野の幅広い知識・経験は、研究テーマを決める上おり、適切な分類を行うことは検索品質を高める上で重要です。

でも、研 究を遂 行 する上 でも直 接 役 立っています。また、日々更新される数千万件の求人情報を扱うため、データの性質ERATO 感謝祭の発表者として声をかけていただくなど、業務でに合わせて適切なアルゴリズムを選択して高速に処理を行う必本プロジェクト関係者と関わることも多く、ここでの人脈が今も活要があります。そのような課題に取り組むときに、河原林巨大グきています。一流の研究者と議論・交流ができるプロジェクトは、ラフプロジェクトに参加して、大規模ネットワークに対してデータ卒業後も研究に携わることになる学生にとって大変ありがたいの性質を利用した高速なアルゴリズムを設計・実装した経験が環境であったと感じます。今後もプロジェクトの OBというアドバ糧となっています。検索サービスは様々なデータ構造とアルゴリンテージを活かし、数理最適化・機械学習分野の研究やそのズムの上に成り立っているので、プロジェクトから学んだものを活応用に少しでも貢献したいと思っています。

かして優れたプロダクトを開発していきたいです。

高濱 隆輔

現在：株式会社リクルートライフスタイル
旧：グラフマイニング &WEB&AIグループ RA（RA 期間：2015 年 5 月～2017 年 2 月）

豊岡 祥

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

修士課程での 2 年間、河原林巨大グラフ

当社では、「数理科学とコンピュータ・サイプロジェクトに RAとして在籍していました。

エンスの融合」というテーマを掲げて数理最大学院を卒業後は株式会社リクルートライフ

適化やデータマイニングを活用した事業を中スタイルに就職し、データ解析技術を活かした事業の改善などの心に行っております。最近はやはり機械学習を応用した仕事が多業務を行っています。

いのですが、周囲には最新の研究に通じている社員が多く、非常河原林巨大グラフプロジェクトは理論寄りの研究者・学生のに刺激的です。そのような中にあって、河原林プロジェクトで毎週方が多く所属されている組織ですが、同時に企業との共同研究のセミナーや成果発表会で色々な分野の方の研究に触れたり、にも力を入れており、私自身もヤフー株式会社との共同研究と研究会で多くの先生・先輩方と議論した経験は今の自分の血肉いう形で勤務させていただきました。現職では研究とビジネスのとなっていると強く感じます。
「どのような意義のある研究なのか」

境界領域ともいえる業務に携わっていますが、RA での共同研究「よりよい研究になるためには何が必要か」といった観点は、ビジネの際にビジネス的な知見に基づくアドバイスを頂いた経験が活きていると感じています。今後は、大学院での研究、また RAを通じて多様な研究分野の研究者の方と関わったことで培われた学
術的な知識を活用し、それらをビジネスと融合していくことで社会に価値を生み出すことができる人間へ成長していきたいと思っています。

スのシーンで研究を活用する上でも非常に大切なことです。
最 近は新 人 研 修 の 一 環として、積 付け 問 題（rectanglepacking）という古典的な課題に取り組んでいます。先輩から「世界レベルの結果を」というアツい命令を頂いて、日々アルゴリズムの改良に取り組んでいます。加速度的な進展を見せる数理科学の分野の研究を社会に還元していくべく、幅広い分野にアンテナを張って勉強を続けていきたいと思っています。

主要な研究成果2017 年 3月～2017 年 8月 国際会議発表論文

論文名Portfolio Optimization for Inﬂuence Spread

著 者
Naoto Ohsaka, Yuichi Yoshida

会議名
WWW2017, Perth, Australia,
April 3-7

Exact Computation of Inﬂuence Spread by Binary
Decision Diagram

Takanori Maehara, Hirofumi Suzuki,
Masakazu Ishihata

WWW2017, Perth, Australia,April 3-7

Coarsening Massive Inﬂuence Networks for Scalable
Diﬀusion Analysis

Naoto Ohsaka, Tomohiro Sonobe, Sumio Fujita,
Ken-ichi Kawarabayashi

SIGMOD2017, Chicago, IL, USA,May 14-19

Landmark indexing for Evaluation of Label-Constrained Lucien Valstar, George Fletcher, Yuichi Yoshida
Reachability Queries

SIGMOD2017, Chicago, IL, USA,May 14-19

A Weighted Linear Matroid Parity Algorithm

Satoru Iwata, Yusuke Kobayashi

STOC2017, Montreal, Canada,June 19-23

High Dimensional Consistent Digital Segments

Man-Kwun Chiu, Matias Korman

SoCG2017, Brisbane, Australia,
July 4-7

On the Average-Case Complexity of MCSP and its
Variants

Shuichi Hirahara, Rahul Santhanam

CCC2017, Riga, Latvia, July 6-9

Online Optimization of Video-Ad Allocation

Hanna Sumita, Yasushi Kawase, Sumio Fujita,
Takuro Fukunaga
Hanna Sumita, Yuuma Yonebayashi,
Naonori Kakimura, Ken-ichi Kawarabayashi

IJCAI2017, Melbourne, Australia,
August 19-25
IJCAI2017, Melbourne, Australia,
August 19-25

An Improved Approximation Algorithm for the Subpath
Planning Problem and Its Generalization

主要受賞

2017 年 3月～2017 年 8月

受賞年月2017 年 4 月
2017 年 6 月

受賞者

受賞名

主催団体名

吉田 悠一

平成 29 年度 科学技術分野の文部科学大臣表彰 若手科学者賞

文部科学省

小林 佑輔

Best Paper Award

The 49th ACM Symposium on Theory ofComputing（STOC2017）

イベントの様子2017.6.9～10 国立情報学研究所オープンハウス2017（学術総合センター）

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