[CS224W] 6. Message Passing and Node Classification

6강은 갓재빈님께서 리뷰하셨습니다. 6강의 핵심은 node의 label 이 몇 개에만 부여되어있을 때 나머지는 어떻게 label을 부여할까? 입니다. 일종의 semi-supervised learning node classification에 대한 내용을 다뤘습니다. 어떤 네트워크에서 어떤 노드는 진짜이고, 어떤 노드는 사기꾼일 때, 다른 노드들은 무엇일지 분류하는 것도 한 가지 예시로 볼 수 있습니다.

목차

0. Intro
1. Collective Classification
2. Relational Classification
3. Iterative Classification
    - Web page Classificaion
    - Application for iterative classification framework : fake reviewer / review detection
4. Belief Propagation
    - NetProbe : Online Auction Fraud

 

0. Intro

Main Question & How

Network에서 몇 개의 node에만 label 이 있고, 몇 개에는 없어서 모르는 node의 label을 부여해주고 싶다! semi-supervised node classification -> Collective Classification(집단분류) 이용! 

 

 

1. Collective Classification

Network에는 Correlation이 존재할 것이기 때문에, 이를 이용해서 node에 label을 부여하자!

• 오늘 배울 방법론
  • Relational classification
  • Iterative classification
  • Belief propagation

Correlations Exist in Networks

correlation을 이용하는 것이 가장 간단한 방법 중 하나입니다. correlation의 3가지 양상은 다음과 같습니다.

(오) Real social network ->  node = 사람 / edge = friendship / color = 인종

• Homophily
  • 'Birds of a feather flock together' 새 깃털은 끼리끼리 뭉친다. -> 유유상종
  • ex. age, gender, organization roles ... 
  • 힙합을 좋아하는 사람들은 서로 연결되어 있다. (힙합 공연을 같이 가거나...노래를 추천해준다...)
• Influence
  • 사회적 연결(social connection)이 개인에게 영향을 미친다.
  • 내가 힙합만 듣고 추천해서 재빈언니가 힙합을 좋아하게 됨!
• Confounding
  • 교란 변수 : individual characteristics와 social connections에 동시에 영향을 주는 environment

 

Classification with Network Data

