작성자 : 이재빈

Contents

0. Intro
1. Relational Classification
2. Iterative Classification
3. Belief Propagation

---

Keyword : Machine Learning applied on Graph, Node Classification

0. Intro

Main Question

Network에서 몇 개의 node에만 label이 달려 있고, 몇 개는 모른다면,
모르는 node의 label을 어떻게 설정해 줄 수 있을까요?

주어진 label을 이용하여, unlabeled node를 예측합니다!
이와 같은 방법론을 semi-supervised node classification 이라고 합니다.

semi-supervised learning

• supervised learning
  관측치마다 정답 label이 달려 있는 데이터셋을 이용하여 학습
  ex. Regression, Classification, Neural Network, ...
• unsupervised learning
  정답 label이 달려 있지 않은 데이터셋을 이용하여, 모델 스스로 학습
  ex. Clustering
• semi-supervised learning
  label이 달려있는 데이터와 label이 달려있지 않은 데이터를 동시에 학습해서, 더 좋은 모델을 만드는 것
  데이터가 군집의 형태를 따르고 있다면, 학습에 도움이 될 것

Network를 구성하고 있는 node 끼리는 Cluster(=Community, Correlation)를 형성하고 있을 것이므로, semi-supervised learning을 통해 unlabeled node를 분류해 보자는 것이 핵심 idea 입니다.

Collective Classification

Network 상에는 Correlation이 존재합니다.
Similar node는 connected 되어 있을 것이고,
이러한 정보를 기반으로 node에 label을 assign 해 주는 것이 collective classification 개념입니다.

Collective Classification Techniques

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

Correlations Exist in Networks

Individual behaviors are correlated in a network environment

1. Homophily

   • 유유상종
   • 비슷한 성향을 가진 사람들끼리, 비슷한 social connection을 형성
   • ex. age, gender, organization roles + AI에 관심 많은 투빅스..

2. Influence

   • 나의 취향을 추천하여, 다른 사람도 좋아하게끔 만드는 것
   • ex. 내가 좋아하는 연예인을 동료한테 매일 보여줬더니 동료도 결국 그 연예인을 좋아하게 되는 것

3. Confounding
   

   • 교란 변수 : individual characteristics와 social connections에 동시에 영향을 주는 environment

correlation 중, homophily에 주목해 node classification을 수행하고자 합니다.

---

Classification with Network Data

How do we leverage this correlation observed in networks to help predict node labels?

Guilt-by-association
If I am connected to a node with label 𝑋, then I am likely to have label 𝑋 as well.
= 내가 투빅스 사람들하고 친구라면, 나도 투빅스 사람일 확률이 크다!

v node label 은 위의 세 가지 요소에 영향을 받게 됩니다.

따라서 node classification task는,
positive / negative / unlabeled node 에서,
unlabeled node 가 positive node가 될 확률을 예측하는 것 입니다.
(cf. logistic regression에서의 p = 1이 될 확률)

---

Collective Classification Overview

Simultaneous classification of interlinked nodes using correlations

• Markov Property : $P(S_t|S_{t-1}, ... , S_1) = P(S_t|S_{t-1})$
• Markov Assumption : neighbor 에 모든 정보가 함축되어 있다고 생각하고, node v에 연결된 neighbor 정보를 고려합니다.

PROCESS

STEP 1. Local Classifier

• 초기 label을 부여합니다.
• node 속성만을 사용해 예측하며, network 정보를 사용하지 않습니다.

STEP 2. Relational Classifier

• correlation 을 capture 합니다.
• neighborhood node의 label, attribute 정보를 사용해 예측합니다.

STEP 3. Collective Inference

• Propagate the Correlation
• 각 node마다 Relational Classifier 를 반복적으로 적용합니다.
• 인접한 neighbor 정보만 사용하는 것이 아니라, neighbor에 전달된 correlation을 사용합니다. 이를 통해 전체 network의 정보를 사용할 수 있게 됩니다.
  (Basically, we do not want to stop at the level of only using our neighbors, but through multiple iterations we want to be able to spread the contribution of other neighbors to each other.)

Collective Classification 은 iterative 하게 진행되며, approximate inference 입니다.

• iterative : neighborhood labels 불일치가 최소화 될 때 까지 반복합니다.
• 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

1. Relational Classification

setting

• idea : $Y_i$의 class probability는 neighbor 노드들의 class probability의 weighted average
• labeled node : ground-truth Y label 로 initialize
• unlabeled node : uniformly 하게 설정합니다. (0.5 or 신뢰할 만한 prior)

training

• update : 수렴할 때 까지 or 최대 iteration 수에 도달하기까지 모든 노드들을 random order로 업데이트 합니다.
• repeat : 모든 node i 와 label c에 대해, 다음 과정을 반복합니다.
  

Example

1. Initialize : node label 에 맞게, 확률값을 초기화 합니다.

2. 1st Iteration : random order 순서대로 update 합니다.

... (node 3→4→5→8→9)

3. Repeat Iteration : 모든 node 가 수렴할 때 까지 or 최대 iteration 수에 도달할 때 까지 반복합니다.

• $P(Y_v) > 0.5$ 인 경우 label = 1, $P(Y_v) < 0.5$ 인 경우 label = 0 으로 분류합니다.
• cf. node 4 : +/- equally contributing → bridge 역할 가능

Challenges

1. convergence 보장되어 있지 않습니다. 위의 예시의 경우 그래프가 작아서 수렴이 잘 되었지만, 그래프 크기가 커지는 경우 취약한 방식이라고 합니다.
2. node feature information을 전혀 사용하지 않습니다.

