[CS224w] Label Propagation on Graphs (1) - Outline

Introduction

주어진 데이터 그래프의 모든 노드에 label이 있지 않을 수 있다.

이 때 network의 다른 node에 label을 어떻게 할당할 수 있을까?

 

기본적으로 node embedding (random walk, GNN 등)을 이용하여 해결할 수 있지만, network topology를 이용한 방법은 없을까?

Semi-Supervised Node Classification이 하나의 방법이 될 수 있다.

반응형

Observation: Correlations in Networks

이웃한 노드들은 서로 correlated한 경향이 있다.

Correlations in Networks

이웃하는 노드가 상관성을 갖는 것은 크게 homophily와 influence로 설명할 수 있다.

Homophily: 같은 interest를 갖는 사람들끼리 더 연결되는 경향이 있다.

Influence: 내가 친구에게 음악을 추천새주면, 친구들 중 일부는 나랑 같은 음악을 더 듣게된다.

 

Semi-supervised Learning

Sample Network

Formal Setting

Given: Graph, Few labeled nodes (위 그림에서 label이 없는 노드는 회색으로 나타냈다)

Find: Class (red/greed) of remaining nodes

Main Assumption: There is homophily in the network

 

각 노드 $v$는 feature vector를 갖고있고, 이를 $f_v$ 라 하자.

$v$의 label을 $Y_v$라 할 때, label의 확률 $P(Y_v)$를 구해보자.

 

크게 3가지 방법이 존재한다.

• Label Propagation
• Correct & Smooth
• Masked label prediction