KAIST 김민수 교수 그래프 데이터 분야 신기원

국내 연구진이 정보통신(IT) 분야에서 광범위하게 사용하는 그래프 타입의 데이터를 실제로 저장하지 않고도 알고리즘을 계산할 수 있는 '그래프 프로세싱 시뮬레이션'이라는 신개념 기술을 세계 최초로 개발하는 데 성공했다. 데이터를 저장할 필요가 없어 1조 개 간선(間線,edge)의 초대규모 그래프도 PC 한 대로 처리가 가능하다.

KAIST(총장 이광형)는 전산학부 김민수 교수 연구팀이 1조 개 간선의 초대규모 그래프에 대해 데이터 저장 없이 알고리즘을 계산할 수 있는 신개념 기술을 세계 최초로 개발했다고 23일 밝혔다.

김 교수는 KAIST에서 전산학으로 학사, 석사, 박사 학위를 받았고 미국 엔비디아 GPU리서치 센터장과 미국 IBM 알라마덴 리서치센터 연구원 등을 지냈다. 지난해부터 KAIST 전산학부 영년직 부교수로 일하고 있다.

그래프 데이터는 웹 페이지 검색, 소셜 네트워크 서비스(SNS), 추천 시스템, 인공지능, 가상화폐 등 여러 분야에서 핵심적으로 사용하는 데이터다. 정점(vertex)과 간선(edge)으로 이뤄진 데이터로 간선은 두 정점 사이를 연결한다.

현재 많은 IT 기술은 그래프 데이터에 대한 알고리즘 계산을 통해 이뤄지고 있다. 예를들어 웹 페이지를 정점, 웹 페이지의 링크를 간선으로 모델링해 페이지랭크(PageRank)라는 그래프 알고리즘을 수행하면, 웹 페이지들 간 중요 순위를 계산할 수 있다. 구글의 웹 검색 시스템은 이렇게 계산한 결과를 바탕으로 중요 순위의 웹 페이지들부터 검색 결과로 보여준다.

SNS 상에서 잠재적 친구를 추천하거나, 온라인 쇼핑에서 관심 상품을 추천하거나, 지식 기반 (Knowledge Base)의 인공지능 기술은 모두 그래프 데이터에 대한 특정 알고리즘을 수행함으로써 이뤄진다.

하지만 그래프 데이터는 복잡성으로 그 크기가 커질 때 막대한 규모 컴퓨터 클러스터가 있어야만 알고리즘 계산이 가능하다는 문제가 있다.

김 교수 연구팀은 이를 근본적으로 해결하는 'T-GPS(Trillion-scale Graph Processing Simulation)'라는 기술을 개발했다. 'T-GPS' 기술은 그래프 데이터를 실제로 디스크에 저장하지 않고도 마치 그래프 데이터가 저장돼 있는 것처럼 알고리즘을 계산할 수 있고, 계산 결과도 실제 저장한 그래프에 대한 알고리즘 계산과 완전히 동일하다고 KAIST는 설명했다.

그래프 알고리즘은 그래프 처리 엔진 상에서 개발하고 실행한다. 이는 산업적으로 널리 사용되는 SQL 질의를 데이터베이스관리시스템(DBMS) 엔진 상에서 개발하고 실행하는 것과 유사한 방식이다.

지금까지는 그래프 알고리즘을 개발하기 위해 먼저 합성 그래프를 생성 및 저장한 후, 이를 다시 그래프 처리 엔진에서 메모리로 적재해 알고리즘을 계산하는 2단계 방법을 사용했다. 하지만 그래프 데이터는 그 복잡성 때문에 전체를 메모리로 적재하는 것이 요구되며, 그래프 규모가 커지면 대규모 컴퓨터 클러스터 장비가 있어야만 알고리즘을 개발하고 실행할 수 있다는 단점이 있다.

김 교수팀은 합성 그래프와 그래프 처리 엔진 분야에서 국제 최고 권위 학술대회에 매년 논문을 발표하는 등 세계 최고 기술력을 보유하고 있다. 이 기술을 바탕으로 기존 2단계 방법의 문제를 해결했다.

그래프 데이터상에서 그래프 알고리즘이 계산을 위해 접근하는 부분을 짧은 순간 실시간으로 생성, 마치 그래프 데이터가 존재하는 것처럼 알고리즘을 계산하는 것이다. 이때 그래프 데이터를 아무렇게 실시간 생성하는 것이 아니라 합성 그래프 모델에 따라 생성하고 저장한 것과 동일하도록 실시간 생성하는 것이 핵심 기술이다. 또, 그래프 처리 엔진이 실시간으로 생성하는 그래프를 실제 그래프처럼 인식하고 알고리즘을 완전히 동일하게 계산하도록 엔진을 수정한 것이 또 다른 핵심 기술이다.

김민수 교수 연구팀은 'T-GPS' 기술을 종래의 2단계 방법과 성능을 비교한 결과, 종래 2단계 방법이 11대의 컴퓨터로 구성된 클러스터에서 10억 개 간선 규모의 그래프를 계산할 수 있었던 반면, T-GPS 기술은 1대의 컴퓨터에서 1조 개 간선 규모의 그래프를 계산, 컴퓨터 자원 대비 기존보다 1만배 더 큰 규모의 데이터를 처리를 할 수 있음을 확인했다. 또, 알고리즘 계산 시간도 최대 43배 더 빠름을 확인했다고 밝혔다.

교신 저자로 참여한 김민수 교수는 "오늘날 거의 모든 IT 분야에서 그래프 데이터를 활용하고 있다"며 "연구팀이 개발한 새로운 기술은 그래프 알고리즘 개발 규모와 효율을 획기적으로 높일 수 있어 산업적 측면에서 파급 효과가 매우 클 것으로 기대한다"고 말했다.