Chapter6. Message Passing and Node Classification
투빅스 12기 배유나
Last updated
투빅스 12기 배유나
Last updated
Main Question
네트워크 상 몇 노드는 라벨을 알고, 몇 노드는 모른다면 알려지지 않은 노드의 라벨을 어떻게 정할 수 있을까?
Relational Classification
Iterative Classification
Belief Propagation
네트워크 안에서 각 개인들은 서로 연결(관) correlated되어 있다.
비슷한 성격의 사람끼리 모여(연결)되어 있다.
집단 안은 서로 영향을 끼쳐 비슷한 성격을 지닌다.
→ 두 요소(external factor)로 환경이 형성된다.
Homophily
the tendency of individuals to associate and bond with similar others
ex) 비슷한 음악취향을 지닌 사람들끼리 사회적 연대를 형성한다.
Influence
social connections can influence the individual
ex) 자신의 음악적 취향을 친구에게 추천하여 비슷한 취향을 가지게 된다.
비슷한 노드들은 일반적으로 가까이 있거나 직접적으로 연결되어있다.
"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 기법을 사용한다.
Y_i : 이웃 노드들의 클래스 확률 평균합
라벨 있는 노드 : 라벨 값으로 초기화
라벨 없는 노드 : 랜덤 (통일) 초기화
4번 노드는 라벨링 되지 않음.
→ not guaranted enabled to reach a decision
위의 예시는 그래프가 작아서 잘 되었지만,
그래프가 커지거나 할 경우 취약한 방식이라고 함.
→ Do not user node attributes
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는 같은 라벨이므로 매우 높은 상관성을 가졌을 것이다.
주변 라벨의 벡터 정보까지 반영!
네트워크 피쳐를 업데이트
리뷰어, 리뷰, 매장 사이의 관계를 찾아내어 그래프 구조로 사기꾼을 찾는다.
초기화 1
계속 반복 ~
Guaranteed to converge
iter가 늘고 node가 많아지면 시감이 오래걸린다.
그래프 모델에서 조건부 확률로 답을 구해내는 접근방식
주변 노드만 연결 : 매우 큰 넽웤에서 실행하기위한 간단한 알고리즘만들기 위해
쉬운 방식이나 닫힌 루프가 많을 경우 수렴되지 않을 수 있다 .
실제 사용: 온라인 경매 사기
평가 점수가 있음 Feedback Mechanism 사용
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
