전파 커널: 전파된 정보로부터 얻은 효율적인 그래프 커널

우리는 구조화된 데이터 간의 유사도를 효율적으로 측정하기 위한 일반적인 그래프 커널 프레임워크인 전파 커널(Propagation Kernels)을 소개한다. 전파 커널은 주어진 그래프 집합 내에서 정보가 어떻게 확산되는지를 모니터링하는 데 기반을 두고 있다. 이들은 무작위 보행(Random Walk)과 같은 전파 방식의 초기 단계 분포를 활용하여 노드 레이블, 속성, 간선 정보에 포함된 구조적 정보를 포착한다. 이러한 접근은 두 가지 장점을 제공한다. 첫째, 상용화된 전파 방식을 활용함으로써 레이블이 부여된 그래프, 부분적으로 레이블이 부여된 그래프, 레이블이 없는 그래프, 방향성 그래프, 속성 그래프 등 다양한 유형의 그래프에 대해 자연스럽게 커널을 구성할 수 있다. 둘째, 기존에 효율적이고 정보량이 풍부한 전파 방식을 활용함으로써, 예측 성능을 희생하지 않으면서도 최신 기술보다 훨씬 빠른 속도로 커널을 계산할 수 있다. 또한, 다루는 그래프가 규칙적인 구조(예: 이미지나 비디오 데이터를 모델링할 때와 같이)를 가질 경우, 이러한 규칙성을 활용하여 수천 개의 노드를 포함하는 대규모 그래프 데이터베이스에서도 커널 계산을 효율적으로 확장할 수 있음을 보여줄 것이다. 본 연구의 기여를 뒷받침하기 위해 다양한 응용 분야에서 나온 실제 그래프 데이터셋을 대상으로 철저한 실험을 수행하였다.