An Effective Graph Edit Distance Model Using Node Mapping Information
J. H. Lee, Jongik Kim · Journal of KIISE · 2025
그래프 편집 거리(GED, Graph Edit Distance)는 그래프 사이의 유사도를 정량화하기 위한 가장 대표적인 방법이다. 그러나 정확한 GED 계산은 NP-Hard 문제로 많은 계산 비용을 필요로 한다. 따라서 최근 GED 근삿값을 예측하는 많은 딥러닝 모델들이 제안되었다. 하지만 기존 모델들은 상대 그래프와의 연관 관계를 부분적으로 고려함에 따라 근삿값의 오차가 크고, 노드 매칭 정보를 고려하지 않아 예측한 근삿값에 대한 설명력이 부족한 문제가 있다. 본 논문에서는 두 그래프의 노드 레벨 임베딩을 통해 사상 행렬을 학습하여 GED 근삿값의 설명력을 제공하며 학습 과정에서의 정보 손실을 최소화 하여 보다 정확한 GED를 예측하는 모델을 제안한다. 실험을 통해 제안한 모델이 기존 모델들보다 더 정확하게 GED를 예측하는 것을 보인다.