• How do we leverage this correlation observed in networks to help predict node labels?
• How do we predict the labels for the nodes in beige? (기본적으로 한 class 당 하나의 분류기를 훈련시킬 것

Guilt - by association

• 비슷한 노드끼리 인접하거나 연결되어 있음
• '내가 투빅스 사람들하고 연결된 사람이면, 나도 투빅스 사람일 확률이 크다!'
• 악성 페이지들은 서로 연결되어있다. (page rank 관련)

Classification label (node v label 이 영향을 받는 것)

• Features of v
• Labels of the nodes in v's neighborhood
• Features of the nodes in v's neighborhood

 

Collective classification overview

- Intuition : Simultaneous classification of interlinked nodes using correlations

- Markov Assumption : v 노드의 이웃 노드에 모든 정보가 함축되어 있다고 생각하고, v에 연결된 neighbor 정보를 고려함

- Process (3 steps)

1. Local Classifier : Used for initial label assignment
   • 노드 속성을 기반으로 label을 예측
   • 전형적인 classification task 
   • network의 정보 사용하지 않음
2. Relational Classifer : Capture correlations
   • 이웃의 label이나 속성(attribute)을 기반으로 label을 예측
   • network 정보 사용
3. Collective Inference : Propagate the correlation
   • 상관관계 전파
   • 각 노드마다 relational classifier를 반복적으로 적용
   • 인접한 이웃 정보만 사용하는 것이 아니라, 이웃에게 전달된 correlation을 사용해서 전체 network 정보파악이 가능해집니다. 
   • 네트워크 구조가 예측에 영향을 주게됩니다.

 

- Collective Classification 은 iterative하게 진행되며, 근사적인 접근 방법입니다. (Exact inference는 특정조건에서만 사용되고, NP-hard 문제가 있음)

• iterative : 이웃간의 label 불일치가 최소화될 때 까지 반복합니다.
• approximate inference : propagation 진행될 때 neighborhood 범위를 점점 좁힙니다. 

 

- several applications

• Document classification
• Part of speech tagging
• Link prediction
• Optical character recognition
• Image/3D data segmentation
• Entity resolution in sensor networks
• Spam and fraud detection

 

---

 

2. Relational Classification

setting

• node i 의 label Y_i를 예측하기
• 각 node i 는 feature vector f_i를 가진다.
• 몇 노드는 label이 있음 
• Task : Find P(Yi) given all features and network

 

Idea

Y_i의 class probability 는 node i 의 이웃의 class probability를 평균한 값이다.

Initialize

• labeled node : ground-truth Y label로 초기화
• unlabeled node : uniformly 하게 초기화

Update 

수렴하거나 최대 iteration수 까지 모든 노드들을 random order로 업데이트(정확한 이유는 모르지만, 노드의 업데이트 순서가 결과에 영향을 주기는 함)

Repeat

(오) 정규화 하는 경우

 

Example

1. 각 노드들을 초기화시킵니다. 

2. Update for the 1st Iteration -> Node 3, 4, 5 를 업데이트

3. Ater Iteration 1 ~ 4

4. All Scores stabilize after 5 iterations -> 점수가 안정화되어서 멈춤

node 5, 8, 9 는 + 이다. (P(Y_i=1) > 0.5)

node 3 은 - 이다. (P(Y_i=1) < 0.5)

node 4는 중간 +/-  (P(Y_i=1) = 0.5)

 

 

Challenges

• 수렴이 보장되지 않음, 그래프(네트워크)가 커지면 더 잘 안됨
• node feature 정보는 전혀 사용하지 않음 (-> 개선한 것이 Iterative Classification!)

 

---

 

3. Iterative Classification

node i 의 attribute 와 이웃의 label 모두 고려하는 방법입니다. 

• 각 노드 i 마다 flat vector a_i 를 만든다.
• a_i를 사용해서 classifier를 학습시킨다. (train)
• 노드별로 매우 다양한 이웃 노드들이 있기 때문에 aggregate 방법론을 다양한 사용한다. (count, mode, proportion, mean, exists...)

 

Process

Bootstrap phase

• 각 노드 i 를 flat vector a_i로 변환
• local classifier f(a_i)를 사용해서 Y_i에 대한 best value 계산 (분류)
• local classifier로는 SVM, knn 등의 알고리즘 사용가능

Iteration phase

• Repeat : 각각의 node i 에 대해 다음 과정을 반복합니다.
  • node vector a_i​ 를 update 합니다.
  • f(a_i​) 에 대해 label Y_i​를 update 합니다.
• Iterate : class label이 stabilize 되거나 최대 iteration 횟수가 만족될 때까지 반복합니다. (수렴이 보장되지 않으므로, 최대횟수 반복하세요)

 

Approach : Train two classifiers

접근할 때 두 가지 방법이 있는데, 1️⃣node가 가진 정보인 feature vector f_z 에만 의존해서 node label을 예측하는 방법이 있고, 2️⃣v의 이웃 label을 요약한 z_v와 feature vector f_z  모두를 사용하는 방법이 있습니다. 

 

Example : Web page Classification

웹페이지를 A, B로 분류하는 task 가 있습니다. 그래서 페이지 안에 word 정보(w1, w2, w3)로 분류를 했더니 '1 0 1' 로똑같은 정보인데도 A로 분류된 페이지가 있었습니다. 이를 Iterative Classification 으로 개선해봅시다.

 v의 이웃 label을 요약한 z_v와 feature vector f_z 모두를 사용하는 2️⃣ 방법입니다. 

과정요약
1. Train classifier
2. Apply classifier to test set 
3. Iterate
    - Update relational features z_v
    - Update label Y_v

 

 

1. Training set : 각 노드를 flat vector 로 바꿔줍니다. 이웃의 label 정보를 포함한 벡터도 포함합니다. (In & Out)

이 때 두 가지 classifier를 사용합니다. word vector 만을 사용하는 분류기, word vector 와 link vector를 사용하는 분류기

 

2. Test set : 먼저 word-vector (feature vector)만으로 학습된 분류기1를 사용해서 test set에 bootstrap을 진행합니다 (이 때는 잘못된 분류가 되는 것을 볼 수 있습니다.)

 

3. Test set : 이제 Iterate를 진행합니다. 모든 노드들에 대해서 neighborhood vector 를 넣어서 update 해줍니다. 그리고 다시 분류합니다. (이 때는 노드 정보 + 이웃 정보인 벡터를 사용하니깐 분류기2를 사용할 것 입니다.)

이번에는 B로 잘 분류

 

4. Test set : 벡터들이 수렴할 때 까지 반복합니다. 

최종엔 Correct!  

 

---

REV2 : Fake Review Detection

iterative classification을 사용하는 추가 예시를 하나 더 보겠습니다. 

• Review Site에서는 spam이 공공연하게 발생합니다.
  • 평점이 하나 높아질수록, 수입이 5~9% 상승합니다.
  • Paid Spammers는 거짓으로 해당 상품들의 평가를 낮게 평가함으로써, 경쟁사를 꺾으려고 합니다.
• Behavioral analysis, Language Analysis 만으로는 Spammer를 판별하기 어려운데, Individual Behavior 이나 Content of Review 는 거짓으로 보여주기 쉽기 때문입니다.
• 따라서, 쉽게 속이기 어려운 graph structure 를 통해 Reviewers, Reviews, Stores 사이의 relationship 을 파악하고자 합니다.

Input으로 bipartite rating graph가 들어가면 output으로 fake rating을 준 악질 유저 집합이 나오는 구조입니다.

Intrinsic Properties

1. Users have fairness scores
   사기꾼들은 좋은 상품에 낮은 평점, 나쁜 상품에 좋은 평점을 줄 것입니다.
2. Products have goodness scores
   좋은 상품의 평점은 좋을 것입니다.
3. Ratings have reliability scores
   reliability ​= fairness : user는 bias가 있습니다.
   개인적인 의견이 다수의 의견과 일치하지 않을 수 있습니다.

   Axiom

   1. Better Products get higher ratings.
   2. Better products get more reliable positive ratings.
   3. Reliable ratings are closer to goodness scores.
   4. Reliable ratings are given by fairer users.
   5. Fairer users give more reliable ratings.

 

Iterative Classification

Iterative Classification에 사용하는 vector로 Fairness of Users, Goodness of Products, Reliability of Ratings 이 있습니다. 다음과 같이 정의하고, Itererative Classification에 따라서 Update를 진행합니다.  

• Fairness of Users : goodness와 reliability를 고정시키고, fairness를 update 합니다.
• Goodness of Products : fairness와 reliability를 고정시키고, goodness를 update 합니다.
• Reliability of Ratings : fairness와 goodness를 고정시키고, reliability를 update 합니다.

F & G

F와 G를 이용한 Reliability

 

1. Initialization

 

2. Iteration 1 -> F, G, R Update

(눌러서 크게 확대하세요)

 

3. After convergence

Faireness 가 낮은 유저가 Fraudster입니다.

 

Properties of REV2 Solution

• REV2는 수렴이 보장되어 있습니다.
• 수렴하기까지 총 Iteration 횟수의 상한선이 존재합니다.
• 시간복잡도는 그래프의 Edge의 수가 증가함에 따라 Linear하게 증가합니다.
• 위에서 다루지는 않았지만, Laplace Smoothing을 통해 cold start problem도 해결합니다.

cold start problem : 추천시스텝에서 정보가 아예 없는 유저들이 있어서 생기는 문제

 

---

 

4. Belief Propagation

마지막으로 Belief Propagation은 message passing 에서 고안한 것으로 dynamic programming 접근 방식입니다. graph model에서 조건부 확률로 답을 구해냅니다. Loopy Belief Propagation 을 알아보겠습니다.

(이 부분은 스터디 내용과 거의 동일합니다.)

 

Message Passing

• Task : graph 에서 node의 개수 세기
• Condition : 각 node들은 그들의 neighbors와만 interact 할 수 있습니다.
• Solution : 각 node들은 그들의 neighbor로 부터 message를 전달받고, 이를 update 하여, 앞으로 전달합니다.

 

 

Message Passing in Trees

따라서 전달된 (Passing a belief) 두 정보를 종합하여, 7+3+3+1=14 라는 과정을 통해 총 node의 개수는 14개가 될 것이라는 Belief Propagation 을 내리게 됩니다.

그래프가 cycle 이면 작동하지 않습니다.

 

 

 

 

 

 

 

---

 

Loopy Belief Propagation (Loopy BP algorithm)

i는 j에게 message를 보낼 때, 주변 이웃 k들에게서 들은 내용을 전달합니다. 

-> 이웃 k는 i에게 belief state를 전달합니다.

 

 

 

 

 

 

 

1. 모든 message(m)을 1로 초기화 한 후, 각 노드에 대해 다음을 반복합니다.

 

2. 수렴하면, 각 state에 대한 belief b_i (Y_i)를 계산합니다. 

 

 

역시 cyclic graph에서 사용할 수 없습니다. 

 

Summary

1. Advantages
   • 프로그래밍 및 병렬화가 쉽습니다.
   • 어떤 그래프 모델보다도 general하게 적용 가능합니다. (+ higher order than pairwise)
2. Challenges
   • 수렴이 보장되지 않습니다.
   • 특히 많은 closed loop가 있는 경우, 적용이 어렵습니다.
     (Clustering Coef를 확인해 보고, Belief Propagation 적용 가능성을 검토해 볼 수 있습니다.)
3. Potential Functions
   • parameter 추정을 위해 train이 필요합니다.
   • gradient-based 최적화가 진행됩니다.

 

---

NetProbe : Online Auction Fraud

Online Auction Fraud

• 경매 사이트는 사기 치기에 상당히 매력적인 장소입니다.
  종종 상품 배달을 못 받았다는 사기를 치곤 하며, 이러한 사기 사건 하나 당 발생하는 평균 손실 비용이 $385 라고 합니다.
• 단순 individual feature (user attributes, geographic locations, login times, session history, etc) 만으로 사기꾼을 탐지하기는 어렵습니다.
• 따라서 graph structure 을 구성하여, user 사이의 relationship 을 캐치하여 사기꾼을 탐지하고자 합니다.

 

Role of Users

fraudster : 사기꾼 / accomplice : 공범 / honest : 선량한 시민들

• 경매 사이트에는 Reputation System 이 존재합니다.
• 사기꾼들끼리는 서로의 Reputation Score를 올려 주지 않는데, 한 명이 걸리게 되면 다 같이 걸리게 되기 때문입니다.
• 따라서 near-bipartite graph를 형성합니다.
  • accomplice
    • perfectly 하게 정상적인 것 처럼 보이는 user를 말하며, honest와 거래하며 high feedback rating 얻습니다.
    • fraudster의 feedback rating 을 올려줍니다.
  • fraudster
    • accomplice 와 거래하며, honest 에게 사기를 칩니다.
• 사기를 치고 나면, fraudster는 사기 현장을 떠나고, accomplice는 사기 현장에 남아 다음 사기를 치는 것을 도와줍니다.

 

Detecting Auction Fraud

Markov Random Field & Belief Propagation

 

 

• 해당 논문에서의 ϵp​ = 0.05 입니다.
• 즉, 노란색으로 칠한 값이 heavily linked 된 관계를 나타냅니다.
• Intuition
  • fraudster 는 accomplice와 heavily link 되어 있으나, 다른 bad node와의 연결은 피하는 양상입니다.
  • accomplice 는 fraudster 와 honest 모두와 연결되어 있으며, 특히 fraudster와 더 잘 연결되어 있습니다.
  • honest 는 accomplice와 다른 honest와 연결되어 있습니다.

 

Process

(오) 최종 분류된 모습

1. fraudster, accomplice, honest 확률값을 모두 같게 initialize 합니다.
2. 각각의 node는 iteratively 하게 message를 pass하며, belief를 update 합니다.
3. ψ(σ,σ′) 에 따르면, iteration 1 이후의 node는 accomplice 가 될 가능성이 높습니다. accomplice 로 분류된 node에 대해서, 이웃을 fraud 혹은 honest 로 두고, 값을 계속적으로 update 합니다.
4. 수렴할 때 까지 update 합니다.

 

 

Reference

Stanford CS224W 2019
스터디 6강 리뷰 자료 velog.io/@tobigs-gnn1213/6.-Message-Passing-and-Node-Classification

6. Message Passing and Node Classification

👇🏻스터디 6강의 리뷰자료 (되게 많길래 링크 올립니다.)

Reference

1. Tobigs Graph Study : Chapter 6. Message Passing and Node Classification
2. 데이터 괴짜님 Review : CS224W - 06.Message Passing and Node Classification
3. snap-stanford Review : Message Passing and Node Classification
4. CS224W Winter 2021 : 5. Label Propagation for Node Classification

---

1. REV2: Fraudulent User Prediction in Rating Platforms
2. NetProbe : A Fast and Scalable System for Fraud Detection in Online Auction Networks
3. Collective Classification in Network Data

---

1. Semi-supervised Learning(준지도학습) - Overview
2. Confounding Variable: Simple Definition and Example