SIDE: Representation Learning in Signed Directed Networks

Posted by 날짜:

  본 문서에서는 WWW 2018에서 발표된 "SIDE: Representation Learning in Signed Directed Networks" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.

Representation Learning in Signed Directed Networks.

부호화 되어있고, 방향성이 있는 그래프에 있는 노드들에 대해서 어떻게 하면 각 노드의 표현 (representation)을 정확하게 학습할 수 있을까요? Representation learning은 주어진 그래프 내에 있는 각각의 노드들에 대해서 각 노드를 표현하는 벡터를 학습하는 것을 의미하며, 그림 1에서와 같이 각 노드별로 고유의 벡터를 가지게 되는 것을 알 수 있습니다. 이때의 노드별로 학습되는 벡터들을 표현 (representation)이라고 하며, 학습된 노드들의 표현은 노드 식별 (node classification), 연결 예측 (link prediction), 그리고 군집화 (clustering) 등 다양한 그래프 문제를 푸는데 사용되기 때문에 각 노드별로 정확한 표현을 학습하는 것은 매우 중요합니다. 

그림 1. Representation learning 예시
이때, 각 노드별로 학습된 표현은 그래프의 구조적인 정보를 잘 담고 있어야 하는데 그래프에서 방향성이 추가되고, 각 간선 (edge)에 부호가 주어진다면 그래프의 구조적인 정보가 더욱 복잡해져서 이러한 정보들을 정확하게 담기가 더욱 어려워지게 됩니다. 본 문서에서는 이러한 방향성이 있고, 부호화된 그래프에서도 정확하게 표현을 학습하는 방법에 대해 알아보도록 하겠습니다.

Network Embedding Formulation

그래프 상에 있는 노드들의 표현을 학습하기 위해서는 다양한 방법이 있는데, 본 글에서는 Random Walk를 기반으로 한 방법을 소개해드리도록 하겠습니다. Random Walk를 이용한 방법은 말 그대로 그래프 상에서 연결된 간선들을 이용하여 임의로 걸어다니는 random suffer가 있다고 했을 때, 그 random suffer가 이동하는 경로를 이용하여 각 노드의 표현을 학습하는 방법을 의미합니다. 이 방법은 다음과 같은 두 가지 단계로 요약할 수 있습니다.

  1. Random Walk 생성 단계
     그래프 상에서 임의로 움직이는 random suffer가 있다고 생각하고, random suffer가 움직일 수 있는 경로를 계속해서 생성해내는 단계입니다. 이 단계에서 생성되는 노드들의 경로는 노드들이 그래프 상에서 얼마나 가까운지를 알 수 있게 해주는 지표가 됩니다.
  2. 학습 단계: 
     첫 번째 단계에서 생성된 경로들 상에서 기준 거리보다 가까운 거리로 등장한 노드들을 동시에 등장한 노드들 (co-occuring node pairs)이라고 생각하고 이들 노드들의 표현이 비슷해질 수 있도록 각 노드의 표현을 학습합니다.
위와 같은 방법으로 노드의 표현을 학습하게 되면 서로 동시에 많이 등장한 노드들 간에 비슷한 표현을 가지게 되기 때문에 위와 같은 방법을 사용해서 노드들의 표현을 학습하게 됩니다. 하지만, 여기서 알아야할 점은, 지금까지 소개한 방법에서는 간선의 부호가 전혀 고려되지 않았으며, 위 방법을 부호화된 방향성 네트워크 상에서 사용할 경우 부호와 간선의 방향에 대한 많은 정보 손실이 일어난다는 점입니다. 

Proposed Method

Overview

본 논문에서는 그래프 상에서의 방향성과 간선의 부호를 고려하여 정보손실 없는 노드의 표현을 학습하려고 합니다. 이를 달성하기 위해서는 다음과 같은 세 가지 문제점들을 해결해야 합니다.
  • Multi-step relation: Radom Walk로 경로를 생성하여 학습을 진행할 경우 직접 연결되지 않은 노드들에 대해서도 학습을 해야하는데, 이때의 부호와 방향성을 어떻게 추측해야 할까요?
  • Negative edges: 기존 방법으로는 고려되지 않던 부정적으로 연결되어 있는 간선들에 대해서는 어떻게 학습을 하는 것이 좋을까요?
  • Individual connectivity: 어떻게 하면 노드 자체의 연결성을 노드의 유사성과 따로 고려할 수 있을까요?
본 논문에서는 위의 문제점들을 모두 해결하며, 부호화된 방향성 그래프의 정보를 손실없이 학습할 수 있는 방법인 SIDE를 제안합니다. SIDE에서는 다음과 같은 세 가지 방법들을 도입하여 각 문제를 해결하였습니다. 지금부터 이들에 대해 각각 알아보도록 하겠습니다.

Sign and Direction Aggregation

Random walk를 통해 생성된 경로 상에서 두 노드들의 관계를 분석할 때, 직접 연결되어 있지 않은 노드들 사이의 방향과 부호를 고려하려면 이를 추정해야합니다. 우선, 두 노드 사이의 방향성의 경우에는 위 경로는 random suffer가 노드 사이에 연결된 간선을 통해 이동하면서 생긴 경로이기 때문에 경로 상에 먼저 등장한 노드에서 나중에 등장한 노드로 방향성이 있다고 보아도 무방합니다. 다음으로 두 노드 간의 부호는 균형 이론 (balance theory)을 통해 추정됩니다. 이는 친구의 친구는 친구, 친구의 적은 적, 적의 친구는 적, 적의 적은 친구라는 것을 의미하는데, 이 때, 양의 간선을 친구 관계, 음의 간선을 적 관계라고 생각하면 이 이론을 노드 간의 부호를 예측하는 데 사용할 수 있습니다. 본 논문에서는 균형이론을 바탕으로 두 노드 간의 연결 사이에 있는 적대적 관계의 수가 짝수 개이면 친구, 홀수 개이면  적으로 부호를 부여하였습니다.

