スペクトラルアルゴリズムによる再現性を指向した高性能並列グラフ解析手法の開発

点击翻译按钮获取中文摘要

スペクトラルグラフ解析手法は、グラフから定義される各種行列（グラフラプラシアン等）の固有空間に基づき、各種のグラフ解析タスクを行う手法である。本手法はスペクトラルグラフ理論に裏付けられた理論基盤を持ち、グラフ分割や、グラフ上のクラスタリング、コミュニティ検出、異常検知、グラフニューラルネットなど、さまざまなグラフ解析タスクに応用されている。グラフ分割タスク等で標準的に使われているマルチレベル型手法のような局所最適化に基づく離散型のヒューリスティックでは、書き込み順序によって解が変わりうる非同期処理を伴わなければ高い並列性能が得られないため、通常、再現可能性を犠牲にする。一方、スペクトラルアルゴリズムは離散型のヒューリスティックと比べ、計算量が大きくなる傾向があるが、同一の計算環境・パラメータ・乱数シード・並列度での実行において同一の近似解を得ることができる並列化の実現が容易である「再現可能な並列性」という好ましい性質がある。本課題では代表者らが新たに開発した測地距離型射影法による高速並列スペクトラルグラフ解析手法をコミュニティ検出等、新たなグラフ解析タスク向けに拡張し、再現性のある高速並列アルゴリズムの開発を進めた。特に、以下の課題：1) 非常に疎なグラフに対する精度劣化、2) 頂点次数分布の偏りが大きいグラフに対する精度劣化、3) 浮動小数点演算の非結合性の考慮による再現可能性の保証、について取り組んだ。幅広い種類グラフに対応した高精度化手法を開発を見据え、また再現可能性の厳密な保証と性能とのトレードオフを明らかにすることを目的に研究を進めた。