작성자 : 권오현

0. Intro

Main Question : 몇몇의 Nodes에 Label이 주어진 Network(Graph)에서 다른 Nodes의 Label을 어떻게 할당할 것인가 ?

• Lecture 3에서 배운 Node Embeddings에 Simply Classifier (Which node is trusted or not trusted )를 추가하면 해결된다.

• 이번 Session에서는 Semi-Supervised Node Classification의 방법으로 해결해 본다.

• Semi-Supervised Node Classification : 주어진 nodes의 labels을 통해 unlabeled nodes의 label을 예측

cf. Semi-Supervised Learning :
Label이 있는 데이터를 학습 하는 Supervised Learning과 Label이 달려 있지 않는 데이터를 학습 하는Unsupervised learning 의 조합으로 이루어진 것을 의미한다.

1. Collective Classification

Intuition : Correlations exist in networks

• Network에서 동일한 Label을 가지는 Nodes는 연결되어 있다고 생각한다. (Network 상에는 Correlation이 존재한다.)

  이러한 가정을 통해 유사한 Nodes는 군집을 형성하고 있다고 판단.- Semi-Supervised Learning

• Labels of the neighbors in the network의 정보를 통해 우리가 예측해야할 node v에 Label을 assign 해준다.

• Collective Classification Techniques :

  • Relational Classification
  • Iterative Classification
  • Belief Propagation

Correlations Exist in Networks

• Homophily
  "The tendency of individuals to associate or bond with similar others "
  • Birds of feather flock together (유유상종)
  • 비슷한 관심사를 가지는 경우 connection이 형성된다.
    
• Influence
  "Social connection can influence the indivisual"
  

Question : How do we leverage this correlation observed in networks to help predict node labels ?

• Motivation

  • 유사한 nodes은 일반적으로 Close together 이거나 Directly connected 되어 있다.

    guilt-by-association : 내가 label이 x인 노드와 연결되어 있으면 나도 label이 x일 확률이 높아진다 !

  • 네트워크 내에서 node v의 Classification label은 다음 3가지에 의해 영향을 받는다.
    

  → 이제 networks에 homophily이 존재한다고 가정하고 graphically하게 생각해 보면 같은 label의 nodes가 서로 연결되는 경향이 있다!

  

• 결론적으로 Node classification task는 unlabeled nodes가 Class 1이거나 Class 0인 확률을 예측하는 것이다.

  • A : Adjaceny matrix, A는 unweighted or weighted / undirected or directed

  ex) Document classification, Link Prediction, Spam and fraud detection 등

Collective Classification Overview

Intuition : Simultaneous classification of interlinked nodes using correlations

• Probabilistic Framework
  

  • label $Y_v$는 neighbor nodes $N_v$의 label에 의존한다. (degree 1 neighborhood)

    $P(X_{t+1} | X_{t},X_{t-1},...,X_1) = P(X_{t+1}|X_t)$ : 어떤 확률변수 $X_{t}$의 분포는 바로 직전에 나타난 확률 변수 $X_{t-1}$ 에만 의존한다. $X_{t-1}$이 $X_1$부터 $X_{t-2}$까지의 정보도 포함하고 있다고 가정

• Collective Classification은 "altogether classifying all the nodes on the graph because every nodes labeled depends on other nodes labeled"
  → nodes will be update the belief for a prediction about the labels until the process will converage
  

• STEP 3
  

  • STEP 1 : Local Classifier
    • node의 attributes/features를 통해 초기 Label을 할당한다.
    • 이 때 network information은 사용하지 않는다.
  • STEP 2 : Relational Classifier
    • nodes간의 correlations를 capture 한다.
    • neighbors의 label/attribution 정보를 사용하여 classifier를 학습한다. (여러번 반복)
  • STEP 3 : Collective Inference
    • Propagate the correlation
    • 각 nodes 마다 Relational Classifier를 수행한다.
    • 결과적으로 network의 정보를 사용하여 nodes의 label을 예측한다.

→ Collective Classification은 neighborhoods의 labels의 inconsistency가 최소화 될 때 까지 반복한다.

2. Relational classifiers

Setting

• Basic Idea : node $v$ 의 $Y_v$의 class probability는 neighbors의 class probability의 weighted average

• labeled node : ground-truth label $Y^{*}_{v}$ 로 initialize

• unlabeled node : $Y_v$ 를 uniform하게 initialize, 믿을만한 prior가 존재하면 이를 사용하여 initialize

• update : 수렴 or max iteration 까지 모든 노드를 random order로 업데이트 한다.

• $\sum_{(v,u)\in E} A_{v,u}$ : node v의 counts the degree or the in-degree of node v (만약 edges가 weight information이면 $A_{v,u}$는 node v, u 사이의 edge weight)
• $A_{v,u} P(Y_u =c)$ : edges의 weight * neighbor의 label = c 일 likelihood
• $\frac{1}{\sum_{(v,u)\in E} A_{v,u}}$ : node v의 label = c일 likelihood 이기 때문에 normalization을 위한 계수

