<CS224W> Lecture 5: Label Propagation for Node Classification

kimkj38·2022년 3월 31일
0

CS224W

목록 보기
5/17

1.Message Passing and Node Classification

Correlation

  • 가까운 노드들끼리는 같은 클래스에 속한다고 보고 동일한 색을 부여한다.
  • 상관관계는 Homophily와 Influence에 의해 정의된다.

    Homophily: 비슷한 특성을 지니는 것들끼리 모이는 경향이 있다.
    Unfluence: 사회적인 관계가 개인의 특성에 영향을 미친다.

Motivation

  • 그래프 상에서 비슷한 노드들가까이 위치하거나 서로 연결되어있을 것이라는 가정
  • Guilt-by-association: 어떤 노드와 연결되어 있는 노드는 그 노드와 동일한 라벨을 가질 것이다.
  • 노드 vv의 라벨은 vv의 feature와 vv이웃 노드들의 라벨과 feature에 영향을 받는다.

Semi-supervised Learning

  • 일부 노드들의 라벨(color)을 알고 있을 때 나머지 노드들의 라벨을 예측하는 semi-supervised learning
  • 네트워크에 homopyiliy가 있다고 가정한다.

Collective Classification

  • 상관관계를 이용해 연결된 노드들의 클래스를 동시에 분류한다.
  • Markov assumption: 노드 vv의 라벨 YvY_v는 이웃노드의 라벨 NvN_v의 영향을 받는다.
    P(Yv)=P(YvNv)P(Y_v) = P(Y_v|N_v)
  • Collective classification은 3개의 step으로 이루어진다.

    1. Local Classifier: 초기 라벨을 할당하는 단계로 노드의 feature를 통해 예측한다.
    2. Relational Classifier: 노드 간의 상관관계를 이용하는 단계로 이웃노드들의 feature를 활용하여 예측한다.
    3. Collective Inference: 상관관계를 활용하는 classifier를 반복적으로 적용하는 단계로 이웃 노드들 간의 inconsistency가 최소가 될 때 반복을 마친다.

2. Relational Classification and Iterative Classification

Relational classifiers

  • 노드 vv의 class probability YvY_v이웃 노드들의 class probability의 가중평균으로 정의한다.
  • 라벨링 된 노드는 ground truth YvY_v^*, 라벨링이 안 된 노드는 Yv=0.5Y_v=0.5로 초기화한다.
  • 수렴할 때까지 혹은 최대 반복횟수에 도달할 때까지 랜덤한 순서로 노드를 업데이트 한다.
  • P(Yv=c)P(Y_v=c)는 노드 vv가 라벨 cc일 확률을, Av,uA_{v,u}는 두 노드 간의 edge weight를 의미한다.
  • 수렴이 보장되지 않으며 노드의 feature 정보를 활용하지 않는다는 단점이 있다.

Example

Initialization

1st iteration, update node3

1st iteration, update node4

1st iteration, update node5

After 1st iteration

After 2nd iteration

After 3rd iteration

After 4th iteration, Convergence

  • 4번의 반복 이후 모든 노드들이 수렴했다.
  • PYvP_{Y_v}가 0.5보다 크면 클래스 1, 작으면 클래스 0으로 분류한다.

Iterative Classification

  • 이웃노드 집합 NvN_vsummary zvz_v와 feature fvf_v를 모두 이용해 노드 vv를 분류한다.
  • feature vector로 예측하는 ϕ1(fv)\phi_1(f_v)와 feature vector와 summary를 통해 예측하는 ϕ2(fv,zv)\phi_2(f_v,z_v) 두 개의 분류기를 활용한다.
  • Summary zvz_vNvN_v에서 각 라벨의 수에 대한 히스토그램, 존재 유무, 비율 등에 대한 vector로 정의할 수 있다.

Training

  • Training 과정에서는 모든 노드의 라벨을 알고 있다.
  • ϕ1(fv)\phi_1(f_v)ϕ2(fv,zv)\phi_2(f_v,z_v)를 통해 YvY_v를 예측한다.
  • zvz_v는 실제 라벨을 이용해 구성한다.

