그래프 편집 거리

수학 및 컴퓨터 과학에서 그래프 편집 거리(GED)는 두 그래프 사이의 유사성(또는 유사성)을 측정하는 척도다. 그래프 편집 거리 개념은 1983년 알베르토 산펠리우와 킹-썬 푸에 의해 수학적으로 처음 공식화되었다.^[1] 그래프 편집 거리의 주요 적용 분야는 기계학습에서 오류 방지 패턴 인식과 같은 부정확한 그래프 매칭이다.^[2]

두 그래프 사이의 그래프 편집 거리는 문자열 간의 문자열 편집 거리와 관련이 있다. 문자열을 최대도 1의 방향 반복 그래프와 연결된 것으로 해석하면 레벤슈테인 거리,^[3][4] 해밍 거리^[5] 및 자로-윙클러 거리와 같은 편집 거리의 고전적 정의는 적절히 제한된 그래프 사이의 그래프 편집 거리로 해석될 수 있다. 마찬가지로 그래프 편집 거리도 뿌리 나무 사이의 나무 편집 거리를 일반화한 것이다.^[6][7][8][9]

형식 정의 및 속성

그래프 편집 거리의 수학적 정의는 정의되는 그래프의 정의, 즉 그래프의 꼭지점과 가장자리에 라벨을 붙이는지 여부와 방법, 가장자리가 방향을 향하는지 여부에 따라 달라진다. 일반적으로 일련의 그래프 편집 작업(기본 그래프 작업이라고도 함)을 고려할 때 G ${\displaystyle E}$ ${\displaystyle D({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{g\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$)로 기록된 두 그래프 $g{\displaystyle {}_{}}$ 1 ${\$과$($$와$) $g{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$$displaystyle g_{2}}$ 사이의 그래프 편집 거리는 다음과 같이 정의할 수 있다$$$.$

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

where ${\displaystyle {\mathcal {P}}(g_{1},g_{2})}$ denotes the set of edit paths transforming ${\displaystyle g_{1}}$ into (a graph isomorphic to) ${\displaystyle g_{2}}$ and ${\displaystyle c(e)\geq 0}$ is the cost of each graph edit operation ${\displaystyle e$$}$.

기본 그래프 편집 연산자 집합에는 일반적으로 다음이 포함된다.

그래프에 라벨이 붙은 새로운 정점 하나를 도입하기 위한 정점 삽입.

그래프에서 단일(최소 분리) 정점을 제거하기 위한 정점 삭제.

주어진 정점의 라벨(또는 색상)을 변경하기 위한 정점 치환.

한 쌍의 꼭지점 사이에 새로운 색상의 가장자리를 도입하기 위한 가장자리.

정점 쌍 사이의 단일 에지를 제거하기 위한 에지 삭제.

주어진 가장자리의 레이블(또는 색상)을 변경하기 위한 가장자리 대체.

추가적이지만 덜 일반적인 연산자에는 에지에 새로운 정점을 도입하는 에지 분할(또한 새로운 에지 생성), 에지 사이의 2도 정점을 제거하는 에지 수축(동일한 색상의) 등의 연산이 포함된다. 이러한 복잡한 편집 연산자는 더 많은 기본적인 변환의 관점에서 정의될 수 있지만, 그 사용으로 연산자가 구성 요소의 합계보다 더 저렴한 경우$$ $비용{\displaystyle }$ 함수 c ${\displaystyle c}$의 매개변수를 더 정밀하게 정의할 수 있다.

기본 그래프 편집 연산자에 대한 심층 분석은 다음과 같다.

그리고 이러한 기본적인 그래프 편집 연산자를 자동으로 추론하는 몇 가지 방법이 제시되었다.^{[13][14][15][16][17]} 일부 알고리즘은 이러한 비용을 온라인에서 학습한다.

적용들

그래프 편집 거리는 필기 인식,^[19] 지문 인식^[20] 및 척수학에서 응용 프로그램을 찾는다.^[21]

알고리즘 및 복잡성

그래프 한 쌍 사이의 그래프 편집 거리를 계산하기 위한 정확한 알고리즘은 일반적으로 문제를 두 그래프 사이의 최소 비용 편집 경로 찾기 중 하나로 변환한다. 최적 편집 경로의 계산은 A* 검색 알고리즘으로 구현되는 경로 찾기 검색 또는 최단 경로 문제로 캐스팅된다.

정확한 알고리즘 외에도 여러 가지 효율적인 근사 알고리즘이 알려져 있다. 그들 중 대부분은 입방체 계산 시간을 가지고 있다.

게다가 GED의 근사치를 선형 시간으로 추론하는 알고리즘이 있다.

위의 알고리즘이 실제로 잘 작동하는 경우도 있지만, 일반적으로 그래프 편집 거리 계산 문제는 NP-하드(온라인에서 사용할 수 있는 증거는 Zeng 등 2절 참조)이며, 심지어 근사치조차 어렵다(형식적으로는 APX-하드^[28]).

참조