グラフマッチング

グラフマッチングはグラフ間の類似性を見つける問題である。^[1]

グラフは、コンピュータービジョンやパターン認識など多くの分野で構造情報をエンコードするために一般的に使用されており、グラフマッチングはこれらの分野で重要なツールです。^[2]これらの分野では、比較はデータグラフとモデルグラフの間で行われると一般的に想定されています。

グラフの完全一致のケースはグラフ同型性問題として知られています。^[1]あるグラフを別のグラフの一部に完全一致させる問題は、部分グラフ同型性問題と呼ばれます。

不正確なグラフマッチングとは、2つのグラフの頂点の数が異なるなど、正確なマッチングが不可能な場合のマッチング問題を指します。この場合、可能な限り最適なマッチングを見つける必要があります。たとえば、画像認識アプリケーションでは、画像処理における画像セグメンテーションの結果は通常、マッチングが期待されるモデルグラフよりもはるかに多くの頂点数を持つデータグラフを生成します。属性付きグラフの場合、頂点と辺の数が同じであっても、マッチングは依然として不正確な場合があります。^[1]

検索方法には、2つのグラフ間の頂点の可能なペアリングと不可能なペアリングの識別に基づく方法と、グラフマッチングを最適化問題として定式化する方法の2つのカテゴリがあります。^[3] グラフ編集距離は、グラフマッチングに提案されている類似度測定の1つです。 ^{[4] [5]}このクラスのアルゴリズムは、エラー耐性グラフマッチングと呼ばれます。^[5]

• 文字列のマッチング
• パターンマッチング

ウィキメディア・コモンズには、マッチングに関連するメディアがあります。