SimGNN: 신경망 접근법을 이용한 빠른 그래프 유사도 계산

그래프 유사성 검색은 가장 중요한 그래프 기반 응용 프로그램 중 하나로, 예를 들어 쿼리 화합물과 가장 유사한 화학 물질을 찾는 것 등이 포함됩니다. 그래프 유사성 계산, 예를 들어 그래프 편집 거리(Graph Edit Distance, GED)와 최대 공통 부분 그래프(Maximum Common Subgraph, MCS)는 그래프 유사성 검색과 여러 다른 응용 프로그램의 핵심 연산이지만, 실제로 계산하는 데 매우 비용이 많이 듭니다. 최근 노드 또는 그래프 분류와 같은 여러 그래프 응용 프로그램에서 신경망 접근 방식의 성공에 영감을 받아, 우리는 이 고전적이면서도 도전적인 그래프 문제를 해결하기 위한 새로운 신경망 기반 접근 방식을 제안합니다. 이 접근 방식은 계산 부담을 줄이면서도 좋은 성능을 유지하는 것을 목표로 합니다.제안된 접근 방식인 SimGNN은 두 가지 전략을 결합합니다. 첫째, 각 그래프를 벡터로 매핑하는 학습 가능한 임베딩 함수를 설계하여 그래프의 전역 요약 정보를 제공합니다. 특정 유사성 지표에 따라 중요한 노드를 강조하기 위해 새로운 주의 메커니즘(attention mechanism)을 제안합니다. 둘째, 세부적인 노드 수준 정보를 그래프 수준 임베딩에 보완하기 위해 쌍별 노드 비교 방법을 설계합니다. 우리의 모델은 미지의 그래프에 대해 더 나은 일반화 능력을 보여주며, 두 개의 그래프 내 노드 수에 대한 최악의 경우에도 이차 시간 복잡도(quadratic time complexity)로 실행됩니다.GED 계산을 예로 들면, 세 개의 실제 그래프 데이터셋에 대한 실험 결과가 우리의 접근 방식의 효과성과 효율성을 입증합니다. 특히, 우리의 모델은 GED 계산에 대한 몇 가지 근사 알고리즘과 많은 기존 그래프 신경망 기반 모델들을 포함한 일련의 베이스라인들과 비교하여 더 낮은 오류율과 큰 시간 단축을 달성했습니다. 우리 연구팀이 아는 한, 우리는 신경망을 사용하여 두 개의 그래프 사이의 유사성을 명시적으로 모델링하는 최초의 연구 그룹 중 하나이며, 이는 향후 그래프 유사성 계산 및 검색에 관한 연구의 새로운 방향성을 제시하고 있습니다.