グラフ編集距離

数学とコンピュータサイエンスにおいて、グラフ編集距離（GED）は、 2つのグラフ間の類似度（または非類似度）の尺度です。グラフ編集距離の概念は、1983年にAlberto SanfeliuとKing-Sun Fuによって初めて数学的に形式化されました。^[1] グラフ編集距離の主な応用は、機械学習におけるエラー耐性パターン認識などの不正確なグラフマッチングです。^[2]

2つのグラフ間のグラフ編集距離は、 文字列間の文字列編集距離に関連しています。文字列を最大次数1の 連結 された有向非巡回グラフと解釈すると、レーベンシュタイン距離^[3]、^[4]ハミング距離^[5] 、ヤロ・ウィンクラー距離などの編集距離の古典的な定義は、適切に制約されたグラフ間のグラフ編集距離として解釈できます。同様に、グラフ編集距離は、根付き木間の 木編集距離の一般化でもあります。^{[6] [7] [8] [9]}

グラフ編集距離の数学的定義は、それが定義されるグラフの定義、すなわち、グラフの頂点と辺にラベルが付けられているかどうか、またそのラベルの付け方、辺が有向かどうかに依存します。一般に、グラフ編集操作のセット（基本グラフ操作とも呼ばれる）が与えられた場合、2つのグラフと間のグラフ編集距離は次のように定義できます 。${\displaystyle g_{1}}$${\displaystyle g_{2}}$${\displaystyle GED(g_{1},g_{2})}$

${\displaystyle GED(g_{1},g_{2})=\min _{(e_{1},...,e_{k})\in {\mathcal {P}}(g_{1},g_{2})}\sum _{i=1}^{k}c(e_{i})}$

ここで、 は( と同型なグラフ)に変換する編集パスの集合を表し、 は各グラフ編集操作のコストです。 ${\displaystyle {\mathcal {P}}(g_{1},g_{2})}$${\displaystyle g_{1}}$${\displaystyle g_{2}}$${\displaystyle c(e)\geq 0}$${\displaystyle e}$

基本的なグラフ編集演算子のセットには通常、次のものが含まれます。

頂点挿入により、グラフに 1 つの新しいラベル付き頂点が導入されます。

頂点の削除は、グラフから単一の（多くの場合、切断された）頂点を削除します。

頂点の置換により、特定の頂点のラベル (または色) を変更します。

エッジ挿入により、頂点のペア間に新しい色付きエッジが導入されます。

頂点のペア間の単一のエッジを削除するエッジ削除。

エッジの置換により、特定のエッジのラベル (または色) を変更します。

追加の、しかしあまり一般的ではない演算子には、エッジに新しい頂点を導入する (新しいエッジも作成する) エッジ分割や、エッジ間の次数 2 の頂点 (同じ色) を削除するエッジ縮小などの操作があります。このような複雑な編集演算子は、より基本的な変換の観点から定義できますが、演算子が構成要素の合計よりも安価である場合、それらを使用すると、コスト関数のより細かいパラメーター化が可能になります。 ${\displaystyle c}$

基本的なグラフ編集演算子の詳細な分析は^{[10] [11] [12]に示されている。}

そして、これらの基本的なグラフ編集演算子を自動的に推論するいくつかの方法が提示されている。^{[13] [14] [15] [16] [17]}そして、いくつかのアルゴリズムはこれらのコストをオンラインで学習する：^[18]

グラフ編集距離は手書き認識^[19] 、指紋認識^[20]、化学情報科学^[21]などに応用されています。

一対のグラフ間のグラフ編集距離を計算するための正確なアルゴリズムは、通常、問題を 2 つのグラフ間の最小コスト編集パスを見つける問題に変換します。最適な編集パスの計算は、パス検索または最短パス問題として表され、多くの場合、 A* 検索アルゴリズムとして実装されます。

正確なアルゴリズムに加えて、多くの効率的な近似アルゴリズムも知られています。それらのほとんどは3乗の計算時間を持っています^{[22] [23] [24] [25] [26]}

さらに、GEDの近似値を線形時間で導くアルゴリズムがある^[27]

上記のアルゴリズムは実際にはうまく機能することもあるが、一般的にグラフ編集距離を計算する問題はNP困難（オンラインで入手可能な証明については、Zengらのセクション2を参照）であり、近似することも困難である（正式にはAPX困難である^[28]）。