logo

グラフとグラフの間の編集距離 📂グラフ理論

グラフとグラフの間の編集距離

定義 1

頂点の有限集合 XX と有限なアルファベットの集合を α\alpha としよう。ここでアルファベットは空白またはヌルnullを含むとする。頂点ラベリングvertex labeling V:X→αV : X \to \alpha とエッジラベリングedge labeling E:X×X→αE : X \times X \to \alpha により、トリプル G=(X,V,E)G = (X, V, E) をグラフという。G^=(X^,V^,E^)\hat{G} = \left( \hat{X}, \hat{V}, \hat{E} \right) が GG のサブグラフであるとは、以下の三つの条件を満たすことを意味する：

  • X^⊂X\hat{X} \subset X
  • ∀x∈X^\forall x \in \hat{X} に対して V^(x)=V(x)\hat{V}(x) = V(x)
  • ∀(x,y)∈X^×X^\forall (x, y) \in \hat{X} \times \hat{X} に対して E^(x,y)=E(x,y)\hat{E} \left( x , y \right) = E \left( x , y \right)

ecgm

G1=(X1,V1,E1)G_{1} = \left( X_{1}, V_{1}, E_{1} \right) と G2=(X2,V2,E2)G_{2} = \left( X_{2}, V_{2}, E_{2} \right) を二つのグラフとする。これらのサブグラフ G^1=(X^1,V^1,E^1)\hat{G}_{1} = \left( \hat{X}_{1}, \hat{V}_{1}, \hat{E}_{1} \right) と G^2=(X^2,V^2,E^2)\hat{G}_{2} = \left( \hat{X}_{2}, \hat{V}_{2}, \hat{E}_{2} \right) に対し、全射 f:X^1→X^2f : \hat{X}_{1} \to \hat{X}_{2} を G1G_{1} から G2G_{2} へのエラー訂正グラフマッチングerror-correcting graph matchingという。

ecgmのコスト

便宜上、エッジラベリングの範囲 E^k(X^k×X^k)\hat{E}_{k} \left( \hat{X}_{k} \times \hat{X}_{k} \right) を E^k\hat{E}_{k} と表す。G1G_{1} から G2G_{2} へのecgm f:X^1→X^2f: \hat{X}_{1} \to \hat{X}_{2} のコストcost c(f)c(f) は次のように定義される。

c(f):=∑x∈X^1cvs(x)+∑x∈X1∖X^1cvd(x)+∑x∈X2∖X^2cvi(x)+∑e∈E^1ces(x)+∑e∈E1∖E^1ced(x)+∑e∈E2∖E^2cei(x) \begin{align*} c(f) :=& \sum_{x \in \hat{X}_{1}} c_{\text{vs}} (x) + \sum_{x \in X_{1} \setminus \hat{X}_{1}} c_{\text{vd}} (x) + \sum_{x \in X_{2} \setminus \hat{X}_{2}} c_{\text{vi}} (x) \\ & + \sum_{e \in \hat{E}_{1}} c_{\text{es}} (x) + \sum_{e \in E_{1} \setminus \hat{E}_{1}} c_{\text{ed}} (x) + \sum_{e \in E_{2} \setminus \hat{E}_{2}} c_{\text{ei}} (x) \end{align*}

  • cvs(x)c_{\text{vs}} (x) は x∈X^1x \in \hat{X}_{1} を f(x)∈X^2f(x) \in \hat{X}_{2} へ変更するコストである。
  • cvd(x)c_{\text{vd}} (x) は x∈X1∖X^1x \in X_{1} \setminus \hat{X}_{1} を G1G_{1} から削除するコストである。
  • cvi(x)c_{\text{vi}} (x) は x∈X2∖X^2x \in X_{2} \setminus \hat{X}_{2} を G2G_{2} に追加するコストである。
  • ces(x)c_{\text{es}} (x) は e=(x,y)∈E^1e = (x,y) \in \hat{E}_{1} を (f(x),f(y))∈E^2\left( f(x), f(y) \right) \in \hat{E}_{2} へ変更するコストである。
  • ced(x)c_{\text{ed}} (x) は e∈E1∖E^1e \in E_{1} \setminus \hat{E}_{1} を G1G_{1} から削除するコストである。
  • cei(x)c_{\text{ei}} (x) は e∈E2∖E^2e \in E_{2} \setminus \hat{E}_{2} を G2G_{2} に追加するコストである。

編集距離

二つのグラフ G1G_{1} と G2G_{2} の編集距離edit distance d(G1,G2)d \left( G_{1} , G_{2} \right) は、G1G_{1} から G2G_{2} へのecgmのコストの中で最小値で定義される： d(G1,G2):=min⁡{c(f):f is an ecgm from G1 to G2} d \left( G_{1} , G_{2} \right) := \min \left\{ c(f) : f \text{ is an ecgm from } G_{1} \text{ to } G_{2} \right\}

説明

一般的な定義に従うと話がやや長くなるが、概念的には非常に簡単である。

例として、上記のような二つのグラフがあるとし、追加、削除、交換のコストがすべて 11 である場合、一方のグラフから頂点とエッジを追加、削除、交換して他方のグラフを作成する方法の中で最も少ない回数がまさにグラフ編集距離である

。上記の場合では、左側のグラフから右側のグラフを作るために1つの頂点を追加し、既存のエッジの1つを新しいノードに接続する交換が必要であるため、グラフ編集距離は 22 である。

参照

  1. Bunke. (1997). On a relation between graph edit distance and maximum common subgraph. https://doi.org/10.1016/S0167-8655(97)00060-3 ↩︎