2. Iterative Classification

idea : node i의 attribute & neighborhood 의 label 모두 고려합니다.
If two objects are related, inferring something about one object can assist inferences about the other.

PROCESS

1. Bootstrap Phase
   • $a_i$ : 각각의 node i 에 대해 flat vector $a_i$ 를 생성합니다.
   • $f(a_i)$ : $a_i$를 local classifier(ex. SVM, KNN, LR) 을 통해 분류합니다.
   • aggregate neighbors : count, mode, proportion, mean, exists 등의 neighborhood information 을 취합합니다.
2. Iteration phase
   • Repeat : 각각의 node i 에 대해 다음 과정을 반복합니다.
     • node vector $a_i$ 를 update 합니다.
     • $f(a_i)$ 에 대해 label $Y_i$를 update 합니다.
   • Iterate : class label이 stabilize 되거나 최대 iteration 횟수가 만족될 때까지 반복합니다.

---

1. $\phi_1(f_v)$ = feature vector 만으로 node label을 예측하는 classifier
2. $\phi_2(f_v, z_v)$ = feature vector + $N_i$ 모두 이용하여 label을 예측하는 classifier

Example : Web Page Classification

0. Setting

   • $f_v$ : feature vector, node의 정보
     (강의에서 소개해 준 feature vector 예시 : Bag-Of-Words)
   • $z_v$ : neighborhood label에 대한 정보 통계량 벡터
     • I : Incoming neighbor label information vector
     • O : Outgoing neighbor label information vector
     • $I_0$ = 1 : 최소 1개의 label 0 노드가 incoming (count)

1. $\phi_1$ 과 $\phi_2$ 를 학습시킵니다.
   

2. feature vector 만으로 classification ($\phi_1$) 을 진행합니다.
   

3. 예측한 label 값에 기반하여, $z_v$를 update 합니다.
   

4. feature vector와 $z_v$를 모두 사용하여 classification ($\phi_2$) 을 진행합니다.
   

5. 수렴할 때 까지 반복합니다.
   

---

REV2 : Fake Review Detection

Fake Review Spam

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

REV2 Solution

1. Setting

• Input : Bipartite rating graph as a weighted signed network
  • node : Users, Products (Items)
  • Edges : [-1, +1] rating scores (Red : -1 & Green : +1)
• Output : 거짓으로 평점을 평가하는 유저 집단

2. Intrinsic Properties
   1. Users have fairness scores
      사기꾼들은 좋은 상품에 낮은 평점, 나쁜 상품에 좋은 평점을 줄 것입니다.
   2. Products have goodness scores
      좋은 상품의 평점은 좋을 것입니다.
   3. Ratings have reliability scores
      reliability $\neq$ fairness : user는 bias가 있습니다.
      개인적인 의견이 다수의 의견과 일치하지 않을 수 있습니다.
3. 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

1. Fairness of Users : goodness와 reliability를 고정시키고, fairness를 update 합니다.
   

2. Goodness of Products : fairness와 reliability를 고정시키고, goodness를 update 합니다.
   

3. Reliability of Ratings : fairness와 goodness를 고정시키고, reliability를 update 합니다.
   

PROCESS

1. Initialize to best scores : F, G, R 값을 모두 1로 초기화합니다.
   

2. Updating goodness
   

3. Update reliability
   

4. Update fairness
   

5. Convergence : Fairness가 낮은 user가 Fraudster 입니다.
   

Properties of REV2 Solution

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

3. Belief Propagation

idea : message passing
dynamic programming 접근 방식으로, graph model에서 조건부 확률로 답을 구해내는 방식입니다.

Message Passing

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

Message Passing in Trees

노란색 node에서 전달된 정보를 토대로 개수를 파악하여, 앞으로 전달합니다.

반대 방향으로 전달할 때에는, 위와 같습니다.

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

다만, graph가 cyclic 한 경우에는 Belief Propagation이 잘 작동하지 않습니다.

---

Loopy Belief Propagation

i는 j에게 message를 보낼 때, 주변 neighbor인 k에게 들은 내용을 전달합니다.
즉, neighbor k는 i에게 belief state를 전달합니다.

Notation

1. $\psi$ : Label-label Potential Matrix

   • node와 neighbor 사이의 dependency
   • $\psi(Y_i, Y_j)$ : 노드 j의 neighbor i가 state $Y_i$에 있을 때, 노드 j가 state $Y_j$에 속할 확률
     = correlation between node i & j

2. $\phi$ : Prior Belief

   • $\phi_i(Y_i)$ : 노드 i가 state $Y_i$에 속할 확률
   • $m_{i→j}(Y_j)$ : j가 state $Y_j$에 있을 때 i의 추정치
     = i's message

3. $L$ : 모든 state의 집합

PROCESS

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

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

Loopy BF는 cyclic graph에서 사용할 수 없습니다. (no longer independent)

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

Main Question : How do fraudsters interact with other users and among each other?

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

Propagation Matrix

$\psi(\sigma, \sigma')$ : the likelihood of a node being in state $\sigma'$ given that it has a neighbor in state $\sigma$

• 해당 논문에서의 $\epsilon_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. $\psi(\sigma, \sigma')$ 에 따르면, iteration 1 이후의 node는 accomplice 가 될 가능성이 높습니다. accomplice 로 분류된 node에 대해서, 이웃을 fraud 혹은 honest 로 두고, 값을 계속적으로 update 합니다.
4. 수렴할 때 까지 update 합니다.

분류가 잘 된 것을 볼 수 있습니다.

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

---

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

---

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