본 문서에서는 WWW Journal에 게재된 "Accurate Relational Reasoning in Edge-labeled Graphs by Multi-labeled Random Walk with Restart" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
- Title: Accurate Relational Reasoning in Edge-labeled Graphs by Multi-labeled Random Walk with Restart
- Authors: Jinhong Jung, Woojeong Jin, Ha-Myung Park, and U Kang
- Journal: World Wide Web - Internet and Web Information Systems 2020
Relation Inference Task
관계 추론 (Relation Inference) 문제는 간선에 관계 라벨이 있는 그래프에서 연결되지 않은 두 정점이 주어졌을 때 두 정점 사이의 관계 라벨을 추론하는 문제입니다.
 |
| 그림 1. 관계 추론 문제 예시 |
예를 들어서 그림 1과 같이 그래프에서 간선에 관계 라벨이 {childOf, spouseOf, grandchildOf} 중에 하나 있을 수 있을 때 두 정점 s와 t 사이의 라벨을 맞추는 문제 입니다.
관계 추론 문제를 푸는 방법은 전통적으로 크게 path feature model과 translation based model로 분류되어 다루어져왔습니다. path feature model은 두 정점 사이에 특정 길이의 path를 추출하여 이를 기반으로 학습을 하여 추론을 하는 방법론입니다. 그러나 그래프에서 path를 추출하는 작업은 길이가 조금만 길어져도 많은 계산량을 요구하기 때문에 전통적인 path feature model은 짧은 경로의 path만을 대상으로 학습을 하였고 이는 더 긴 path로 부터 얻을 수 있는 정보를 활용할 수 없게 되어 추론 성능에 제약이 있습니다. translation based model은 시작 정점의 임베딩에 관계 임베딩을 더하면 도착 정점의 임베딩와 같은 방향을 가져야한다는 가정을 기반으로 정점과 관계의 임베딩을 학습하여 추론을 하는 방법입니다. 간단하게 학습을 진행할 수 있지만 학습시 한번에 하나의 간선 만을 대상으로 학습을 진행하기 때문에 multi-hop path로 부터 제공될 수 있는 다양한 정보를 학습을 할 때 놓칠 수 있게 됩니다.
Random Walk with Restart and Its Limitation
본 논문에서는 전통적인 접근 방법과는 달리 그래프에서 정점간의 관계도를 구하는 방법인 Random Walk 기반의 기법으로 관계 추론 문제를 해결하려고 합니다. Random Walk with Restart (RWR)는 두 정점간의 그래프 구조적인 관계도 (relevance score)를 구하는 방법입니다. RWR에서는 랜덤 서퍼를 이용하여 특정 seed 정점에서 출발하게 하여 그래프를 탐색하게 합니다. 각 단계 마다 랜덤 서퍼는 다음의 두 가지 행동중 하나를 선택하여 행동하게 됩니다.
- Random walk: 현재 노드에서 나갈 수 있는 이웃 정점 중 하나를 임의로 선택하여 이동하는 것을 말합니다.
- Restart: 출발 했었던 seed 노드로 되돌아가는 것을 말합니다.
 |
| 그림 2. RWR의 Input과 Output의 예시. RWR은 두 정점 사이의 연결 관계와 정점의 연결 차수 및 경로의 길이 등 그래프 구조적으로 다양한 측면을 고려하여 정점간 관련도를 파악합니다. |
예를 들어서 그림 2와 같이 정점 4에서 출발하여 RWR을 반복적으로 수행하면 특정 정점에서 랜덤 서퍼가 도달하게 되는 확률을 구할 수 있고, 각 정점 별 확률을 출발 정점과 해당 정점의 관계도 점수로 활용하게 됩니다. Restart를 주기적으로 하기 때문에 그래프 구조적으로 긴밀하게 연결되어 있는 정점일 수록 RWR 점수가 크게 됩니다. 랜덤 서퍼가 특정 노드에 도달하기 위해서는 여러 path를 거쳐 도달 할 수 있기 때문에 두 정점의 관계도는 multi-hop path를 명시적으로 추출하지 않아도 자연스럽게 path에 의한 정보를 반영할 수 있다는 장점이 있습니다.
그러나 RWR은 관계 라벨이 있는 그래프에서 관계 추론의 문제를 해결 할 수 없습니다. 그 이유로는 두 정점이 어떠한 관계 라벨로 관련이 있는지 알 수 없기 때문입니다. 예를 들어서 그림 1에서 두 정점 s와 t가 어떠한 관계 라벨로 얼마만큼 관련이 있는지 알 수 없습니다. 랜덤 서퍼는 두 정점이 그래프 구조적으로 두 정점의 관계도만을 파악할 뿐 라벨의 측면에서는 두 정점의 관련도를 파악 할 수 없습니다.
Proposed Method
본 논문에서는 위와 같은 RWR의 한계점을 극복하고 관계 추론을 효과적으로 할 수 있는 랜덤 워크 모델인 MuRWR (Multi-labeled Random Walk with Restart)를 제안합니다. MuRWR의 핵심 아이디어는 다음과 같습니다.
- 랜덤 서퍼가 관계 라벨을 가지게 합니다. 이를 labeled random surfer라고 부르며 랜덤 서퍼가 특정 정점에서 가지고 있는 라벨은 시작 정점과 해당 정점의 관계 라벨을 의미합니다.
- Labeled random surfer는 그래프의 정점을 랜덤 워크 하면서 특정 규칙에 따라 서퍼의 라벨을 변경할 수 있게 하여 multi-hop 추론을 할 수 있도록 합니다.
- 입력 그래프로 부터 서퍼의 라벨을 변경하는 규칙을 추출하여 서퍼가 어떻게 라벨을 변경해야하는지 학습합니다.
 |
