본 문서에서는 데이터 마이닝 분야의 ICDM 2016 학회에서 발표된 Personalized Ranking in Signed Networks using Signed Random Walk with Restart 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다.
- Title: Personalized Ranking in Signed Networks using Signed Random Walk with Restart
- Authors: Jinhong Jung et al.
- Conference: IEEE International Conference on Data Mining (ICDM) 2016
Personalized Ranking in Signed Network
부호화된 네트워크(signed network)는 노드(node) 간의 신뢰 관계를 + (positive, 신뢰) 또는 - (negative, 불신뢰)의 부호가 붙은 간선(edge)로 표현하는 네트워크를 말하며, 이 네트워크가 가장 많이 사용되는 분야로는 각 유저들간의 관계가 신뢰/불신뢰로 이루어진 소셜 네트워크가 있습니다. 부호화된 네트워크에서는 어떠한 유저와 다른 유저들간의 신뢰 정도 혹은 불신뢰 정도의 순위(rank)를 매겨 유저간의 신뢰도를 표현할 수 있는데, 이는 간선 부호 예측(link sign prediction), 연결 예측(link prediction), 집단 탐지(community detection) 등의 문제를 푸는 데에 사용될 수 있습니다. 본 논문에서는 각 노드별로 다른 노드들과의 신뢰 정도 혹은 불신뢰 정도의 순위를 매기는 방법인 개인화된 신뢰도 랭킹(personalized trust ranking) 방법을 통해 간선 부호 예측 문제를 풉니다. |
| 그림 1. 부호화된 네트워크 예시 |
Signed Random Walk with Restart (SRWR)
개인화된 신뢰도 랭킹을 계산하는 방법에는 여러 방법이 있는데, 본 논문에서는 랜덤 워크(random walk)를 기반으로 한 방법을 소개합니다. 랜덤 워크 방법은 그래프 상에서 연결된 노드들을 임의로 걸어다니는 랜덤 서퍼(random suffer)의 이동 경로를 통해 노드 신뢰도 랭킹을 계산하는 방법입니다. 개인화된 랜덤 워크(personalized random walk)에서는 랜덤 서퍼가 일정한 확률로 출발 노드로 돌아가는데, 이를 통해 출발 노드에 집중된 이동 경로를 얻어 출발 노드에 개인화된 노드 신뢰도 랭킹을 구할 수 있습니다. 간단한 예시로 노드 a에서 출발한 랜덤 서퍼가 랜덤 워크 후에 노트 b에 있을 확률이 제일 높다면, 노드 b는 노드 a에 대해 가장 높은 신뢰도 랭킹을 갖게 됩니다. 그러나 기존의 개인화된 랜덤 워크 방법은 모든 간선을 + 부호를 가지는 신뢰 간선(positive edge)로 가정하므로, 노드간에 복잡한 관계가 존재하는 부호화된 네트워크에서는 사용되기 어렵습니다.부호화된 네트워크에서 노드간의 관계는 균형 이론(Balance theory)을 통해 표현될 수 있습니다. 균형 이론에 따르면 1) 친구의 친구는 친구, 2) 친구의 적은 적, 3) 적의 친구는 적, 4) 적의 적은 친구 입니다. 이 때 + 부호 간선을 친구 관계, - 부호 간선을 적 관계로 생각하면, 부호화된 네트워크에서 떨어져 있는 노드간의 관계를 예측할 수 있습니다. 본 논문의 저자는 균형 이론에 착안하여, 부호화된 네트워크에서 동작하는 개인화된 랜덤 워크 기반의 노드 신뢰도 랭킹 모델인 Signed Random Walk with Restart (SRWR) 모델을 제안합니다.
 |