Example

1. Initialize : labeled nodes 는 groud-truth에 맞게 초기값을 설정, unlabeled nodes는 0.5로 설정
   
2. $1^{st}$ Iteration : random order를 통해 unlabeled nodes의 probability를 update
   - unweighted graph 이기 때문에 neighbors의 average로 설정
   
   - node의 probability가 update 됨
   
3. Repeat Iteration : 모든 node가 수렴되거나 max iteration 까지 반복
   

• 여기에서 이전 Iteration과 다음 Iteration에 대해서 node의 probability가 변하지 않으면 수렴 되었다고 판단
• random order 로 학습이 되기 때문에 이전 node의 probability가 다음 node의 probability에 영향을 미치기 때문에 Propagate

Challenges

• 수렴이 보장되지 않는다.
• node의 feature information을 사용하지 않았다.
  → 단순히 nodes의 label과 network information만 이용하기 때문이다.

3. Iterative Classification

Setting

• Main Idea : 단순히 neighbor set $N_v$의 labels $\mathrm{z}_v$만 사용한 Relational Classifier 방법에 neighbor set $N_v$의 attributes $f_v$도 사용

• Input : Graph

  • $f_v$ : feature vector for node $v$
  • $Y_v$ : labeled nodes $v$

• Two Classifiers

  • $\phi_1(f_v)$ : feature vector $f_v$를 통해 node label을 예측하는 모델
  • $\phi_2(f_v,\mathrm{z}_v)$ : feature information과 network information(summary $\mathrm{z}_v$ of labels of $v$'s neighbors) 두개 다 고려하여 node label을 예측하는 모델

    Compute summary $\mathrm{z}_v$ of labels of $v$'s neighbors $N_v$ :

    • Histogram of the number of each label in $N_v$
    • Most common label in $N_v$
    • Number of different labels in $N_{v}$

• Update :

  • Iterative classifier는 2step으로 구분된다.
    

  • Phase 1 : training set을 통해 classifier를 학습한다 e.g., linear classifier, svm, neural networks

    • $\phi_1(f_v)$ : node의 feature $f_v$를 통해 node의 label $Y_v$를 예측하는 모델
    • $\phi_2(f_v, \mathrm{z}_v)$ : node의 feature $f_v$ , summary $\mathrm{z}_v$ of labels of $v$'s neighbors 를 통해 node의 label $Y_v$를 예측하는 모델

  • Phase 2 :

    • $\phi_1(f_v)$를 통해 node의 label $Y_v$를 할당
    • summary $\mathrm{z}_v$ of labels of $v's$ neighbors를 compute
    • $f_v$ , $\mathrm{z}_v$를 이용하여 모델($\phi_2(f_v,\mathrm{z}_v)$)을 통하여 labels를 예측한다.
    • Repeat for each node v
      • Update $\mathrm{z}_v$ based on $Y_u$
      • Update $Y_v$ based on the new $\mathrm{z}_v$ ($\phi_2$)
    • 수렴하거나 max iteration 까지 반복 !
    • Convergence is not guaranteed

Example : Web Page Classification

• input : Graph of web pages
• Node : Web page
• Edge : Hyper-link between web pages (Directed edge)
• Node features : Webpage description
  

1. Phase 1 :

   • $\phi_1(f_v)$ : feature vector $f_v$를 통해 node label을 예측하는 모델

   • $\phi_2(f_v,\mathrm{z}_v)$ : feature information과 network information(summary $\mathrm{z}_v$ of labels of $v$'s neighbors) 두개 다 고려하여 node label을 예측하는 모델

   위의 그래프 경우 Directed graph이기 때문에 Incoming neighbor label information, Outgoing neighbor label information vectorfmf 고려해야 한다.

   • $I$ : Incoming neighbor label information vector
   • $O$ : Outgoing neighbor label information vecotr
   • $I_0$ : 최소 1개의 Incoming node의 label이 0 이면 1 아니면 0
   • $O_0$ : 최소 1개의 Outgoing node의 label이 0 이면 1 아니면 0

2. Phase 2 : 위에서 학습한 $\phi_1$, $\phi_2$를 Test Set에 적용해보자 !

• node feautre $f_v$를 사용한 모델 $\phi_1$를 통해 $Y_v$ 할당
  

• 할당된 $Y_v$ 를 통해 summary $\mathrm{z}_v$ of labels of $v$'s neighbors compute
  

• $f_v$ 와 $\mathrm{z}_v$를 이용하여 모델 $\phi_2$를 통해 $Y_v$ update
  
  

• 수렴이나 max iterations 까지 반복
  

Summary

• Relational classification : Iteratively update probabilities of node belonging to a label class based on its neighbors
• Iterative classification :
  • Improve over collective classification to handle attribute/feature information
  • Classify node $i$ based on its features as well as labels of neighbors

4. Belief Propagation

Setting

• Main Idea :

  • Graph에서 조건부확률 queries에 대한 Dynamic Programing approach

  • Neighbors가 서로 'Talk'하는 Iterative Process, Passing Messages

  • "When consensus is reached, calculate final belief"
    

  Belief Propagation(신뢰전파 알고리즘) : Graphical Model에서 일부 노드에 대한 확률 분포 또는 값이 주어졌을 때, 다른 노드에 해당하는 확률 변수의 분포를 추정하는 문제 !

Message Passing : Basics

1. Define an ordering of nodes
   
   
2. Edge directions are according to order of nodes
   
3. Compute the message from node i to i+1 and Pass the message

• 이와 같은 방법은 Primitive 하지만 Powerful 하다.

• 또한 마지막 노드만이 Task에 대한 답을 알 수 있다.
  

• Tree 구조에도 이를 사용할 수 있다.

• line graph나 tree의 root 만이 Task에 대한 정답을 알 수 있나 ?
  

• 빨간색으로 표시된 노드 또한 Message Passing을 통해 Task에 대한 답을 할 수 있다 !

• neighbors의 Belief를 통해 우리가 원하는 node의 Belief를 구할 수 있다 !

Loopy BP Algorithm

• Task : What message will i send to j ?
• node $i$ 가 주변 neighbors node $k , u , v$들로 부터 얻는 belief에 의존한다.
• 각각의 neighbor nodes $k,u,v$는 node $i$의 state에 대한 belief를 $i$에게 message passing을 하고, 이러한 message를 통해 node $i$가 node $j$에게 passing 함.

Notation

• $\psi$ : Label-label potential matrix

  • labels에 대해서 node와 neighbors 사이의 dependency
  • $\psi(Y_i, Y_j)$ : 노드 j의 neighbor i가 state $Y_i$에 있을 때, 노드 j가 state $Y_j$에 속할 확률과 비례한다. = correlation between node $i\& j$

    cf. Homophily에 대해서 Label-Label potential matrix가 high value on diagonal일 것이다. (node i 와 j의 class 가 같다) 만약 Big value off the diagonal 이면 node i와 j의 class는 다를 것이다.

• $\phi$ : Prior Belief

  • $\phi(Y_i)$ : node i 가 state $Y_i$에 속할 확률
  • node features capturing

• $m_{i \rightarrow j}(Y_j)$ : j가 state $Y_j$에 대한 $i$의 추정치

• $\mathcal{L}$ : 모든 states에 대한 집합 (class or labels)

Process

1. 모든 message들을 1로 초기화
2. 다음과 같은 방법을 반복 :

• node $i$의 neighbors로 부터 state $Y_i$에 대한 belief를 message passing
• node $i$의 node features를 통해 state $Y_i$에 속할 확률을 구한다.
• label-label potential matrix를 통해 $\psi(Y_i, Y_j)$를 구한다. ( 이 때 label-label potential matrix을 통해 구해진 값을 $i$의 label이 $j$의 label에 얼마나 영향을 끼치는지로 해석)
• 위에서 구한 값들을 통해 $m_{i \rightarrow j}(Y_j)$ 를 구한다.
  

3. 수렴하거나 max iteration이 되면, 각 state에 대한 Belief를 계산 !

Challenges

• Loopy Belief Propagation은 Cycle이 있을 경우 잘 작동하지 않음 !
  

• $m_{u \rightarrow i}(Y_i)$를 생각해보면, 이러한 cycle이 있으면 자기 자신의 정보를 반영하기 때문에 수렴이 되지 않음 !

• 걱정할 필요 없다 ! Real World의 Graph는 cycle이 작거나 발생하지 않는다 !

• 이러한 문제를 해결하기 위한 Heuristic한 방법도 많이 있다.

Summary

1. Advantages

   • 프로그래밍 및 병렬화가 쉬움

   • label-label potential matrix를 통해 어떤 그래프 모델보다 general하게 적용 가능하다 (homophily 뿐만 아니라 node labels의 complex patterns도 학습 가능)

2. Challenges

   • 수렴이 보장되지 않는다.

   • closed loop가 많으면 적용이 어렵다

3. Potential Functions

• parameter학습이 필요하다 (potential matrix, prior)

Reference

1. CS224W : Machine Learning with Graphs (Winter 2021)
2. 투빅스 GNN 스터디 (12-13기)
3. 데이터 괴짜 Graph 리뷰
4. Stanford cs224 notes
5. AI PLUS TECH : Semi-supervised learning