SimGNN: グラフ類似性計算のためのニューラルネットワークアプローチ

グラフ類似度検索は最も重要なグラフベースの応用の一つであり、例えばクエリ化合物と最も類似した化学化合物を見つけることが挙げられます。グラフ編集距離（Graph Edit Distance: GED）や最大共通部分グラフ（Maximum Common Subgraph: MCS）などのグラフ類似度計算は、グラフ類似度検索やその他の多くの応用における核心的な操作ですが、実際には非常に高コストな処理です。最近のノード分類やグラフ分類など、いくつかのグラフ応用におけるニューラルネットワークアプローチの成功に着想を得て、この古典的かつ困難なグラフ問題を解決する新しいニューラルネットワークに基づくアプローチを提案します。本アプローチは、計算負荷を軽減しつつ良好な性能を維持することを目指しています。提案されたアプローチであるSimGNNは、2つの戦略を組み合わせています。まず、各グラフをベクトルにマッピングする学習可能な埋め込み関数を設計しました。これにより、グラフ全体の要約が提供されます。さらに、特定の類似度指標に関連する重要なノードを強調するための新しい注意機構（attention mechanism）を提案しました。次に、細かい粒度のノードレベル情報でグラフレベルの埋め込みを補完するために、ペアワイズノード比較手法を開発しました。当モデルは未見のグラフに対してより良い汎化性能を持ち、最悪の場合でも2つのグラフ内のノード数に関する二次時間で動作します。GED計算を例にとって説明すると、3つの実際のグラフデータセットに対する実験結果から当アプローチの有効性と効率性が示されています。具体的には、当モデルはGED計算に関する一連の基準モデル（baseline）、いくつかの近似アルゴリズムや既存の多くのグラフニューラルネットワークベースモデルと比較して誤差率が小さく、大幅な時間短縮が達成できることを確認しています。我々が知る限りでは、本研究は初めてニューラルネットワークを使用して2つのグラフ間の類似度を明示的にモデリングし、今後のグラフ類似度計算およびグラフ類似度検索に関する研究に新たな方向性を提示していると言えます。