본 문서에서는 PLOS ONE 저널에 게제된 "Signed random walk diffusion for effective representation learning in signed graphs" 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다.
- Title: Signed random walk diffusion for effective representation learning in signed graphs
- Authors: Jinhong Jung, Jaemin Yoo, and U Kang
- Journal: PLOS ONE (2022)
Learning Node Representations on Signed Social Graph
부호화된 사회 연결망이란 정점간의 신뢰 관계를 양 (+, 신뢰) 또는 음 (-, 불신뢰)의 부호가 붙은 간선으로 표현하는 네트워크를 말하며, 실제로 Epinions와 같은 온라인 소셜 서비스에서 각 사용자들이 서로에 대해 표현한 신뢰 관계등이 부호화된 사회 연결망에 해당됩니다. 이러한 부호화된 사회 연결망에서는 정점 간의 신뢰관계 정보를 바탕으로 하여 주어지지 않은 연결 관계를 예측하거나, 연결 관계에서의 신뢰 여부를 예측하거나, 이상현상 탐지를 하는 등 실생활과 연관된 많은 문제를 풀 수 있습니다.
이러한 많은 실생활 응용 문제들을 풀기 위해서는 주로 각 정점들의 표현 (representation)을 학습하는 방식이 많이 채택됩니다. 기존의 연구들은 네트워크 표현 (network embedding)을 학습하거나, Graph Convolutional Network (GCN)을 기반으로 정점들의 표현을 학습하는 것이 일반적이었습니다. 하지만 이러한 기법들은 각각 다음과 같은 한계점들을 가지고 있습니다. 네트워크 표현을 학습하는 기존 연구들의 경우 주어진 테스크에 대해 종단간 학습 (end-to-end learning)이 불가능합니다. 이러한 기법들은 주로 정점들의 신뢰 관계를 바탕으로 학습을 진행한 후에 주어진 테스크에 대한 학습을 진행하게 되는데, 이러한 과정을 통해서는 신뢰 관계와 주어진 테스크를 모두 잘 만족시키는 정점 표현을 얻기 힘듭니다. 다음으로 GCN을 기반으로 하는 기법들의 경우 기본적인 형태의 GCN을 단순히 차용해와서 레이어를 깊게 쌓아 멀리 떨어진 정점들 (multi-hop neighbors) 간의 연결관계를 학습하려 했을 때 정점들의 표현이 비슷해 지는 over-smoothing 현상이 발생하게 됩니다. 이러한 한계점들 때문에 기존 기법들을 이용해서는 부호화된 사회 연결망에서의 정점 표현을 정확하게 학습하기 어렵습니다. 본 논문에서는 이러한 한계점들을 극복하고 멀리 떨어진 정점들 간의 신뢰관계까지도 올바르게 학습할 수 있는 Signed Diffusion Network (SidNet)을 제안힙니다.
Proposed Method (SidNet)
부호화된 사회 연결망에서의 정점들의 표현을 정확하게 학습하기 위해서는 다음과 같은 한계점을 극복해야합니다.
- [C1] 부호화된 신뢰관계 정보를 정확하게 반영할 수 있어야 합니다.
- [C2] 부호화된 신뢰관계 부터 주어진 응용문제까지 종단간 학습 (end-to-end learning)이 가능해야합니다.
- [C3] 멀리 떨어진 노드들 (multi-hop neighbors)에 대한 신뢰관계까지도 반영할 수 있어야 합니다. 특히 이 과정에서 모든 노드들의 표현이 비슷해지는 현상 (over-smoothing)을 방지할 수 있어야 합니다.
본 논문에서 제안하는 Signed Diffusion Network (SidNet)은 다음과 같은 해결책으로 각 한계점을 극복합니다.
- [S1] 각 정점마다 양과 음의 표현들을 가지게 하고, 신뢰 관계에 따라 각기 다른 표현을 전달하게 하여 신뢰 관계 정보를 반영할 수 있도록 하였습니다.
- [S2] SidNet의 마지막 레이어에서 나오는 정점들의 표현을 이용하여 주어진 응용 문제의 목적 함수를 구성할 수 있도록 하여 종단간 학습이 가능합니다.
- [S3] 부호화된 랜덤워크 확산 시에 해당 정점의 표현 (local feature)을 주입하여 먼 거리까지의 확산 과정에서도 정점들의 표현이 구분 가능하도록 하였습니다.
아래 그림은 SidNet의 전체 구조 (a), 각 레이어의 구조 (b), 그리고 부호화된 랜덤워크 확산 방법 (c)을 나타내고 있습니다. 이어지는 내용에서는 이 그림들을 이용하여 좀 더 자세한 설명을 드리도록 하겠습니다.
(a) SidNet의 전체 구조
SidNet에서는 초기 정점들의 표현이 주어지면 연속된 레이어들을 통과하며 정점 표현을 가공하고, 최종적으로 가공된 정점 정보를 응용 문에의 목적함수에 반영 시키며 이를 통해 종단간 학습이 가능하도록 합니다. 각 레이어에서는 사용자가 지정한 횟수 (K) 만큼의 확산이 일어나여 이웃 정점들 간의 정보를 반영한 정점 정보를 얻을 수 있게 됩니다.
(b) 각 레이어 구조
그림 (b)는 각 레이어의 구조를 나타내고 있습니다. SidNet의 레이어 내부에서는 부호화된 신뢰관계를 학습하기 위해 각 정점마다 양과 음의 표현을 각각 두 개씩 가지게 되는데, 이전 레이어에서 전달된 노드 표현을 변형하여 (feature transformation) 해당 레이어의 양의 표현을 만들고, 음의 표현은 임의로 생성하게 됩니다. 이후에 사용자가 지정한 횟수 (K) 만큼의 확산이 일어나게 되고, 마지막 확산 이후의 양과 음의 표현들을 연결한 후에 다시 표현 변형 (feature transformation)을 통해 하나의 정점 표현을 얻을 수 있도록 합니다. 여기서 사용자가 지정한 횟수 (K)는 한 레이어에서 해당 횟수만큼 떨어진 이웃 (K-hop neighbor)의 정보까지도 얻을 수 있는 것을 의미합니다.
(c) 부호화된 랜덤워크 확산 (Signed random walk diffusion)
그림 (c)는 각 레이어에서 K번 일어나는 부호화된 랜덤워크 확산 방법에 대해 나타내고 있습니다. 각 정점은 양과 음의 표현을 가지고 있는데, 부호화된 신뢰 관계를 반영하기 위하여 신뢰 관계에 따라 연결된 노드의 다른 표현을 받아오게 됩니다. 즉, 양의 신뢰 관계로 연결된 경우 이웃 노드의 양의 표현이 해당 노드의 양의 표현에 영향을 주게 되고, 음의 신뢰 관계로 연결된 경우 이웃 노드의 음의 표현이 해당 노드의 양의 표현에 영향을 주게 됩니다. 또한 확산 과정에서 해당 정점의 표현 (local feature)을 주입해줌으로써 확산 과정에서 모든 노드들의 표현이 비슷해지는 현상 (over-smooting)을 방지하게 됩니다.
Experiment
본 논문에서는 SidNet의 효과를 검증하기 위하여 다양한 실험을 진행하였고, 아래 표는 이 중 가장 대표적인 실험 결과인 간선의 신뢰 관계 예측 실험 결과를 나타내고 있습니다. 실험에서는 대표적인 5개의 부호화된 사회 연결망에 대하여 간선의 신뢰 관계를 예측하고, 이에 따른 정확도를 비교하였습니다. SidNet은 앞서 언급한 기존 기법들의 한계점들을 극복함으로써 모든 데이터셋들에서 가장 높은 정확도를 보였습니다.
Conclusion
본 문서에서는 PLOS ONE 저널에 게재된 "Signed random walk diffusion for effective representation learning in signed graphs" 논문에 대해 소개하였습니다. 해당 논문에서는 부호화된 사회 연결망에서의 정점들의 표현을 정확하게 학습하는 방법인 SidNet을 제안하였으며, 실험을 통해 해당 기법이 기존 기법들을 모든 데이터 셋에서 능가함을 보였습니다.
부호화된 사회적 연결망은 실생활에서 다양한 응용으로 사용될 수 있습니다. 페이스북, 인스타 그램 등과 같은 소셜 네트워크에서 내가 좋아할만한 게시물들만 추천해주거나, 데이팅 앱에서 소개해줄 상대를 추천해주는 일에서부터 아마존, 이베이와 같은 온라인 쇼핑몰에서 소비자가 좋아할만한 물건을 추천해주는 것까지 그 활용 범위가 매우 넓습니다. 본 논문이 제안한 SidNet 기법은 기존 기법들의 한계점을 훌륭하게 극복하여 이러한 다양한 응용처에서 효과적으로 활용 될 수 있을 것으로 기대됩니다. 논문에서는 본 문서에서 다룬 내용 이외에도 더욱 자세한 설명들과 다양한 이론적, 실험적 근거들이 있으니 관심있으신 분들은 논문을 참고해주시면 감사하겠습니다. (링크)