河原林健一

NII教授所在地：神保町・竹橋（NII)本郷
NII 副所長
２０１９－２０２１
Shonan Meeting Chair
２０１７－



専門分野（詳細）： グラフ理論（離散数学），アルゴリズム
理論計算機科学、グラフアルゴリズム，高速アルゴリズム開発
国際会議： STOC, FOCS, SODA（理論), LICS（論理）ICML, NeuRIPS, ICLR, AISTAT(機械学習）,SIGMOD, VLDB, ICDE(データベース）、
KDD, WWW, CIKM(データマイニング）, AAAI, IJCAI（ＡＩ）, ACL（自然言語）研究歴：～2005年: グラフ理論、離散数学 → 数学のみ
2005～2011年: グラフ理論, アルゴリズム → 数学＆CS
2011年～ グラフ関連何でも！
2012～2019年: JST ERATO「河原林巨大グラフ」 PD １６億
2018～2026: 基盤S PI 2億（5年）
2019～: JST ACT-X「数理と情報」 研究総括
受賞歴
2008年： 日本IBM科学賞
2013年： 日本学術振興会賞・日本学士院奨励賞、SODA’13 BEST PAPER
2015年： 日本数学会春季賞
２０２１年： Fulkerson Prize(離散数学、アルゴリズムで世界で最も権威ある賞）アルゴリズムと離散数学研究室（BRAND NEW!)

情報科学の達人主催
この本を買わずして何を買う！とは言ってない。
小さいところだけ

教授： 河原林 健一（多分左）  研究トピック（アルゴリズム全般）
NII（国立情報学研究所）教授
１．グラフ理論、離散数学
所在地：神保町・竹橋（NII)
２．グラフアルゴリズム → 理論的に速いアルゴリズム開発

NII

グラフカット、グラフ彩色、フローなど
３．高速アルゴリズム → 実装して速いアルゴリズム
最短パス、検索など
４．グラフ関連何でも → 深層学習（GNN), 自然言語処理
データ解析などへの応用
５．データ構造・組合せ最適化・理論計算機科学

数学・計算機科学分野の超難問とブレイクスルーの要請
・P vs NP （7大数学難問の一つ）
・Shorの素因数分解の多項式「量子的」アルゴリズム→ 現在の「量子コンピューター」ブームのきっかけ！
ハードウェアの限界 アルゴリズムからのスピードアップ！
・ムーア則の限界から、ハード面（特にCPU）で100倍スピードアップ達成は難しい。
・しかしアルゴリズムでは100倍スピードアップは日常茶飯事
5







アルゴリズム理論の導入による新しい実用手法がGAFAを作り、 IT社会を先導！
・ 検索エンジン（HITS，PAGERANKなど)
・ 暗号（RSA暗号など）
・ プライバシー（差分プライバシーなど）
・ バイオインフォマティクス
機械（深層）学習ブーム
・ Explainable AI (アルゴリズムの解析が必要！）
・ スケール化とアルゴリズムの効率化が必要！
量子コンピューターブームのきっかけ
・ Shorの素因数分解の多項式「量子的」アルゴリズム

6

３

Min-Cut: グラフアルゴリズムで最も歴史があり、有名な問題
具体的貢献： 決定的(deterministic)な、ほぼ線形アルゴリズムを開発！
(Journal of ACM 2018)→ Fulkerson Prize 2021!
アルゴリズム、組合せ最適化、ネットワーク、グラフ理論などにおける当該分野のトップ国際賞

Min-cutの歴史は？

Min-cutの歴史
m,n: # of vertices, edges, respectively.
Ｒａｃｅ ｂｙ ｍａｎｙ “ｇｉａｎｔ” ｒｅｓｅａｒｃｈｅｒｓ ｉｎ ｔｈｅｏｒｙ！
Ｆｏｒｄ ａｎｄ Ｆｕｌｋｅｒｓｏｎ’５６O(mn2) ← ＯＲの創立者！
Ｅｖｅｎ ａｎｄ Ｔａｒｊａｎ’７５O(nm1.5) ← Ｔｕｒｉｎｇ賞受賞者
Ｋａｒｚａｎｏｖ ａｎｄ Ｔｉｍｏｆｅｅｖ’８６ O(n3)← ロシア学派
Ｈａｏ ａｎｄ Ｏｒｌｉｎ’９２O(nm log(n2/m)) Ｄｅｔｅｒｍｉｎｉｓｔｉｃ
Ｎａｇａｍｏｃｈｉ ａｎｄ Ｉｂａｒａｋｉ’９２ O(nm+n2log n)
Ｄｅｔｅｒｍｉｎｉｓｔｉｃ
Ｋａｒｇｅｒ’９４
O(mn0.5)(Ｒａｎｄｏｍｉｚｅ, Ｍｏｎｔｅ Ｃａｒｌｏ) J.ACM
Ｋａｒｇｅｒ ａｎｄ Ｓｔｅｉｎ’９６
O(n2 log3 m)(Ｒａｎｄｏｍｉｚｅ, Ｍｏｎｔｅ Ｃａｒｌｏ)
Ｋａｒｇｅｒ’９９O(m log3 n)(Ｒａｎｄｏｍｉｚｅ, Ｍｏｎｔｅ Ｃａｒｌｏ) J. ACM
ＫＫ ａｎｄ Ｔｈｏｒｕｐ（ＳＴＯＣ’１５） O(m log5 n)Ｄｅｔｅｒｍｉｎｉｓｔｉｃ！ J.ACM

基礎研究の貢献：ネットワークの構造利用
現実のソーシャルネットワーク→ 低次数の頂点が縁でツリー状（木分解）になっている構造

この性質を積極的に利用
１．PageRankの計算（通常の３－５倍高速化）（VLDB'14)
２．SIMRANKの掲載（７００－１０００倍）

CoreFringeVertex Ranking Measure

ImportantComputing
PageRank
for large webgraphs is very
important forweb searchengine!
(Google etc)

代表的応用: PageRank(重要度)x = (1-a) Ax + a b

Aは隣接行列！
各ユーザは確率 a でホームページ b に戻り，確率 (1-a) で次のページに進む
x の値 = そのノードにいる確率 = 重要度

A のグラフ構造を利用して効率的にPageRank （逆行列）を計算する！

28/43

従来手法：
 反復法：「x ← (1-a) A x + a b を繰り返す」
・早くはないが，大規模なグラフでも動く 直接法：「ガウスの消去法で解く」
・基本的に動的計画法
・実際のウェブでは，計算が終わらない提案手法：
グラフの木分解を「前処理」で行い，コア以外は直接法，コアは反復法で解く！

29/43

 コア以外：「木幅が小さい」－直接法で早い！
－動的計画法で動く！

 コア：「エクスパンダー」－直接法は遅い！
－反復法がすばやく収束

CoreFringe

web-Stanford (281k nodes, 2M edges)

Our Contribution

A fast and accurate algorithm for real-world
networks
 1/3 real-time than power iteration
twitter-2010
64 × 106 vertices
1 × 109 edges

uk2007105 × 106 vertices
4 × 109 edges

研究成果（例） Ｔｗｉtterのリアルタイム解析

データマイニングトップ会議のKDDで発表
Ｈａｙａｓｈｉ, Ｋ., Ｍａｅｈａｒａ, Ｔ.,Ｔｏｙｏｄａ, Ｍ. ＆ Ｋａｗａｒａｂａｙａｓｈｉ, Ｋ.
Ｒｅａｌ-ｔｉｍｅ Ｔｏｐ-Ｒ Ｔｏｐｉｃ Ｄｅｔｅｃｔｉｏｎ ｏｎ Ｔｗｉｔｔｅｒ ｗｉｔｈ Ｔｏｐｉｃ Ｈｉｊａｃｋ Ｆｉｌｔｅｒｉｎｇ
ＡＣＭ ＳＩＧＫＤＤ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ(ＫＤＤ), 2015 その後，日刊工業新聞の一面に掲載
取り除かれた不正トピックの例
••
•
•

広告系
シネマトゥデイ 妖精 トム 映画 ハリウッド 戦闘 クルーズ 主演
発売 2013 情報 開催 参加 商品 入荷
限定 情報 開催 イベント 好評 商品 @******
リプライ 富士山 樋口 フェスティバル 興味 早稲田 開催 現在 不問 募集 スタッフ 大

拡散系• リフォロー アカウント 19836 フォロワー Only 希望 支援 696382 交流 相互• 無料 日本 拡散 希望 2013/04 リプボット系• 特徴 燃料 格闘 操縦 射撃 装甲 整備 評価 機動• 所有 City ポイント 前回 Tweet アクセス 獲得 Intel• 自動 だれ 宣伝 AutoTweet オートツイート Twitter 定期 設定 サイト• とノ ω・ ┏┓ ┃┏ ┓┃ ┗┛ ┗┓ ┃┗ ┏┛ ┛┃ ─┘• ┗━┛ ┃ぅ ━┫ ━┓ Å・ ┃ぉ ●∩ ┳⊂ ┃ょ 。) ┏━ 。・• *・ ゚・* :.。..。.: *・' *゚'・ :.。. .。.:顔文字系

