Chapter6. Message Passing and Node Classification

투빅스 12기 배유나

Main Question

네트워크 상 몇 노드는 라벨을 알고, 몇 노드는 모른다면 알려지지 않은 노드의 라벨을 어떻게 정할 수 있을까?

1. Relational Classification

2. Iterative Classification

3. Belief Propagation

1. Relational Classification

Correaltions Exist in Networks

네트워크 안에서 각 개인들은 서로 연결(관) correlated되어 있다.

비슷한 성격의 사람끼리 모여(연결)되어 있다.

집단 안은 서로 영향을 끼쳐 비슷한 성격을 지닌다.

→ 두 요소(external factor)로 환경이 형성된다.

Homophily

the tendency of individuals to associate and bond with similar others

ex) 비슷한 음악취향을 지닌 사람들끼리 사회적 연대를 형성한다.

Influence

social connections can influence the individual

ex) 자신의 음악적 취향을 친구에게 추천하여 비슷한 취향을 가지게 된다.

Correlations Exists in Networks

비슷한 노드들은 일반적으로 가까이 있거나 직접적으로 연결되어있다.

"Guilt-by-association" :

if i am connected to a node with label X,

then i am likely to have label X as well

Collective Classification

simultaneous classification of interlinked nodes using correlations

1) Local Classifier

initial label assignment

노드 속성을 사용하여 라벨을 예측함

네트워크 정보를 사용하지 않음

2) Relational Classifier

Capture correlations based on the network

이웃 노드 라벨, 속성을 참조하여 라벨 분류기를 배움

네트워크 정보를 사용함

3) Collective Inference

propagate the correlation

Apply relational classifier to each node iteratively

Iterate until the inconsistency between neighboring labels is minimized

network structure substantially affects the final prediction

Exact inference 특정 조건을 만족하는 넽웤에서 실용적이고

exact 방법은 노드가 많을 수록 너무 많은 시간이 소요되므로,

propagation의 범위를 줄여가는 방식의 approximate 기법을 사용한다.

Probabilistic relational classifier example

Y_i : 이웃 노드들의 클래스 확률 평균합

라벨 있는 노드 : 라벨 값으로 초기화

라벨 없는 노드 : 랜덤 (통일) 초기화

4번 노드는 라벨링 되지 않음.

→ not guaranted enabled to reach a decision

위의 예시는 그래프가 작아서 잘 되었지만,

그래프가 커지거나 할 경우 취약한 방식이라고 함.

→ Do not user node attributes

2. Iterative classification

Classify node i based on its attrubutes as well as labels of neighbor set N_i

Bootstrap phase

convert each node i to a flat vector a_i

use local classifier f(a_i) to compute best values for Y_i

Iteration phase

수렴할 때까지 반복

update node vector a_i

update label Y_i to f(a_i)

Convergence is not guaranteed

좌측 B는 같은 라벨이므로 매우 높은 상관성을 가졌을 것이다.

주변 라벨의 벡터 정보까지 반영!

네트워크 피쳐를 업데이트

Application of iterative classification framework : fake reviewer/ revirew detection

리뷰어, 리뷰, 매장 사이의 관계를 찾아내어 그래프 구조로 사기꾼을 찾는다.

초기화 1

계속 반복 ~

Guaranteed to converge

iter가 늘고 node가 많아지면 시감이 오래걸린다.

3. Loopy belief propagation

그래프 모델에서 조건부 확률로 답을 구해내는 접근방식

주변 노드만 연결 : 매우 큰 넽웤에서 실행하기위한 간단한 알고리즘만들기 위해

쉬운 방식이나 닫힌 루프가 많을 경우 수렴되지 않을 수 있다 .

실제 사용: 온라인 경매 사기

평가 점수가 있음 Feedback Mechanism 사용

Conclusion

1. Relational models

weighted average of neighborhood properties

cannot take node attributes while labeling

2. iterative classification

update each node's label using own and neihbor's labels

can consider node attributes while labeling

3. Belief propagation

message passing to update each node's belief of itself based on neighbors' beliefs

지난 주 내용 보충 전체적 정리