Signed Proximity Term

본 논문에서는 간선의 부호를 고려하기 위해서 두 노드간의 간선이 적대적인 관계를 나타낼 경우 노드간의 연결성을 나타내는 함수에 (-1)을 곱해 주었습니다. 또한, 간선의 방향성을 고려하기 위하여 들어오는 간선에 대한 노드의 표현과 나가는 간선에 대한 노드의 표현을 구분하여 학습하였습니다. 이러한 과정을 통해 본 논문에서는 간선의 부호와 방향성을 제대로 학습할 수 있게 되었으며, 자세한 수식은 논문 (링크)을 통해 확인하실 수 있습니다.

Bias Terms

마지막으로 SIDE에서는 각 노드들간의 연결성을 표현하기 위해 bias term을 도입하였습니다. 특히 실제 상황에서 많은 그래프들은 power law를 따르게 되는데, 이러한 경우 연결성이 높은 노드들을 표현할 방법이 필요해지는데, 이를 나타낼 수 있게 해주는 것이 bias term입니다. 본 논문에서는 간선의 방향성과 부호를 고려하기 위하여 들어오고 나가는 방향성, 양과 음의 부호 각각의 조합에 대해 서로 다른 bias term을 도입하여 각 노드별로  4개의 bias term를 도입하였습니다.

SIDE 알고리즘에서는 위와 같은 세 가지 방법을 통해 그래프의 부호와 방향성 정보를 모두 잘 담아내려고 하였습니다. 그리고 우리는 그 결과를 그림 2를 통해 확인할 수 있습니다. 그림 2에서 (a)는 실험에 사용한 그래프를 나타내며, 여기서 파란색 간선은 우호적인 관계, 빨간색 간선은 적대적인 관계를 나타냅니다. (b)는 본 논문에서 제안한 SIDE 알고리즘, (c)와 (d)는 각각 서로 다른 SIDE의 경쟁 알고리즘으로 학습한 노드의 표현을 시각화한 것입니다. 이 때, 우리는 우호적인 노드들이 가까이 있고, 적대적인 노드들이 멀게 배치되어 같은 기호끼리 가깝고, 다른 기호 끼리 멀게 배치되기를 기대했는데 오직 SIDE 알고리즘만이 이와 같은 결과를 보여 그래프 상의 부호 정보를 올바르게 반영했음을 알 수 있습니다.

그림 2. 알고리즘 별 노드 표현 시각화 결과


Experiments

본 논문에서는 SIDE의 성능을 평가하기 위해 실제 세상에서 얻어진 그래프 (real-world graph)를 바탕으로 다양한 실험을 하였고, 본 문서에서는 그 중에 부호 예측 실험과 확장성 실험에 대해 소개하도록 하겠습니다. 
우선, 부호 예측 실험 결과는 그림 3와 같습니다. 실험 결과 SIDE 알고리즘을 이용하여 학습된 각 노느들의 표현을 이용하여 간선의 부호를 예측했을 때 가장 높은 정확도와 F1-score를 보인 것을 확인할 수 있습니다.

그림 3. 실 세계 그래프 상에서의 간선 부호 예측 실험 결과

다음으로 SIDE 알고리즘의 확장성을 확인하기 위해 노드의 수에 따른 알고리즘의 실행 시간을 측정해보았으며 그 결과는 그림 4과 같습니다. 실험 결과 SIDE는 비교 대상인 두 알고리즘에 비해 최대 1.8배 더 빠른 속도를 보였으며, 노드 수가 증가함에 따라 선형적으로 증가하는 실행시간을 보였고, 그 기울기 또한 세 알고리즘중에 가장 낮아서 큰 그래프에서도 충분히 사용 가능한 확장성이 있는 알고리즘이라는 것을 확인할 수 있었습니다.

그림 4. SIDE의 확장성.

Conclusion

본 문서에서는 SIDE: Representation Learning in Signed Directed Networks 논문을 소개하였습니다. 해당 논문에서는 부호화되어 있고, 방향성이 있는 그래프상에서 노드들의 표현을 잘 학습할 수 있는 방법인 SIDE를 제안하였습니다. 또한, 실험 결과 본 논문에서 제안한 방법으로 학습된 노드의 표현을 사용할 경우 부호 예측을 잘 할 수 있으며, SIDE 알고리즘은 큰 그래프에 대해서도 적용할 수 있는 확장성 있는 알고리즘이라는것을 확인하였습니다. SIDE 알고리즘은 적대적인 관계를 포함하는 사회 연결망 그래프를 분석하는데 사용될 수 있으며, 확장성이 높은 알고리즘이기 때문에 규모가 큰 그래프도 처리해낼 수 있어 중요성이 높은 알고리즘이라 할 수 있습니다. 해당 논문에 대한 더욱 자세한 정보는 현재 링크를 통해 확인하실 수 있습니다.