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

使用谱算法开发旨在再现性的高性能并行图分析方法

• 批准号: 22K12046
• 负责人: 二村 保徳
• 金额: $ 2.66万
• 依托单位: University of Tsukuba
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K12046/
• 关键词: 再現可能並列性; スペクトラルアルゴリズム; 固有値解析; グラフ解析; 固有値計算; 数値線形代数; 並列計算

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

谱图分析方法是基于从图定义的各种矩阵（例如图拉普拉斯）的特征空间来执行各种图分析任务的方法。该方法具有谱图理论支持的理论基础，并已应用于各种图分析任务，例如图分割、图聚类、社区检测、异常检测和图神经网络。基于局部优化的离散启发式方法（例如图分区任务中标准使用的多级方法）无法实现高并行性能，除非它们涉及解决方案可以根据写入顺序而变化的异步处理，因此通常会牺牲可重复性。另一方面，谱算法往往需要比离散启发式更大的计算量，但它们是并行算法，在相同的计算环境、参数、随机数种子和并行度下执行时可以获得相同的近似解。它具有易于实现的“可再现并行性”的理想特性。在该项目中，代表们利用测地距离投影方法扩展了新开发的高速并行谱图分析方法，用于社区检测等新的图分析任务，并开发了可重复的高速并行算法。特别是，我们解决了以下问题：1）非常稀疏的图的精度下降，2）具有高度偏差的顶点度分布的图的精度下降，以及3）通过考虑我所研究的浮点运算的非关联性来保证再现性。它。我们进行研究的目的是开发一种可以处理各种图形类型的高精度方法，并阐明严格保证再现性和性能之间的权衡。

项目成果

Search for a characteristic low-dimensional space by local structures and dimensionality reduction

通过局部结构和降维寻找特征低维空间

• 发表时间: 2022
• 作者: Ryo Tamura;Jianbo Lin;Yasunori Futamura;Tetsuya Sakurai;and Tsuyoshi Miyazaki
• 通讯作者: and Tsuyoshi Miyazaki