Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks

본 문서에서는 데이터 마이닝 분야의 ICDM 2017 학회에서 발표된 Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다.

  • Title: Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks
  • Authors: Jaemin Yoo, Saehan Jo, and U Kang
  • Conference: IEEE International Conference on Data Mining (ICDM) 2017

Node Classification

정점 분류(node classification)는 그래프 내의 각 정점(node)을 분류하는 문제입니다. 예를 들어 넷플릭스 같은 스트리밍 서비스에서 그림 1과 같이 사용자들이 컨텐츠를 소비한 내역을 그래프로 모델링한 다음 영화나 드라마를 분류하는 작업 등을 생각해볼 수 있습니다. 최근에 그래프 신경망에 대한 연구가 활발히 이루어지면서 함께 주목을 받고 있는 문제이기도 한데, 데이터간 관계가 그래프 형태로 주어져 있는 경우 정점 분류를 통해 학습 데이터가 부족한 반지도 학습(semi-supervised learning) 상황을 해결할 수 있기 때문입니다.

그림 1. 스트리밍 서비스에서 사용자와 컨텐츠간 관계를 나타내는 그래프.

만약 그래프의 각 정점이 고유한 피처 벡터를 가지고 있다면 그래프는 피처간 관계를 나타내는 보조적인 정보로서 사용됩니다. 이런 경우에는 각 정점의 피처 벡터와 그래프 구조를 동시에 고려하여 그 관계를 학습하는 것이 중요합니다. 반면, 본 논문에서는 피처 벡터가 주어지지 않고 그래프 구조 및 간선 정보가 정점 분류를 위한 유일한 정보라고 가정합니다. 따라서, 정점 피처를 인위적으로 생성해야 하는 그래프 신경망 모델을 바로 적용하기 어렵고, 그래프 구조를 최대한 활용하여 관측된 정점의 정보를 그래프 전체로 전파해야 합니다.

Loopy Belief Propagation

신뢰 전파(loopy belief propagation) 알고리즘은 위와 같은 상황에서 정점 분류 문제를 풀 수 있는 방법입니다. 원래는 확률 그래프 모델에서 각 변수의 주변 분포(marginal distribution)를 계산하기 위해 제안된 알고리즘이지만, 몇 개의 파라미터만으로도 일부 정점의 정보를 효과적으로 전파할 수 있다는 것이 알려져 있습니다. 특히, 그래프 간선 수에 선형적인 시간 복잡도 때문에 대용량 그래프에 널리 사용되어 왔습니다. 

신뢰 전파 알고리즘은 주어진 그래프를 마코프 망(Markov network)으로 모델링함으로써 동작합니다. 먼저, 관측된 정보를 각 정점의 사전 분포로 반영한 다음, 간선 포텐셜(edge potential) 함수를 통해 인접한 정점이 동일한 라벨을 갖을 확률이 높다는 가정을 모델에 반영합니다. 그런 다음, 모든 정점에 대한 신뢰도(belief)가 수렴할 때까지 메시지 전파를 반복합니다. 여기서 간선 포텐셜 함수는 주어진 그래프에서 인접한 정점이 얼마만큼 관련되어 있는지, 즉 메시지 전파가 얼마나 잘 일어나는지 결정하는 중요한 인자로 작용합니다.

하지만, 기존 연구에서는 신뢰 전파 알고리즘의 포텐셜 함수를 임의로 정했기 때문에 이에 따라 알고리즘의 성능이 크게 좌우되는 문제가 있었습니다. 또한, 그래프 간선에 부호(sign)나 점수(rating) 등이 있어 모든 간선이 동일한 포텐셜 함수를 갖지 않는 경우, 간선 형태별로 다른 포텐셜 함수를 모델링하는 것이 현실적으로 어렵다는 문제도 있었습니다. 본 논문에서는 관측된 정점을 이용하여 포텐셜 함수를 학습하고, 기존 신뢰 전파 알고리즘의 성능을 향상시키는 Supervised Belief Propagation (SBP)를 제안합니다.

Supervised Belief Propagation

본 논문에서 제안하는 Supervised Belief Propagation (SBP)은 지도 학습을 통해 기존 신뢰 전파 알고리즘의 포텐셜 함수를 학습하는 알고리즘입니다. 특히, 간선마다 피처 벡터가 주어져 있어 각 간선에 대한 포텐셜 함수를 임의로 정하기 어려운 상황에서 효과적으로 동작합니다. SBP는 propagation과 update의 두 단계로 구성되어 있으며, 각각 관측된 정점의 라벨 정보를 그래프 전체로 전파하여 신뢰도를 계산하는 역할과 전파된 신뢰도를 기반으로 모델의 가중치(weight) 벡터를 업데이트하는 역할을 수행합니다.

