JST ERATO

河原林巨大グラフプロジェクト

Newsletter 3
Kawarabayashi Large Graph ProjectMarch2016

vol.

研究総括より感謝祭と WINTER FESTA
研究総括

河原林 健一Ken-ichi Kawarabayashi

例年、本プロジェクトは、4 つのイベントを行っている。そのうち 2 つは、9 月に行われる「中間報告会」と年度末に行われる「成果報告会」であり、この二つのイベントは、本プロジェクトで雇用された研究員、および RA（リサーチアシスタント）の研究成果発表の場である。ERATO に雇用されている人は、当然研究成果を報告する義務があるであろう。しかし未発表（査読中または論文制作中）の結果も多く、この二つのイベントは、一般の方に完全なオープンな形にはできない。
この二つのイベント以外に、本年度は 8 月に「ERATO 感謝祭SeasonII」、12 月に「情 報 系 WINTER FESTA（JST の ERATO・CREST・さきがけ、科研費の基盤（S）、新学術領域研究）合同ワークショップ」を行った。前者は、今年度のトップ会議・トップジャーナルに採用された論文発表の講演を中心に行い、後者は、研究員のポスター発表を中心に行った。この二つのイベントは、すでに論文発表を行った研究成果発表であるので完全にオープンな形である。
感謝祭の開催意図は、年齢、地位に関係なく、その「年」に良い研究成果を挙げた研究者にチャンスをあげることである。
通常の学会や大きな国際会議での「招待講演」では、キャリアと名声が考慮され、かつ「政治的」な配慮がなされることが多い。したがって有名大学の教授、あるいは有名 IT 企業の研究者による講演が多くなる。感謝祭では、そのような要素を一切排除して、純粋にその年に良い論文を発表した研究者のみ

国立情報学研究所 情報学プリンシプル研究系 教授／ビッグデータ数
理国際研究センター センター長。専門分野は離散数学におけるグラフ彩色問題、グラフ構造理論とアルゴリズム、ネットワークフローとパス問題。
主な受賞に、日本数学会 2015 年度日本数学会春季賞［2015］、第 9 回日
本 学 術 振 興 会 賞、第 9 回日本 学 士 院 学 術 奨 励 賞［2013］、ACM-SIAM
Symposium on Discrete Algorithms（SODA13）Best Paper Award［2013］、公益財団法人船井情報科学振興財団 船井学術賞船井哲良特別賞（アルゴリズム的グラフマイナー理論の研究とその応用）［2011］がある。に講演をしてもらっている。その結果、講演者は、学生、PDような「講演」のみの研究発表会では、研究者同士の討議は（ポスドク研究員）、若手研究者が中心となり、自分の世代のあまり期待できない。従って研究成果へのフィードバックなどを講演者が「最年長」となった。しかしこの状況は、世界のトップ直接得る場を作る必要があると思った。結果、今回の合同ワー会議での講演者を鑑みると、極めて自然である。本プロジェク

クショップには 200 人近い研究者が出席し、その大半が若手トの研究員、RA、そして関係各方面の若手研究者の方々か研究者であった。若手研究者を中心に、ポスター発表で研究ら、「感謝祭」で発表することが名誉である、と思われるような討論が活発に行われたと思う。

研究集会にしたい。そして、その年の研究ハイライトを聞きたければ、感謝祭へ！という形にしたいと思う。

感謝祭は、その年の研究ハイライトの発表の場（優秀な若手研究者を売り出す場）、そして合同ワークショップは、新しい合同ワークショップの開催意図は二つある。一つ目は基礎研究交流を始める場として、今後も続けていきたいと思う。本

系の大型研究プロジェクト同士の交流（とくに若手研究員同プロジェクト終了後に、この二つのイベントを継続できるかどうか士の交流）の場を設けること。二つ目は研究成果と手法をじっはわからないが、どのような形にせよ「若手研究コミュニティ」くり研究者同士で討議する機会を設けることである。感謝祭のが継続していくことを願っている。

2015.8.3〜4 ERATO 感謝祭 SeasonⅡ2015.12.22〜23 情報系 WINTER FESTA 〜基礎から変える情報分野〜

研究紹介

グラフ理論によるデータベース匿名化

近年、個人情報を含むデータが公開されるようになってきています。例えば、誰が税金をいくら払ったか？といった内容のものです。こういったデータは、研究のためにとても役立つものなのですが、一方で、個人のプライバシーが暴かれてしまうことにもつながります。ですので、図のように、個人の名前は伏せて、特定の個人がいくら税金を払ったか、などということが分からないようにしてから公開されています。このような情報の編集を、「匿名化」と言います。さて、図のような匿名化をして、それで十分でしょうか？まずいことに、この場合、神保学さんが 52 歳の男性だと知っている人には、彼が税金をいくら払っているかが分かってしまいます。このことから分かるように、匿名化をするといっても、うまい工夫をしないと、あっという間に個人が特定できてしまうのです。様々なプライバシー漏洩の可能性に対応して、様々な匿名化手法が提案され、盛んに研究されています。
私は、グラフ理論という数学の理論を使って、このデータベース匿名化を、個人情報が 漏れにくいように、かつ高 速に行うための方法を研究しています。数学の理

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

