그래프 편집 거리

수학 및 컴퓨터 과학에서 그래프 편집 거리(, GED)는 두 그래프 사이의 유사도(또는 비유사도)를 나타내는 척도이다. 그래프 편집 거리의 개념은 1983년 알베르토 산펠리우(Alberto Sanfeliu)와 킹선 푸(King-Sun Fu)에 의해 처음으로 수학적으로 공식화되었다. 그래프 편집 거리의 주요 응용 분야는 기계 학습에서의 오류 허용 패턴 인식과 같은 비정밀 그래프 매칭(inexact graph matching)이다.

두 그래프 사이의 그래프 편집 거리는 문자열 사이의 문자열 편집 거리와 관련이 있다. 문자열을 최대 차수가 1인 연결된 유향 비순환 그래프로 해석하면, 레벤슈타인 거리, 해밍 거리, 자로-윈클러 거리와 같은 전통적인 편집 거리의 정의들은 적절하게 제약된 그래프들 사이의 그래프 편집 거리로 해석될 수 있다. 마찬가지로, 그래프 편집 거리는 유근 수형도 사이의 트리 편집 거리(tree edit distance)를 일반화한 것이다.

 형식적 정의 및 속성 
그래프 편집 거리의 수학적 정의는 정의되는 대상 그래프의 유형, 즉 정점과 간선에 레이블이 있는지 여부와 방법, 그리고 간선이 유향 그래프인지 여부에 따라 달라진다. 일반적으로 그래프 편집 연산(기초 그래프 연산으로도 알려짐)의 집합이 주어졌을 때, 두 그래프 과  사이의 그래프 편집 거리 는 다음과 같이 정의될 수 있다.

여기서 는 을 와 (동형인 그래프로) 변환하는 편집 경로의 집합을 나타내며, 는 각 그래프 편집 연산 의 비용이다.

기초 그래프 편집 연산의 집합은 일반적으로 다음을 포함한다:

정점 삽입(vertex insertion): 그래프에 레이블이 지정된 단일 새 정점을 도입함.
정점 삭제(vertex deletion): 그래프에서 단일(주로 연결되지 않은) 정점을 제거함.
정점 치환(vertex substitution): 주어진 정점의 레이블(또는 색상)을 변경함.
간선 삽입(edge insertion): 한 쌍의 정점 사이에 색상이 지정된 새로운 간선을 도입함.
간선 삭제(edge deletion): 한 쌍의 정점 사이의 단일 간선을 제거함.
간선 치환(edge substitution): 주어진 간선의 레이블(또는 색상)을 변경함.

흔하지는 않지만 추가적인 연산으로는 간선에 새 정점을 도입하는(새로운 간선도 생성되는) 간선 분할(edge splitting)과 동일한 색상의 간선 사이에 있는 차수가 2인 정점을 제거하는 간선 축약(edge contraction) 등이 있다. 이러한 복잡한 편집 연산은 더 기초적인 변환들로 정의될 수 있지만, 해당 연산의 비용이 구성 요소들의 합보다 저렴한 경우 비용 함수 의 더 세밀한 매개변수화가 가능해진다.

기초 그래프 편집 연산에 대한 심층적인 분석은 다음 연구들에 제시되어 있다.

또한 이러한 기초 그래프 편집 연산을 자동으로 유도하는 몇 가지 방법이 제시되었다. 일부 알고리즘은 이러한 비용을 온라인으로 학습한다.

 응용 
그래프 편집 거리는 필기 인식, 지문 인식, 그리고 화학정보학 분야에서 응용된다.

 알고리즘 및 복잡도 
한 쌍의 그래프 사이의 그래프 편집 거리를 계산하는 정밀 알고리즘은 일반적으로 이 문제를 두 그래프 사이의 최소 비용 편집 경로를 찾는 문제로 변환한다. 최적의 편집 경로 계산은 경로 탐색 또는 최단 경로 문제로 간주되며, 종종 A* 알고리즘으로 구현된다.

정밀 알고리즘 외에도 여러 효율적인 근사 알고리즘이 알려져 있다. 이들 중 대부분은 3차 시간 복잡도(cubic computational time)를 갖지만; 적어도 하나의 알고리즘은 실행 시간이 노드 수에 대해 선형적이면서 노드 차수에 대해서는 3차 시간을 유지한다.

위의 알고리즘들이 때때로 실제 상황에서 잘 작동함에도 불구하고 일반적으로 그래프 편집 거리를 계산하는 문제는 NP-어렵다(온라인에서 확인 가능한 증명은 젱 등(Zeng et al.)의 섹션 2 참조). 또한 근사하는 것조차 어렵다(공식적으로는 APX-어렵다).

 각주 

분류:그래프 이론
분류:그래프 알고리즘
분류:그래프 이론의 계산 문제
분류:거리