Weisfeiler-Lehmanアルゴリズムに基づく新しいグラフ構造間距離の提案

• Item type: SIG Technical Reports(1)
• 公開日: 2022-02-18
• タイトル: Weisfeiler-Lehmanアルゴリズムに基づく新しいグラフ構造間距離の提案
• タイトル / 言語: en
• タイトル: A novel graph distance based on Weisfeiler-Lehman algorithm
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学基幹理工学研究科情報理工・通信専攻
• 著者所属: 早稲田大学基幹理工学研究科情報理工・通信専攻
• 著者所属: 早稲田大学基幹理工学研究科情報理工・通信専攻／早稲田大学基幹理工学部情報通信学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Communications Engineering, FSE Graduate School, WASEDA University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Communications Engineering, FSE Graduate School, WASEDA University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Communications Engineering, FSE Graduate School, WASEDA University / Department of Computer Science and Communications Engineering, FSE Graduate School, WASEDA University
• 著者名: 方, 鐘熙; 黄, 健明; 笠井, 裕之
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 有効なグラフ距離の定義は，距離の理論的妥当性，時間複雑性，及びグラフ間の距離としての有効性を考慮する必要があるため，グラフ機械学習における困難な課題である．本稿では，グラフカーネルでよく用いられる Weisfeiler-Lehman（WL）アルゴリズムの欠点に対処し，新しいグラフ構造間の距離を提案する．具体的には，まず WL アルゴリズムを構造解析の観点から分析し，カテゴリラベルの整合性のみに基づいてノードを識別することは，重要な構造情報を十分に捉えないことを論じる．そこで，カテゴリラベルを用いる代わりに，WL 部分木間のノード距離を木構造編集距離で定義し，複雑なグラフ構造を測定することを試みる．さらに，その計算のための効率的なアルゴリズムを提案する．最後に，提案したノード距離を応用し，最適輸送の枠組みを利用した埋め込み空間上のグラフ距離を定義する．要約すると，我々は 2 つのノード間の木構造編集距離を定義し，それをグラフレベルに反映させる．グラフ分類課題に対する数値実験の結果，提案するグラフ Wasserstein 距離は従来手法と同等以上の性能を持つことが示された．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10438399
• 書誌情報: 研究報告オーディオビジュアル複合情報処理（AVM）; 巻 2022-AVM-116, 号 6, p. 1-6, 発行日 2022-02-18
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8582
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会