2022.03.22

1. Intro

前人工作:容忍错误和畸变

  • graph edit distance (Shapiro and Haralick, 1981; Bunke, 1997.)
  • maxiaml common subgraph (Horaud and Skordas, 1989; Levinson, 1992)

度量(metric)的要求：

  • d(A,B)=0 <=> A=B
  • d(A,B)=d(B,A)
  • d(A,B)+d(B,C)<=d(A,C) （三角形距离）

三角形距离这个我还没考虑好 （空间&子空间（操作码子空间、立即数子空间）就可以满足好三角形距离）

2. Basic definitions

  1. graph
  2. subgraph
  3. graph isomorphism (bijective)
  4. subgraph isomorphism (injective)
  5. common subgraph
  6. maximal common subgraph

3. Graph distance measure

d(G1,G2) =: 1 - |mcs(G1,G2)|/max(|G1|,|G2|)

这样的距离定义是个度量

然后是证明

4. Discussion and conclusion