박근수 교수 연구진,
그래프 동형 문제에 대한 세계 최고 성능 알고리즘 기술 개발

박근수 교수 연구진이 세계 최고 성능의 그래프 동형(Graph Isomorphism) 알고리즘 기술을 개발하였다. 그래프 동형 문제는 두 개의 그래프가 동형인지 판별하는 문제로 소셜 네트워크 서비스, 생물정보학, 화학정보학 등 다양한 응용 분야에서 그래프 분석을 위해 다루고 있는 핵심 문제이다. Garey & Johnson은 1979년에 NP-complete에 속하는지 혹은 P에 속하는지 알려지지 않은 12개의 미해결 문제를 소개하였는데, 그중에서 그래프 동형 문제는 40년이 지난 현재까지도 미해결 상태로 남아있는 유명한 문제이다.

실용적인 측면에서는 지난 30여 년 동안 nauty/Traces가 그래프 동형 문제를 푸는 가장 빠른 알고리즘으로 알려져 왔다. 박근수 교수 연구진은 그래프 동형 문제를 실제 데이터에서 빠르게 푸는 세계 최고 성능의 알고리즘을 개발하고, 개발한 알고리즘이 benchmark 그래프 데이터에서 nauty/Traces보다 평균 수천 배 빠르게 문제를 푸는 것을 보였다.

개발된 그래프 동형 알고리즘은 공개 SW로 배포되었으며, 이 내용으로 박근수 교수의 지도학생인 구건모, 남예현이 과학기술정보통신부에서 주최한 2020 공개SW 개발자대회에서 금상을 수상하였다.

박근수 교수 연구진의 그래프 동형 알고리즘에 관한 연구 결과는 ICDE 2021에 accept 되었으며, 2021년 4월에 열리는 ICDE 2021에서 발표될 예정이다.

G. Gu, Y. Nam, K. Park, Z. Galil, G.F. Italiano, and W.-S. Han, Scalable Graph Isomorphism: Combining Pairwise Color Refinement and Backtracking via Compressed Candidate Space, International Conference on Data Engineering (ICDE) 2021.