KAIST 김민수 교수팀, 그래프 데이터 기반 알고리즘 연구에 획기적 돌파구 마련

PC 1대로 1조개 규모의 그래프 알고리즘 계산 가능해져

기존 대비 10,000배 효율.. 산업 파급효과 매우 클 전망

KAIST 전산학부 김민수 교수, 워털루 대학 박힘찬 박사

그래프 타입의 데이터를 실제로 저장하지 않고도 알고리즘을 계산할 수 있는 ‘그래프 프로세싱 시뮬레이션’ 신기술이 세계 최초로 개발됐다.

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

이 기술은 데이터 저장이 필요없어 1조개 간선의 초대규모 그래프도 PC 한 대로 처리가 가능한 것으로 알려졌다. 교신저자로 참여한 김민수 교수는 "오늘날 거의 모든 IT 분야에서 그래프 데이터를 활용하고 있는바, 연구팀이 개발한 새로운 기술은 그래프 알고리즘의 개발 규모와 효율을 획기적으로 높일 수 있어 산업적 측면에서 파급 효과가 매우 클 것으로 기대한다ˮ 라고 말했다.

이번 연구는 한국연구재단 선도연구센터 사업 및 중견연구자지원사업, 과기정통부 IITP SW스타랩 사업의 지원을 받아 수행된 것으로, 김민수 교수의 제자이자 캐나다 워털루 대학에 박사후 연구원으로 재직 중인 박힘찬 박사가 제1 저자로, 김 교수가 교신저자로 참여했다.

연구 결과는 지난 22일 그리스 차니아에서 온라인으로 열린 데이터베이스 분야 최고 국제학술대회 중 하나인 IEEE ICDE에서 발표됐다.

그래프 데이터 규모 문제에 주목.. T-GPS 기술 개발

오늘날 웹, SNS, 인공지능, 블록체인 등의 광범위한 분야들에서 그래프 타입의 데이터에 대한 다양한 알고리즘들의 연구가 매우 중요하다.

그래프 데이터와 그에 대한 알고리즘 계산이 광범위하게 사용되기 때문에 지난 수 십 년 동안 수 많은 그래프 알고리즘들이 연구되어 왔고, 지금도 인공지능 챗봇(chatbot)과 같은 최신 애플리케이션들을 위한 다양한 그래프 알고리즘들이 개발되고 있다. 그러나, 그래프 데이터의 규모가 점점 증가하면서 새로운 그래프 알고리즘, 또는 그래프 기반 애플리케이션을 개발하고 테스트하는데 점점 더 많은 컴퓨팅 자원과 시간이 소요되고 있다. 웹, SNS, IoT 응용들에서 수집되는 그래프 데이터는 그 규모가 수 십 내지 수 백 억 간선 규모 이상이 되며, 인공지능, 또는 사람의 뇌 신경망 데이터는 그 규모가 수 천 억 내지 1조 간선 규모 이상이 된다.

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

종래의 2단계 방식 기술 개념도

T-GPS 기술, 자원 대비 10,000배 더 큰 규모 데이터 처리 가능해

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

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

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

연구팀은 “그래프 데이터상에서 그래프 알고리즘이 계산을 위해 접근하는 부분을 짧은 순간 동안 실시간으로 생성해, 마치 그래프 데이터가 존재하는 것처럼 알고리즘을 계산하는 것이다. 이때 그래프 데이터를 아무렇게 실시간 생성하는 것이 아니라 합성 그래프 모델에 따라 생성하고 저장한 것과 동일하도록 실시간 생성하는 것이 핵심 기술 중 하나다”라고 말했다.

또한, 그래프 처리 엔진이 실시간으로 생성되는 그래프를 실제 그래프처럼 인식하고 알고리즘을 완전히 동일하게 계산하도록 엔진을 수정한 것이 또 다른 핵심 기술이다.

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

게임 및 가상 현실 소프트웨어서 활용 가능

구글, 페이스북, 네이버, 카카오와 같은 IT 대기업들 뿐만 아니라 중소 및 벤처 기업들에서 그래프 데이터 기반의 서비스를 개발할 때, 저비용으로 빠르게 서비스 개발을 완료할 수 있다. 특히 중소 및 벤처 기업들은 서비스에 사용되는 그래프 데이터가 매우 커질 때 현재의 알고리즘이 어떤 성능상의 문제를 가질지, 어떤 다른 알고리즘을 사용해야 그 문제를 해결할 수 있을지 미리 알기 어렵다.

연구팀은 “T-GPS 기술을 사용하면, 초기 서비스에서 확보된 매우 소규모의 그래프 데이터와 서비스 중인 알고리즘을 입력으로 넣어주고 시뮬레이션 함으로써, 서비스 운영에 따른 그래프 데이터가 증가할 때 현재 알고리즘이 어떤 성능을 낼지 PC 1대만으로도 매우 쉽게 정확히 계산할 수 있다”며 “만약 성능이 좋지 않다면 다른 후보 알고리즘을 try-and-error 방식으로 빠르게 찾을 수 있다. 뿐만 아니라 게임 및 가상 현실 소프트웨어에서 실제 초대규모 그래프 데이터를 저장하지 않고, 참여자가 접근하는 데이터 부분만 가시화하거나, 반응을 계산하는 기술에도 적용될 수 있다”고 전했다.