[CS224W] Message Passing and Node classification

 

1️⃣  5강 복습 

---

 

🔹Main Topic : Node classification 

 

 

•  몇개의 노드에 레이블이 주어질 때, 다른 모든 노드의 레이블을 예측하는 node classification Task 

 

👉 Semi supervised node classification : 라벨링된 노드와 그렇지 않은 노드를 동시에 사용하는 분류문제 

 

•  Message Passing 방법을 통해 노드 간의 correlation (dependencies) 을 가정하여 레이블을 예측한다. 

 

•  correlation : 비슷한 노드는 직접적으로 연결되어 있거나 근접한 위치에 존재한다는 의미로, 주변 노드가 같은 레이블에 속할 때 상관관계가 존재한다고 말할 수 있다. 

 

•  Applications : 문서 분류, 품사태깅, link prediction, OCR, 3D data segmentation, fraud detection 

 

 

🔹 Overview of collective classification 

 

•  분류를 위해 사용하는 네트워크 정보 

↪ Features of node v 

↪ Labels of the nodes in v's neighborhood 

↪ Features of the nodes in v's neighborhood 

 

•  Markov Assumtion 

↪ 노드 레이블은 주변 노드의 레이블에만 영향을 받는다. 

 

 

•  3 step 

 

↪  Local Classifier : Initial label assignment. 노드 피처를 기반으로 레이블을 초기화 한다. 

 

↪  Relational Classifier : Capture correlations. 이웃 노드의 피처와 라벨 정보로 노드 간 상관관계를 파악한다. 

 

↪  Collective Inference : Propagate the correlations. 상관관계를 네트워크에 전파한다. 

 

 

🔹 Relational classification 

•  v 의 이웃노드들의 클래스 확률 (class probability Yv) 들의 가중평균으로 v 노드의 클래스 확률을 구한다. 

•  레이블이 되지 않은 노드는 Yv 를 0.5로 초기화한다. 

•  For each node v and label c : 노드 v 가 class c 로 할당 될 확률 

 

•  Update 예시 

 

🔹 Iterative classification

 

•  Relational classifier 는 노드의 라벨과 엣지와 같은 정보만을 활용하며, 노드의 속성 (attributes, features) 는 사용하지 않는다. 

•  Iterative classification 은 노드의 feature 정보 f(v) 와 이웃 노드의 라벨 z(v) 을 기반으로 해서 노드를 분류한다 👉 Train Two classifiers 

 

 

•  예제 

 

(1) Train classifier

(2) Apply classifier to test 

(3) Iterate 

    1. update relational features z(v) 

    2. update label Yv 

 

 

 

 

🔹 Belief propagation

•  동적 프로그래밍 (dynamic programming) 접근법을 사용하여 특정 클래스에 속할 확률값을 구하는 접근 방법으로, 반복적으로 이웃노드와 talk 하면서 message 를 passing 한다. 

 

 

•  Message Passing Algorithm

 

(1) 노드의 순서를 정의 

(2) 엣지의 방향을 정의 

(3) 이전 노드로부터 메시지를 전달받고 현재 노드에서 메시지를 업데이트 하여 앞의 노드로 전달 

 

 

•  message passing 은 path graph (일방향 그래프 모양) 뿐 아니라 트리 구조에도 적용이 가능하다. 

 

•  Loopy BP algorithm 

 

 

(1) 노드 i 가 이웃들로부터 beliefs 를 수집하고 

(2) node i 가 Y_i 레이블을 가질 확률을 곱하고 

(3) i 의 레이블이 얼마나 이웃 노드 j 의 레이블에 영향을 미칠지, 노드 j 에게 전달하기 위해 label potential matrix 를 곱한다. 

(4) 이 과정을 각 레이블 Y_i 마다 반복한다. 

(5) 수렴을 통해 구해지는 노드 i 의 클래스가 Y_i 일 belief bi(Yi) 는 prior 확률에 belief 를 곱함으로써 구해진다. 

 

 

 

2️⃣  코드리뷰 

---

 

https://colab.research.google.com/drive/1HjC0bCFJQrEKfl_NmH-NV1qRw7pgYEth?usp=sharing 

cs224w 5강 복습과제.ipynb

 

 

 

🔹 Iterative classification algorithm Review 

 

•  Task : Classify nodes in the e-mail exchange graph to company management levels 

•  Class : company management levels (1,2,3) 

•  Data : 2010년 1월 1일부터 2010년 9월 30일까지 중간 규모 제조 회사 직원 간의 이메일 교환에 대한 메타데이터가 포함되어 있으며 , 조직 계층을 나타내는 그래프가 함께 제공된다. 

 

 

 

💡 Semi-supervsied classification 

 

↪ Known , Unknown 

 

 

 

 

💡 노드의 feature 정보 f(v) 와 이웃 노드의 라벨 z(v) 을 기반으로 해서 노드를 분류

 

↪ f(v) : 이메일 수신여부(0,1), 송신여부(0,1), 노드 degree, 노드 중심도 betweenness, 노드 중심도 closeness

↪ z(v) : 이웃노드1 레이블, 이웃노드2 레이블, 이웃노드3 레이블 

 

 

※ http://www.incodom.kr/Betweenness_Centrality

생물정보 전문위키, 인코덤

 

 

💡 Apply 

 

(1) Train classifier

 

 

(2) Apply classifier to test  , Iterate 

 

 

(3) Result