著者の感想「理論的にはあまりたいしたことない．
でもうまく「数理科学」の知識を組みあわせることができた．」→数理科学の知見を効果的に組み合わせることで可能に！
学生さんの「推進力（実装力）」も大きな武器に！
産業界から問い合わせ多数！

その他の具体的な研究対象
１．グラフ理論、離散数学
4色定理とその拡張、グラフ構造に関する研究など
２．グラフアルゴリズム → 理論的に速いアルゴリズム開発
グラフ彩色問題（グラフ彩色に関する近似アルゴリズム開発）など
３．グラフ関連何でも深層学習（GNN), 自然言語処理、データ解析、実ネットワークへの応用。グラフ理論、グラフアルゴリズムなどの応用。
４．データ構造・組合せ最適化・理論計算機科学

１．「最適化」問題をセンスよく、かつ効率的に解く技術を多数もっている。
２．データサイエンスから派生する問題を、（近似的に）解決可能に「定式化」 する技術を多数持っている。特に物理学者などが作った「モデル」の精神を引き継ぎながら、計算可能なモデルに変更する能力に長けている。
→ アルゴリズムを動かすときに、式の魂の叫び＆パラメーターの悲鳴が聞こえる！行列＆グラフ＆多面体の形が見える！
3. 幅広い数学の道具を、「広く」＆「浅く」組み合わせることができる！
→ 離散数学、アルゴリズムの専門家のみが可能！これこそ汎用性！

意欲的な皆さん、一緒に研究しましょう！
１．「難しい」研究課題に対して２．「理論ベース」アプローチで３．「未来」の人材（５年後に世界的に競争力ある世代）が４．「国際的な」研究成果を見せる！
そのために必要なこと
１．離散数学（グラフ理論、組合せ論）、グラフアルゴリズム、組合せ最適化等の最先端の成果と知見を得る←私の専門！
２．優秀な大学院生を巻き込む→ スーパーエリートへの道筋を作る！

日本のVISIBILITY向上へ！

Question？