# Chapter6. Message Passing and Node Classification

**Main Question** 

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

![](/files/-M5ANUQGcWkJHkotPD2w)

1. **Relational Classification**
2. **Iterative Classification**
3. **Belief Propagation**

### 1. Relational Classification

#### Correaltions Exist in Networks

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

![](/files/-M5ANdYzLKjAztcz5bpy)

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

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

→ 두 요소(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

![](/files/-M5ANmEdbDIHIjxqpldP)

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

**"Guilt-by-association"** :

if i am connected to a node with label X,

then i am likely to have label X as well

![](/files/-M5ANs1Br7-g91bj4wTa)

![](/files/-M5ANxEN0gJ_vrxQsyzQ)

**Collective Classification**

simultaneous classification of interlinked nodes using correlations

![](/files/-M5AO3DokYGCP6d25qgH)

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

![](/files/-M5AOH1zWzZQSReLLouN)

Y\_i : 이웃 노드들의 클래스 확률 평균합

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

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

![](/files/-M5AOMu5YFZ9ZCP5iFZu)

![](/files/-M5AOTAnPaNNlRz3hT9o)

![](/files/-M5AOXESUt_R8KWnWHk-)

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*

![](/files/-M5AObtl2NXbiplsIlpt)

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

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

![](/files/-M5AOiJJdD00Bok5P_z8)

![](/files/-M5AOmfS8_MtFedauvMl)

![](/files/-M5AOsbFrwU14ZYcU4rt)

![](/files/-M5AOxd1FsIw3PTJUynY)

![](/files/-M5AP0nzSOXyk8_oSxGN)

![](/files/-M5AP6GBIL6weegSXdJZ)

네트워크 피쳐를 업데이트

![](/files/-M5APDNgRNqh5IIwbVKC)

### Application of iterative classification framework : fake reviewer/ revirew detection

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

![](/files/-M5APOEFlf6SCXeXvaUX)

초기화 1

![](/files/-M5AP_fN1KnGSRGPi7vv)

![](/files/-M5APdsfcxzbBwBj1-SC)

![](/files/-M5APi5aFtfJY4LBTx_S)

![](/files/-M5APm1cK71GWw413TsT)

계속 반복 \~

![](/files/-M5APq2FCBdqVho8M2Dj)

Guaranteed to converge

![](/files/-M5APurKAAxtR1l7005q)

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

## 3. Loopy belief propagation

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

![](/files/-M5APzCmh3Vf5o4E2Say)

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

![](/files/-M5AQ4cuE0YQVGN2oUno)

![](/files/-M5AQBjk892YsSQP9s-G)

![](/files/-M5AQGYofyoPY3oN1vOI)

![](/files/-M5AQO7LMIQtefjAar7q)

![](/files/-M5AQRVEAPehBmgL-8JL)

![](/files/-M5AQVALK4VEdqPlVXvp)

![](/files/-M5AQYZKH65jaXX8cPzM)

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

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

평가 점수가 있음 Feedback Mechanism 사용

![](/files/-M5AQfdbQPAcd1gxuGV5)

![](/files/-M5AQkrEkvbernWfQ4tF)

## 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

![지난 주 내용 보충 전체적 정리](/files/-M5gVqJNGCJWnc7RhoEg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://tobigs.gitbook.io/tobigs-graph-study/chapter6..md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.