[CS224w] Label Propagation on Graphs (2) - Label Propagation

Label Propagation

labeled node는 ground truth label $Y_v^*$로 초기화한다.

unlabeled node는 $Y_v = 0.5$로 초기화한다.

 

Update each unlabeled node

\[ P^{(t+1)}(Y_v = c) = \cfrac{1}{\sum_{(v, u) \in E} A_{v,u} } \sum_{(v, u) \in E} A_{v, u} P^{(t)}(Y_v = c) \]

$A_{v, u}$: edge에 가중치(strength, weight)가 있다면 $A_{v, u}$는 두 노드 $v$와 $u$ 사이의 edge weight를 나타낸다.

$P(Y_v = c)$: 노드 $v$가 label이 $c$일 확률

convergence할 때 까지 반복하여 update를 수행한다.

• Convergence Criteria: $ |P^{(t)}(Y_v) - P^{(t-1)}(Y_v)| \le \epsilon $
• 이전 단계에서의 확률과 차이가 나지 않을 때 수렴한다.

반응형

Example

[Initialization] label이 있는 노드는 그 label 자체로 시작 label이 없는 노드는 $0.5$로 초기화
[Iteration #1, Node 3] 3번 노드의 이웃노드는 $N_3 = \{ 1, 2, 4 \}$ 따라서 이들의 확률의 평균값이 $P(Y_3)$가 된다.
[Iteration #1, Node 4] 4번 노드의 이웃노드는 $N_4 = \{ 1, 3, 5, 6 \}$ 따라서 이들의 확률의 평균값을 계산한다. 이때 이전 단계의 확률을 이용해야 하므로 Iteration #0의 확률을 이용한다.
[Iteration #1, End]
[Iteration #2, End]
[Iteration #3, End]
[Iteration #4, End] Iteration #3과 거의 차이가 나지 않는다. 따라서 convergence

Applications

Labael Propagation의 적용분야는 대표적으로 다음과 같다.

• Document Classification
  • node: document
  • edge: document similarity (e.g. word overlap)
• Twitter polarity classification
  • node: users, tweets, words, hashtags, emoji
  • edges: [users -> users]: Twitter follower graph
  • edges: [users -> tweets]: creation
  • edges: [tweets -> words/hashtags/emoji]: part of
• Spam / Fraud Detection

 

Issue

• Convergence는 매우 느리며, 심지어 수렴성이 보장되지 않는다.
• node attributes를 전혀 사용하지 않는다. (단순히 확률 계산만 반복하여 업데이트)
• feature information을 이용하여 label propagation을 향상시킬 수 있지 않을까?