Test

  • Test 과정에서는 일부 노드의 라벨만 알고 있다. 혹은 모든 노드의 라벨을 모를 수도 있다.
  • fvf_v는 변하지 않을므로 ϕ1(fv)\phi_1(f_v)는 한 번만 계산하여 YvY_v를 예측한다.
  • ϕ1\phi_1을 통해 할당한 초기 YvY_v를 토대로 아래 과정을 수렴 혹은 최대횟수에 도달할 때까지 반복한다.
    1. YvY_v를 통해 zvz_v를 업데이트한다.
    2. ϕ2(fv,zv)\phi_2(f_v,z_v)를 통해 YvY_v를 업데이트한다.

Example

Input: 웹페이지의 그래프
Node: 웹페이지
Edge: 웹페이지를 연결하는 하이퍼링크(Diredcted)
Node feature: 웹페이지 description
Task: 각 웹페이지의 주제 예측

fvf_v: 각 노드의 feature vector(TF-IDF 등)
II: Incoming neigbor 라벨에 대한 summary([0인 이웃노드 유무, 1인 이웃노드 유무])
OO: Outgoing neigbor 라벨에 대한 summary([0인 이웃노드 유무, 1인 이웃노드 유무])

Training

  • Feature vector(green)만을 활용해 ϕ1\phi_1YvY_v 예측
  • Feature vevtor와 summary(red)를 활용해 ϕ2\phi_2YvY_v 예측

Test

  • 학습된 ϕ1\phi_1을 통해 YvY_v를 예측한다.
  • 예측한 YvY_v를 통해 zvz_v를 업데이트한다.
  • fvf_v와 새로운 zvz_v를 통해 YvY_v를 업데이트 한다.
  • 위 과정은 수렴할 때까지 반복하며 예시에는 한 번의 반복만으로 GT를 맞춘 것을 확인할 수 있다.

3. Collective classification: Belief Propagation

Loopy Belief Propagation

  • 앞서 본 방식에서는 노드 vv의 클래스 확률을 이웃 노드의 확률의 가중평균으로 정의하였다.
  • 이를 이웃노드로부터 belief를 전달받는다고 말하며 반복을 통해 이웃노드 뿐만 아니라 간접적으로 연결된 노드(ex.이웃노드의 이웃노드)로부터도 영향을 받는다고 할 수 있다.
  • Loopy belief propagation은 간접적인 방식이 아닌 belief가 그래프에 직접 흐르도록 알고리즘을 구성하는 것을 의미한다.
  • 예를 들어, 트리 구조에서 그래프의 노드 수를 계산할 때는 child->parent 방향으로의 belief를 생각할 수 있다.
  • i1i-1 노드의 belief(이전까지 지나온 노드의 수)에 자기 자신 1을 더하면 ii 노드까지의 노드의 수를 구할 수 있다.

Algorithm

  • ψ\psi: 각 노드가 이웃노드의 클래스에 미치는 영향력을 나타낸 행렬. ψ(Yi,Yj)\psi(Y_i,Y_j)는 노드 ii의 라벨이 YiY_i일 때 노드 jjYjY_j 클래스에 속할 확률에 비례한다.
  • ϕ\phi(prior beleif): 노드 iiYiY_i에 속할 확률
  • mij(Yj):m_{i\rightarrow j}(Y_j): jj로 전달되는 ii의 메시지로 ii가 이웃노드들로부터 받은 belief와 자신의 정보를 종합해 jj의 라벨을 believe하는 것
  • L:L: 모든 라벨을 포함하는 집합

  • message passing 과정이 충분히 반복되어 수렴되었을 때 위 식과 같이 확률이 계산된다.

What Can Go Wrong?

  • 그래프가 순환구조인 경우 노드들은 독립적이지 않다.
  • 노드 uukk로부터 메시지를 받고 있지만 결국 자기 자신의 메시지까지 받는 상황이다.
  • 반대로 jji,ki,k로 메시지를 전달하고 i,ki,kuu로 메시지를 전달한다면 jj의 메시지는 uu에게 중복 전달하게 된다.
  • 부분적으로는 이러한 문제점이 크게 나타날 것 같지만 실제로는 전체 구조가 매우 크고 복잡하여 Loopy BP 알고리즘은 잘 작동한다.

References

0개의 댓글