夫紀恵

大いに立つ、というところに、大きな魅力をNorie Fu

国立情報学研究所

論が、実社会の役に感じています。
特任研究員

2013 年 3月、東京大学大学院情報理工学系研究科博士課程終了。2013 年 4月より現職。
グラフアルゴリズムを作ること、特に、グラフや最適化問題の理論を代数的な観点から研究することに興味を持つ。

機械学習で
Web データに潜む規則を明らかにする機械学習の Web データへの応用について研究しています。Web データは Webページのアクセスログや、ショッピングサイトの購買履歴、SNS 上のユーザ同士のやりとりなど多岐にわたります。こうしたデータの規則性が分かると、例えば Web 上で今流行っている話題の早期発見や、ユーザ一人ひとりの好みに合った情報や商品の推薦につながります。しかし Web データはとても大きく、しかも日々増え続けています。人手で調べても背後にある規則性は中々見えてきません。そこで機械学習の登場です。機械学習はデータを学習することで、隠れた規則性を明らかにする技術です。実際に前述のような応用で活躍しています。
具体例として、最近取り組んでいる検索クエリからのトピック抽出の研究を紹介します。検索クエリは皆さんが検索サイトに入力するキーワードのことです。検索クエリには同じように使われる単語があり、それらが共通のトピックをもつと考えられます。
このトピックもデータに潜む規則だとみなせるので、検索クエリの履歴から機械学習で推測することができます。これらトピックを抽出することで、検索クエリを入力したユーザが関心のあるトピックの予測などに応用できると考えています。

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

小西 卓哉

Takuya Konishi

国立情報学研究所特任研究員

2015 年 3月、奈良先端科学技術大学院大学情報科学研究科博士後期課程修了。2015 年 4月より現職。
Webデータへの機械学習・データマイニングの応用に興味をもつ。

社会的ネットワークと協力行動の関係についての実験研究を行っています。コス
トをかけて他者を助ける行動は助けない行動よりも本来不利ですが、特定の社会的ネットワーク構造の元では有利になり得ることが進化ゲーム理論で示されています。
私は本プロジェクトで、これらの理論が現実の人間行動を反映しているかどうかを実証的に検討しています。人を対象とした実験を手法として用いています。

社会的ネットワークに関する実験研究

例えば、ネットワークの形態によって協力行動が伝染していく程度が異なるかを実験的に調べました。誰かから助けてもらった恩を別の人に返す 恩送り（図 a）、前に誰かを助けた人のことを助ける
評 判 に基づいた協力（図 b）、いずれも私たちの日常でよく見られる現象ですが、どちらのかたちが集団全体に協力行動を伝染させていく力が強いかを、大人数の参加者の間でお金を分配し合う経済実験を通して検討しました。社会科学での行動実験手法と情報学での数理的解析を交えることで実現可能な課題です。制度設計など現実社会への応用のためには、実証結果に応じて現実の人間行動を反映させた理論を再構築していく過程が重要であると思います。

私の研究分野は計算幾何学とグラフ理論です。このプロジェクトでは、私は主に幾何ネットワークに関する研究を行っています。幾何ネットワークは、幾何的な構成要素により定義されるグラフであって、経済学や無線ネットワーク通信、および生命化学などの多彩な分野に現れます。過去 20 年ほどの間、これらのネットワークに関する計算および解析に関する数多くの研究が進められてきましたが、それらの研究で扱われるネットワークの多くは静的なものでした。一方、最近の応用では、扱われるネットワークの多くは動的なものとなっています。例えば、無線ネットワークにおいてノードは移動するため、ノード間の接続は切れる可能性があると同時に、新たな接続が生まれる可能性があります。このようなネットワークは動的 (kinetic) ネットワークと呼ばれます。私の研究の目的は、動的ネットワークが時間とともに変化するときに、そのネットワークのもつ重要な特性と統計量を保つための効率的な手法を見いだすことです。
そのような問題の具体例としては、無線アドホックネットワークにおける干渉が挙げられます。無線ネットワークでは、各ノードは互いにメッセージを送ることによって通信を行います。
しかし、あるノードに対して、非常に多くのノードからメッセージが同時に送信されると、それらのメッセージは互いに干渉します。そのため、受信側のノードは送信されたメッセージを正しく受信することができなくなり、その結果、送信ノードは同じメッセージを再度送信しなければなりません。これにより、通信速度は遅くなるとともに、通信装置の電力消費量が増加します。この問題の解決策として、静的なネットワークの場合には、各ノードから通信可能な距離を制限するか、各ノードが異なる周波数を用いて通信する、という方法が用いられてきました。私の研究では、動的なネットワークにおいてこのような問題をどのように解決すべきか考えています。ネットワークが時間と共に変化する状況において、ノード間の干渉を制限するために、各ノードへの周波数割当と通信半径をいつ、どのようにして変更すべきかを決定するアルゴリズムの開発に取り組んでいます。

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