| 그림 2. 기존 랜덤 워크 방법과 부호화된 랜덤 워크 방법. |
부호화된 랜덤 워크(signed random walk)는 부호화된 랜덤 서퍼(signed random suffer)를 통해 이루어지는데, 핵심 아이디어는 부호화된 랜덤 서퍼가 - 부호 간선을 만날 경우 서퍼의 부호를 바꾸는 것입니다(그림 2(b)). 부호화된 랜덤 워크가 끝난 후에는 각 노드마다 + 부호 랜덤 서퍼가 존재할 확률과 - 부호 랜덤 서퍼가 존재할 확률이 각각 존재하게 됩니다. 이 때 + 부호 랜덤 서퍼가 존재할 확률이 높으면 해당 노드는 출발 노드에게 높은 신뢰를 받고 있고, - 부호 랜덤 서퍼가 존재할 확률이 높으면 해당 노드는 출발 노드에게 신뢰를 못 받고 있다고 해석할 수 있습니다. 그림 2(b)에 따르면 부호화된 랜덤 워크가 끝난 이후에 + 부호 랜덤 서퍼가 존재할 확률은 1) + 부호 랜덤 서퍼가 + 부호 간선을 통해 방문하는 확률과 2) - 부호 랜덤 서퍼가 - 부호 간선을 통해 방문하는 확률의 합으로 나타낼 수 있습니다. 이와 비슷하게, 부호화된 랜덤 워크가 끝난 이후에 - 부호 랜덤 서퍼가 존재할 확률은 1) + 부호 랜덤 서퍼가 - 부호 간선을 통해 방문하는 확률과 2) - 부호 랜덤 서퍼가 + 부호 간선을 통해 방문하는 확률의 합으로 나타낼 수 있습니다. 추가로 본 논문에서는 개인화된 신뢰도 랭킹을 계산하기 위해 일반 랜덤 워크가 아닌 개인화된 랜덤 워크를 사용합니다. 즉, 부호화된 랜덤 서퍼는 일정한 확률로 출발 노드로 돌아가는데, 이 때 출발 노드는 항상 신뢰할 수 있으므로 출발 노드로 돌아갈 때는 랜덤 서퍼의 부호를 + 로 설정합니다. 특정 출발 노드에서 출발한 부호화된 랜덤 서퍼가 랜덤 워크를 끝낸 후에 각 노드별로 + 부호 랜덤 서퍼로 존재할 확률과 - 부호 랜덤 서퍼로 존재할 확률을 업데이트하는 자세한 수식은 논문을 통해 확인할 수 있습니다.
Balance Attenuation Factors
본 논문이 제안한 부호화된 랜덤 서퍼는 그림 2(b)와 같이 균형 이론의 4가지 경우에 대해 크게 의존합니다. 그러나 현실에서는 내 친구의 적이 친구일 수 있는 것처럼 균형 이론에 정확하게 부합하지 않는 경우가 있습니다. 따라서 저자는 추가적으로 균형 감쇠 요소(balance attenuation factor)를 도입하여 균형 이론의 불확실성을 보완합니다. 균형 감쇠 요소가 추가된 부호화된 랜덤 서퍼는 1) 내 적의 적은 적이다, 2) 내 친구의 적은 친구이다 와 같이 균형 이론에 따르면 불가능하지만 현실에서는 가능할 법한 상황을 반영할 수 있습니다.Experiments
본 논문에서는 SRWR 모델이 간선 부호 예측 문제에서 가장 높은 성능을 보이는 것을 실험을 통해 보입니다. 간선 부호를 예측하기 위해서는 SRWR을 통해 얻은 개인화된 랭킹이 사용됩니다. 예를 들어 노드 a에서 b로 가는 간선의 부호를 예측할 때는, 먼저 노드 a에서 부호화되고 개인화된 랜덤 워크(signed random walk with restart)를 진행합니다. 노드 a에서의 랜덤 워크가 끝난 후에는 노드 b에 + 부호 랜덤 서퍼가 존재할 확률과 - 부호 랜덤 서퍼가 존재할 확률을 구할 수 있습니다. 이 때, 이 두 확률의 차가 0보다 크면 간선의 부호를 +, 0보다 작으면 - 로 예측합니다.
 |
| 그림 3. 세 개의 데이터셋에서 SRWR과 기존 알고리즘의 간선 부호 예측 정확도 비교 |
그림 3은 세 가지 데이터에서 SRWR과 기존 알고리즘을 비교하는데, SRWR이 일관성 있게 가장 높은 정확도를 보이고 있습니다. 이는 SRWR이 기존 방법들보다 더 효과적인 개인화된 랭킹을 제공한다고 해석할 수 있습니다.
Conclusion
본 문서에서는 ICDM 2016에서 발표된 Personalized Ranking in Signed Networks using Signed Random Walk with Restart 논문을 소개하였습니다. 해당 논문은 부호화된 네트워크에서 개인화된 신뢰도 랭킹을 구하는 랜덤 워크 기반의 SRWR (Signed Random Walk with Restart)을 제안하였습니다. 또한, 실험을 통해 SRWR이 기존 방법보다 간선 부호 예측 문제에서 더 높은 분류 정확도를 보인다는 것을 보였습니다. 부호화된 네트워크에서 개인화된 신뢰도를 구하는 기법은 페이스북, 인스타그램과 같은 소셜 네트워크에서 내가 좋아할 만한 게시글을 분류하거나 아마존, 이베이와 같은 온라인 쇼핑몰에서 소비자가 좋아할 만한 물건을 추천할 때 유용하게 사용될 수 있습니다. 본 논문이 제안한 SRWR 기법은 기존의 랜덤 워크 기법을 부호화된 네트워크에 적용할 때, 노드간의 복잡한 관계를 균형 이론에 근거하여 효율적으로 표현했다는 점에서 의의가 있습니다.