| 그림 3. Labeled random walk (a)와 label transitive triangles (b-c)의 예시 |
MuRWR에서 s에서 t까지의 서퍼의 움직임은 두 정점의 관계를 추론하는 과정으로 생각할 수 있습니다. 그림 3은 MuRWR에서 서퍼가 어떻게 s와 t사이의 관계를 추론하는지 나타내는 예입니다. 서퍼는 특정 정점에서 childOf나 grandchildOf (gclOf)와 같은 라벨을 가질 수 있습니다. 먼저 위 예에서 다음과 같은 규칙이 있다고 가정을 하겠습니다.
- Rule 1. childOf 라벨을 가지는 서퍼가 childOf 간선을 타고 이동하는 경우, 다음 노드에서 서퍼의 라벨은 grandchildOf로 변경됩니다.
- Rule 2. grandchildOf 라벨을 가지는 서퍼가 spouseOf 간선을 타고 이동하는 경우, 서퍼의 라벨은 그대로 grandchildOf를 가집니다.
그림 3에서 먼저 서퍼는 아무런 라벨을 가지지 않은 상태에서 시작 정점 s에서 출발을 합니다. 이 경우 정점 u에서 childOf 라벨을 가지게 됩니다. 이때 서퍼가 childOf 라벨을 가진다라는 의미는 두 정점 s와 u이 childOf라는 라벨로 관련이 있다라는 의미입니다. 그 다음, 정점 v로 이동 할때는 Rule 1에 의해 서퍼의 라벨은 grandchildOf로 변경됩니다. 따라서 정점 s와 v는 grandchildOf로 관련이 있습니다 (즉, s는 u의 자식이고 u는 v의 자식이므로 s는 v의 손자가 됩니다). 유사하게 정점 t로 이동 할때는 Rule 2에 의해 그대로 grandchildOf를 가지게 됩니다. 이와 같은 움직임을 labeled random walk이라고 부르며 특정 정점에서 서퍼가 가지고 있는 라벨을 통해 두 정점의 관계 라벨을 파악할 수 있습니다.
그렇다면 처음 가정했던 규칙은 어떻게 알아낼 수 있을까요? 이를 위해 본 논문에서는 data driven 방식을 기반으로 하여 규칙을 파악하는 방법을 제안합니다. 서퍼가 변경되는 규칙은 그림 3(b)와 (c)에서와 같은 labeled transitive triangle로 표현되는 지식으로 부터 추출될 수 있습니다. 하나의 transitive triangle은 삼단논법적인 해석을 가집니다. 예를 들어서 그림 3(b)는 다음과 같이 해석됩니다.
childOf(x, y) and childOf(y, x) => grandchildOf(x, z)
따라서 하나의 transitive triangle이 주어지면 그림 3(b)와 같이 서퍼가 어떻게 변경되어야하는지 학습할 수 있습니다. 예를 들어서 아무런 라벨이 없는 서퍼가 x에서 각 정점 y로 이동한다고 생각하면 y에서는 childOf라벨을 가져야합니다. 유사하게 z에서는 grandchildOf라는 라벨을 가져합니다. 이 상황에서 y에서 z로 이동한다고 생각하면 childOf 간선을 타고 이동하는 경우 Rule 1과 같이 라벨을 변경해야 한다는 것을 추출해 낼 수 있습니다. 따라서 입력 그래프에서 labeled transitive triangle을 모두 추출하여 추출된 삼각형을 기반으로 서퍼의 규칙을 학습합니다.
Experimental Result
 |
| 그림 4. 제안 기법인 MuRWR의 정확도 (accuracy). 기존의 다른 경쟁 메소드 보다 좋은 추론 성능을 보입니다. |
그림 4에서는 간선에 라벨이 있는 실세계 그래프에서 각 메소드별 두 정점 사이의 관계 추론 정확도를 나타냅니다. Random은 간선의 라벨을 랜덤으로 추론하는 방법으로 관계 추론의 최소 기준 정확도를 나타내는 방법입니다. Line과 node2vec은 정점의 임베딩을 추출하는 방법인데 그래프의 라벨 정보를 고려하지 않아서 추론 성능에 한계가 있습니다. SRWR은 부호가 있는 그래프 (WikiVote, Slashdot, Epinions)에서는 작동하는 랜덤워크 기법이지만 그 외의 그래프에서는 작동하지 않는 방법입니다. MuRWR이 PRA (path feature model)이나 TransE/R (translation based model)보다 좋은 성능을 내는데 이는 MuRWR이 경쟁 메소드 보다 더 긴 multi-hop path의 정보를 고려하기 때문에 발생하는 차이라고 유추할 수 있습니다.
Conclusion
본 문서에서는 WWW Journal 2020에 게재된 "Accurate Relational Reasoning in Edge-labeled Graphs by Multi-labeled Random Walk with Restart" 논문을 소개하였습니다. 해당 논문은 간선에 임의의 라벨이 있는 그래프에서 랜덤워크를 통해 효과적으로 관계 추론을 할 수 있는 방법인 MuRWR을 제안하였습니다. 실험을 통해 제안 기법이 다른 경쟁 모델보다 효과적으로 관계 추론을 함을 확인하였습니다. 논문에 대한 상세 정보는 link를 통해 확인 할 수 있습니다.