堀田 結孝
Yutaka Horita

国立情報学研究所

特任助教

2011 年 3月、北海道大学大学院文学研究科博士課程修了。
2011 年 4月から2013 年 9月まで日本学術振興会特別研究員
PD。同年 10月より現職。
社会的ネットワークと人間行動との関係についての実証的研究に関心を持つ。

動的幾何ネットワークの研究

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

Marcel Roeloﬀzen
マ ル セ ル ル ロフゼ ン

国立情報学研究所

特任助教

2013 年 10月、アイントホーベン工科大学大学院博士課程終了。
アイントホーベン大学博士研究員、東北大学特任助教を経て2015 年 4月より国立情報学研究所 特任研究員、2015 年 10月より現職。

アウトリーチ「大分スーパーサイエンスコンソーシアム」
県外科学研修 数学班への講義
場所：国立情報学研究所

日時：2015 年 7月29日 14:00 ー 16:30

大分県より数学に興味を持つ生徒 8 名が NIIを訪れ、ビッグデー
タ数理国際研究センター（ERATO 河原林巨大グラフプロジェクト）の研究員が「数学を使った情報学」の研究紹介を行った。プレゼ
ンターは河原林センター長と、大輪拓也、小関健太、町出智也、澄田範奈、阿部真人ら5 人の研究員。センター長の「ComputerScience（計算機科学）とは？」の解説に続いて、5 人の研究員がそれぞれの研究を紹介した。
まずは河原林センター長。
「コンピュータの動作を保証しているのは数学」という導入から、12 個のテニスボールに紛れている少し目方の重い欠陥品を見つけ出す方法、16 個の重さの異なるテニスボールを重い順に並べ替える方法を、「トーナメント判別法」を用いると総当たりで比べるより少ない回数で判別することができると紹介。
河原林健一 センター長「これらの手順はコンピュータがしているソーティングという動作と同じ。実はコンピュータは 2 つの数字の比較しかできないので、賢い方法で並べ替えをする方法、すなわち良いアルゴリズム（解決方法）が必要。良いアリゴリズムはコンピュータによる問題解決に要する時間（計算量）を決定する大きな要因のひとつとなる。また、離散数学は巨大なデータを扱う問題、例えば国勢調査など、1 億以上のデータを扱う場合などに役立つ。世の中で、人を納得させる唯一の道具は数学だけ。数学の定理を信用して、現実の問題を数学的に定式化する必要がある。将来的には問題を作る能力、解きたくなるような問題を作れる力、すなわち、問題を発見する能力が重要」

研究員が続く。
大輪研究員（グラフマイニング &WEB&AIグループ）は「ランダムな方法で暗号を解く」と題して、確率の理論を用いた方法で換字暗号を解く方法を紹介。
大輪拓也 研究員（グラフマイニング&WEB&AIグループ）

聴講者：大分県の高校 1 年生

8名

町出研究員（グラフ・ネットワークにおける理論と最適化グループ）は「行列のランクを機械学習を使って計算する」と題して、オイラーが研究していたゼータ関数を、解析接続を用いて複素数全体への拡張を行い、複素数全体 (s ≠ 1) へゼータ関数を拡張した場合、「ζ(s) の自明でない零点 s は、全て実部が 1/2 の直線上に存在する」と予想した、いわゆる「リーマン予想」（史上最難の問題のひとつ、と言われている）（Wikipedia 参照）を紹介。
町出智也 研究員（グラフ・ネットワークにおける理論と最適化グループ）「多重ゼータ値から作られる行列のランク付けを機械学習を使って研究してみたい」

澄田研究員（グラフ・ネットワークにおける理論と最適化グループ）は「日常における最適化問題」と題して、日常の中の乗換案内、献立問題、スケジューリング、おやつの配分など、いろいろな最適化の例を紹介した。
澄田範奈 研究員（グラフ・ネットワークにおける理論と最適化グループ）「日常を定式化し、アルゴリズムを使ってできるだけ早く解き、それを現実に戻す。それを考える。食糧の配分、エネルギーの配分問題などにも応用できる。人々は最適化しながら生きている」

