[Study]Chapter 5. Label Propagation for Node Classification
해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.
I. Message Passing and Node Classification
그래프에서 노드에 label이 부분적으로 할당되어있으면 다른 노드들은 label을 어떻게 할당해야하는가?
Fugyre 5-1 : 좌측 그림과 같이 label이 지정된 몇몇의 노드가 주어졌을때, label이 없는 노드들의 label을 예측한다. 이러한 분류를 semi-supervised 라고 부른다.
Node Classification은 그래프 안에서 연관관계(유사한 노드들은 연결)가 존재하는데, 핵심은 같은 집단으로 분류된 모든 노드에 동일한 label을 부여하는것입니다.
그래프에서 개별 활동은 상호 연관(근처 노드들은 같은 색상)되어 있습니다.
- 동종 선호\(_{Homophily}\) : 각각의 유사한 것들끼리 연관되고 묶이도록 되는 경향
- ex) 같은 취미를 가진 사람들은 동종 선호로 인해 더 가까운 연결 관계
- 영향\(_{Influence}\) : 소셜 연결은 사람의 개인의 성질에 영향
- ex) 같은 장르를 좋아하는 사람에게 어떤 영화를 추천
여기서 그래프에서 노드 라벨을 예측하는데 도움이되는 상호연관의 영향력\(_{leverage}\)을 관찰할 수 있을까?
1. Motivation
- Guilt-by-association : 특정 노드와 연결되어있다면, 노드가 가지고있는 것들을 좋아함
- 특징에 의존 : 노드 특징, 노드 이웃들의 라벨, 노드 이웃들의 특징 등에 의존하여 라벨을 분류
이렇게 그래프안에 동종 선호가 존재한다고 가정하고, 부분적인 정보를 가지고 나머지 Label이 각 class와 얼마나 일치하는지 예측하는 semi-supervised learning 방법을 사용한다.
2. Approach
집단 분류\(_{Collective-classification}\)의 방법으로 상호 연결된 노드들의 상관관계를 이용하여 동시에 분류하는 것이다. 확률 Framework로 아래와 같이 v의 라벨은 노드 v의 이웃들에 의존하는 마코브 가정을 사용한다.
\[P(Y_v) = P(Y_v|N_v)\]집단 분류는 아래와 같은 3가지를 포함한다.
- 로컬 분류기; Local classifier
- 초기 라벨 배정; 노드의 속성과 특징을 가지고(그래프 정보 없이) 예측하는 작업
- 관계 분류기; relational classifier
- 노드간의 관계를 수집; 이웃의 정보(그래프 정보)를 가지고 학습 시킴.
- 집단 추론; collective inference
- 관계 전달; 관계 분류기를 적용하여 이웃 라벨의 일관성이 최대화
이제 우리는 네트워크와 모든 특징이 주어졌을때 \(P(Y_v)\)를 찾아야한다.
II. Relational classifiers
기본적인 아이디어로 Node의 분류 확률 \(P(Y_v)\)는 이웃 노드들의 클래스 확률의 가중 평균과 같다고 생각하는 것이다.
Figure 2 : \(A_{u,v}\)는 v와 u사이 edge의 가중치
1. Step
Figure 3 : label이 지정되어 있지 않는 노드들의 확률 값을 0.5로 초기화하고, Figure 2를 기반으로 업데이트
Figure 4 : Iterate until convergence
2. Limitaion
모델이 노드의 feature 정보를 사용할 수 없어 수렴이 보장되지 않는다.
III. Iterative classification
Relational classifier의 한계를 극복하고자 이웃 노드들의 labels($z_v$)과 feature($f_v$)를 입력으로 사용하여 라벨을 예측한다.
1. How to work?
아래와 같은 2개의 classifier를 학습시킴으로써 작동한다.
- $\phi_1(f_v)$ : local classifier; 특징 벡터($f_v$) 기반으로 라벨 예측
- $\phi_2(f_v,z_v)$ : summary($z_v$)와 $f_v$를 이용하여 라벨 예측
- $z_v$ : 이웃 노드들의 label 정보 벡터표현으로 다양한 방법을 사용 가능.
- ex. most common label, number of different labels, …
2. Steps
Train Phase.
Figure 5 : 먼저, 학습 데이터에 주어진 특징 벡터($f_v$)를 이용하여 $Y_v$를 예측하는 $\phi_1(f_v)$($\phi_1(\cdot)$: SVM, NN 등)를 학습시키고 $f_v$와 summary $z_v$를 이용하여 $Y_v$를 예측하는 $\phi_2(f_v,z_v)$를 학습함
Test Phase.
Figure 6 : $\phi_1(f_v)$를 이용하여 초기 라벨을 한번만(특징 벡터는 변하지 않기에) 예측한 후 summary $z_v$)를 계산하여 $\phi_2(f_v,z_v)$를 이용해 $Y_v$를 예측을 수렴할때까지 반복함
IV. Loopy Belief Propagation
해당 방법의 주된 핵심은 아래와 같다.
“내가 속할 확률은 너가 속할 가능성과 같다고 믿습니다.“ → belief
이러한 방식은 신뢰 전달\(_{Belief-Propagation}\)로 그래프에서 확률적 쿼리를 동적 프로그래밍 접근법으로 해결한다.
Figure 7 : 각 이웃 노드로부터 정보를 받다보면, 먼 노드까지 정보 전달(messages passing)이 가능하고 신뢰를 계산 가능하다.
이러한 메시지 패싱을 잎에서 root로 전달하는 순서의 트리 구조 그래프로 변환하여 수행할 수도 있다.
Figure 8 : 트리 구조 그래프의 메시지 패싱
1. Notation
- $\psi$ : Label-label 잠재 행렬로 노드와 이웃 사이의 의존성 행렬이다.
- $\phi(Y_i)$ : Prior belief; node i가 state $Y_i$에 속할 확률
- $m_{i \to j}(Y_j)$ : i로 부터 j의 상태($Y_j$)에 대한 message
- $L$ : 모든 classes/labels의 집합
2. Steps
- 모든 messages를 1로 초기화.
각각의 노드에 대해 아래와 같이 messages의 업데이트를 반복.
Figure 9 : 메시지는 이전 메시지들의 곱과 (i,j) 상관행렬, i의 사전확률의 곱으로 이루어졌다. 초록색영역은 노드 i가 $Y_i$ 상태에 있을 때, 노드 j가 $Y_j$에 속할 확률과 비례한 i,j 의 상관행렬로도 볼 수 있음.
- 위 과정으로 메시지가 수렴하면 belief를 계산 가능.
1
2
_Figure 10 : belief는 state($Y_i$;class)에 속할 사전 확률과 이웃 메시지들의 곱으로 이루어져있다._
3. Limitation
만약 그래프에 cycle이 존재한다면 메시지들은 BP를 실행할 수 있지만 메시지는 더 이상 독립적이지 않아 루프를 돌게 된다.
즉, Belief가 수렴하지 않을것이다.
그러나 실제로 Loopy BP는 여전히 많은 가지를 포함한 복잡한 그래프에서 heuristic하기 좋다.
Figure 11 : 메시지들이 독립적인 것처럼 곱해지지만 cycle을 통해 비독립적으로 영향을 받게되어 변수가 잘못되어도 확신하면서 계속할 것이다.
4. Property
| Advantages | Challenges |
|---|---|
| - 구현하기 쉬움 - 어떤 graph model에도 적용할 수 있음 | - 수렴이 보장되지 않음 - 특히 closed loops가 많을 때 수렴이 어려움 |