Propagation 단계에서 수행하는 일은 일반적인 신뢰 전파 알고리즘에서와 거의 같습니다. 즉, 관측된 정점의 정보를 메시지 전파를 통해 그래프 전체로 전달합니다. 하지만, 기존 알고리즘에서 포텐셜 함수 내의 전파도 파라미터를 상수로 고정한 것과 달리, SBP에서는 각 간선의 피처 벡터와 학습 가능한 가중치 벡터의 결합 함수로 전파도 파라미터를 모델링합니다. 그 결과, 가중치 벡터가 업데이트되면서 propagation 결과도 달라지게 되고, 각 간선의 형태나 특징에 따라 적절한 포텐셜 함수를 찾게 됩니다.

Update 단계에서는 목적 함수를 최소화하는 방향으로 가중치 벡터를 업데이트합니다. 이때, 목적 함수로는 최근에 많이 사용되는 교차 엔트로피 함수 대신에 AUC(area under the ROC curve) 값을 근사하는 랭킹 함수를 사용합니다. 그 이유는 전체 정점의 수에 비해 학습에 직접 사용할 수 있는 관측된 정점의 수가 적기 때문에, 문제를 단순 이진 분류가 아니라 랭킹 문제로 취급함으로써 더 좋은 가중치 벡터를 찾을 수 있기 때문입니다. 즉, 예측 확률이 50%를 넘는지의 여부보다는 클래스간 랭킹을 잘 보존하는지를 중시합니다.

Experiments

본 논문은 SBP가 정점 분류 문제에서 기존 알고리즘에 비해 더 높은 정확도를 달성한다는 것을 실험을 통해 보입니다. 그림 2는 세 가지 데이터에서 SBP와 기존 알고리즘을 비교하는데, SBP가 일관성 있게 가장 좋은 성능을 보이고 있습니다. MovieLens와 Epinions-R에서는 각 간선에 점수(rating) 정보가 주어진 것에 비해 Epinions-S에서는 각 간선에 부호(sign) 정보가 주어져 있기 때문에 사용된 경쟁 상대가 조금 다르지만, SBP는 간선 피처의 종류에 상관 없이 세 데이터 모두에서 포텐셜 함수를 잘 학습하게 됩니다.

그림 2. 세 개의 데이터셋에서 SBP와 기존 알고리즘의 정점 분류 정확도 비교.

그림 3은 그래프의 간선 수에 따른 SBP의 수행 시간을 나타냅니다. 신뢰 전파 알고리즘의 중요한 장점 중 하나는 확장성(scalability)으로, 이는 알고리즘의 동작 시간이 그래프의 간선 수에 선형적으로 비례하는 특징을 나타냅니다. 본 논문은 SBP가 지도학습을 포함하는 복잡한 알고리즘임에도 기존 신뢰 전파 알고리즘과 마찬가지로 선형적인 시간 복잡도를 가진다는 것을 보여줍니다. 따라서, SBP는 대용량 그래프에서도 무리 없이 사용될 수 있으며, 정점 분류 문제에서 기존의 신뢰 전파 알고리즘을 대체할 수 있습니다.

그림 3. 그래프의 간선 수에 따른 SBP의 동작 시간.

Conclusion

본 문서에서는 ICDM 2017에서 발표된 Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks 논문을 소개하였습니다. 해당 논문은 간선에 피처 벡터가 주어진 그래프에서 효과적인 정점 분류를 수행하기 위한 SBP(Supervised Belief Propagation) 알고리즘을 제안하였습니다. 또한, 실험 결과 SBP가 기존 방법보다 정점 분류 문제에서 더 높은 분류 정확도를 보인다는 것을 보였습니다.

간선에 피처 벡터가 주어져 있고 이 피처 벡터에 따라 정점간 관계가 달라질 것으로 기대되는 경우 단순히 인접 정점이 비슷한 특성을 가질 것이라고 가정하는 메시지 전파 방식은 좋은 성능을 내기 어렵습니다. 예를 들어, 글의 앞 부분에서 제시한 예시처럼 사용자-상품의 리뷰 그래프가 주어져 있을 경우, 5점 리뷰와 1점 리뷰 사이에는 메시지 전파 방식과 전파되는 정보의 양에 분명한 차이가 존재합니다. 본 논문에서 제시하는 SBP 알고리즘은 이 같은 상황에서 각 리뷰 점수에 따른 메시지 전파 방식을 학습하고, 상품 추천이나 부정 사용자 탐지 문제 등의 문제를 잘 해결할 수 있습니다. 자세한 내용은 논문 홈페이지에서 확인하실 수 있습니다.