阿部研究員（複雑ネットワーク・地図グラフグループ）は「社会をネットワークとして解き明かす」と題し、一例としてアリの順位行動をグラフ化にして紹介した。
阿部真人 研究員（複雑ネットワーク・地図グラフグループ）「総当たりだと60 兆年かかってしまうが、ランダムな方法（ランダムウォーク理論、マルコフ連鎖の理論）を使うと0.13 秒しかかからない。
ランダムウォークはウェブサイトのページランキングなどデータ解析に応用されており、数学の研究とビジネスは結びついている」「複雑ネットワーク、生物、食物網、タンパク質などの実際にあるものを数理モデル化し科学する。人から人へ伝わること、例えば感染症、周囲の関係性、文化が科学的にわかるようになるかもしれない。
数学を使って生物をわかるようになりたい」

小関研究員（グラフ・ネットワークにおける理論と最適化グループ）は「グラフのハミルトン経路問題」と題して、NP 困難問題のひとつである「巡回セールスマン問題」をチェスのナイトの駒（ナイトツアー・チェスを使った数学的パズルの一種）を使って解説。多項式時間アルゴリズムが見つかりそうにな
いこの問題に関連して、ハミルトン経路問題は与えられたグラフについて、全ての頂点を一度だけ通る閉路が存在するかどうか調べる問題であると紹介。

生徒たちは熱心に研究員の話に耳を傾けた。
「具体的でわかりやすい講義だった」「数学が現実の生活に役立っているなんて思いも寄らなかった」「できないことを証明するのは難しいと、考えたことがなかった」「身近にあることを定式化するって面白そう」「今までは問題を解く能力を重要視していたが、問題を発見する能力の重要性を認識した」「数学や情報学は他の分野にも通じる。数学を通してすべての事を真剣に考える人になりたい」など感想をいただいた。

小関健太 研究員（グラフ・ネットワークにおける理論と最適化グループ）「全検索してできなかったと証明するのは時間がかかるので、できない理由をうまく説明する方法を考えている。できないことを証明するのは、できることを証明するより難しい」主要な研究成果

2015 年 9月〜 2016 年 2月 国際学会発表論文

論文名
著 者
An average-case depth hierarchy theorem for Boolean Benjamin Rossman, Rocco A. Servedio, Li-Yang Tancircuits

会議名FOCS2015, Berkeley, CA, USA,Oct 18-20

The Average Sensitivity of Bounded-Depth Formulas

FOCS2015, Berkeley, CA, USA,Oct 18-20

Benjamin Rossman

What Is a Network Community? A Novel Quality Function Atsushi Miyauchi, Yasushi Kawase
and Detection Algorithms

CIKM2015, Melbourne, Australia,
Oct 19-23

Monotone k-Submodular Function Maximization with Size Naoto Ohsaka, Yuichi Yoshida,
Constraints

NIPS2015, Montréal, Canada,
Dec 7-12

A Generalization of Submodular Cover via the Diminishing Tasuku Soma, Yuichi Yoshida,
Return Property on the Integer Lattice

NIPS2015, Montréal, Canada,Dec 7-12

Gowers Norm, Function Limits, and Parameter Estimation

SODA2016, Arlington, VA, USA,Jan 10-12

Yuichi Yoshida

Improved Approximation Algorithms for k-Submodular Satoru Iwata, Shin-Ichi Tanigawa and Yuichi Yoshida
Function Maximization

SODA2016, Arlington, VA, USA,Jan 10-12

Exact and Approximation Algorithms for Weighted Chien-Chung Huang, Naonori Kakimura,
Matroid Intersection
Naoyuki Kamiyama

SODA2016, Arlington, VA, USA,Jan 10-12

Expected Tensor Decomposition with Stochastic Gradient Takanori Maehara, Kohei Hayashi,DescentKen-ichi Kawarabayashi

AAAI2016, Phoenix, Arizona, USA,Feb 12-17

Joint Word Representation Learning using a Corpus and a Danushka Bollegala, Alsuhaibani Mohammed,
Semantic Lexicon
Takanori Maehara, Ken-ichi Kawarabayashi

AAAI2016, Phoenix, Arizona, USA,Feb 12-17

Extracting Search Query Patterns via the Pairwise Coupled Takuya Konishi, Takuya Ohwa, Sumio Fujita,
Topic Model
Kazushi Ikeda, Kohei Hayashi

WSDM2016, San Francisco, CA, USA,Feb 22-25

主要受賞

2015 年 9月〜 2016 年 2月

受賞年月

受賞者

受賞名

主催団体名

2015 年 9月

東野 克哉

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

2015 年 10月

Benjamin Rossman

Best Paper Award: An average-case depth hierarchy
theorem for Boolean circuits

56th Annual IEEE Symposium on Foundationsof Computer Science [FOCS2015]

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

大輪 拓也

名特任研究員転出時期

2015 年 10月

転出先

株式会社富士通研究所

川崎研究所

イベントの様子「ICIAM 2015 TV」撮影風景 2015.7.24

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