CS224W - 06.Message Passing and Node Classification

in Data on Graph


Message Passing and Node Classification

  • 오늘의 메인 궁금증
    어떤 네트워크가 주여졌을 때, 몇몇 노드들에는 label이 있다면, 그렇지 않은 node들에는 어떻게 label을 설정해줄 수 있을까?
    • ‘Semi-supervised` node classification
      gnn06-1

Collective classification

  • 위와 같이 네트워크 상의 모든 노드들에 label을 assign하는 태스크!
  • Intuition
    네트워크 상에서는 분명 Correlation이 존재하고, 우리는 이 정보를 Leverage 하면 된다!

  • Collective Classification의 세 가지 테크닉

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

    Correlation?

    • Correlation을 낳는 3가지 Dependency

        1. Homophily
          • 비슷한 성향을 지닌 사람들이 사회적인 connection을 형성한다.
          • 유유상종
          • ex. age, gender, organizational role, …
        1. Influence
          • Social connection은 개인들에게 영향을 미친다.
          • 이 강의에서 메인으로 다룰 대상
        1. Confounding
          • 외부적인 요인이 개인 및 social connection 모두에 영향을 미친다.

        gnn06-2

  • (처음의 궁금증으로 돌아와서,) 예를 들어, 다음과 같은 네트워크에서 Beige 색의 노드들에는 어떻게 label을 predict?
    = 어떻게 네트워크 상에서 관찰되는 Correlation을 Leverage 할 것인가?
    gnn06-3
    (이 그림은 Binary Classification이지만, Multiple Classifier도 충분히 가능한 이야기)

  • Motivation
    • 유사한 노드들은 Directly connected 되어 있거나, Close together 이거나!

    • 네트워크 내에서 어떤 object O의 Classification Label은 다음 3가지에 의존할 것

      gnn06-4

  • 위의 Task는 결국 다음과 같은 문제로 귀결될 수 있음.
    • W: nxn (weighted) adjacency matrix
    • Y: Label들의 벡터
      • 1: + node
      • -1: - node
      • 0: unlabeld node
    • 결국, 0인 노드들 중, 어떤 노드들이 1일지를 예측하라는 것.
  • 이 단순한 사고의 다양한 application 사례
    • Document classification
    • Part of speech tagging
    • Link prediction
    • Optical character recognition
    • Image/3D data segmentation
    • Entity resolution in sensor networks
    • Spam and fraud detection

Collective Classification Overview

  • 마코프 가정
    • 어떤 한 노드의 Label은 그 Neighbor 노드의 Label에 의존한다.
  • 3 Steps?
    • Step1. Local Classifier
      초기 label 부여
    • Step2. Relational Classifier
      노드들 간의 correlation을 capture!
    • Step3. Collective Inference
      네트워크를 통해 correlation을 propagate

      gnn06-5

  • Collective Classification을 위해 3가지 테크닉을 사용할 것이며,
    이 3가지(Relational classifiers, Iterative Classification, Belief propagation) 모두 Approximate inference다!
    • 또한, 모두 Iterative algorithm

1. Relational Classifier

  • Idea: 어떤 노드 Yi의 class probability는 neighbor 노드들의 class probability의 가중평균이다!
  • Labeled Node는 ground-truth(실측자료) Y label로 initialize
  • Unlabeld Node는 uniform하게 initialize
    • 물론 믿을만한 prior가 있다면, 당연히 이를 사용해도 괜찮다!

  • 수렴할 때까지 혹은 최대 iteration 수에 도달하기까지 모든 노드들을 random order로 업데이트
    (물론 order가 결과에 영향을 미칠 수 있다는 점은 명심할 것. 작은 Dataset에 대해서는 물론 local effect가 exacerbated 될 것이지만, Dataset의 킉가 크다면 순서가 다름으로써 얻게되는 결과의 label distribution에는 그닥 큰 영향을 미치지는 않을 것

  • 각 node i와 label c에 대해 다음을 반복
    • W(i,j): i → j의 edge strength
    • Ni: Node i의 neighbor들의 수
    • P(Yj = c): i의 neighbor이 label c를 가질 확률
  • 이 방법의 단점
    • 수렴이 보장되지 않는다.
      • Solution: ML에서의 경험적인 해결책
        -> Weight의 Behavior 및 Label의 Distribution을 Plotting 해보고, 이 fluctuation이 시간의 흐름에 따라 증가하지 않는다면 일종의 convergence state에 도달했다고 볼 수 있다.
    • 모델이 Model Feature information을 사용할 수가 없다.
  • 예시
    • Initialize
      gnn06-6
    • 첫번째 Iteration
      • 3 -> 4 -> 5 -> 8 -> 9의 순서로 update하는 것을 가정
        gnn06-7
        gnn06-8
        …
      • 결과
        gnn06-9
        …

    • 이런 과정을 통해 Iteration을 4번 돌았을 때
      gnn06-10

    • Iteration을 다섯번 돌면 Score가 안정되었다고 함
      -> 5번의 Iteration을 통해 Score가 안정되었다는 가정 하에, 0.5라는 값을 기준으로 노드를 Classify!
      gnn06-11
      • 4번 노드는 +,-가 거의 equally contributing → 적절한 label assign을 못함

2. Iterative classification

  • ‘Relational classifier가 그렇게 powerful하지는 않더라.’ (Node feature를 사용하고 있지 않더라.)

  • Neighbor들의 label 뿐만 아니라 attributes 들도 사용하여 classify해보자!

    • 각 노드 i에 대해 flat vector a_i를 만든다
    • a_i를 이용하여 분류할 수 있도록 분류기 학습
    • 노드들마다 다양한 neighbor node의 수를 갖게 됨
      -> count, mode, proportion, mean, exists 등을 사용해서 aggregate할 수 있다.

Basic architecture of iterative classifiers

Bootstrap Phase
  • 각 노드 i를 flat vector a_i로 전환!
  • Y_i에의 최고의 값을 계산해내기 위해, SVM, KNN등 다양한 local classifier f(a_i)를 이용!
Iteration Phase
  • 수렴할 때까지 계속 반복!
    • 각 노드 i에 대해,
      • node vector a_i를 업데이트
      • f(a_i)에 대해 lable Y_i를 업데이트
    • 역시 class label이 stabilize 되거나 최대 iteration 횟수가 만족될 때까지 iterate
    • 하지만, 역시나 convergence가 보장되지는 않기 때문에, max iteration 횟수를 사용

  • 정리하자면

    1. Train
2. Bootstrap 
3. Iterate 
  a. Update relational features 
  b. Classify
  • 예시
    • Web page classification
      • w1, w2, w3, … : Document 내에서 특정 단어의 존재 여부를 나타냄
      • Baseline: 처음 given 네트워크에 대해 Classifier(예: KNN)을 학습!
        gnn06-12
    • 이제, network feature를 감안!!
      • 노드들 사이의 전입, 전출 관계에 따라, 각 노드에 neighborhood label의 벡터를 추가!
      • ex) I_A: A label의 Page로부터 incoming되고 있는 경우!
        gnn06-13

1. Train

  • 각 training set마다, 두 가지 classifier를 train!!!
    1. Word vector만 (초록색)
    2. Word & Link vector (빨간색)

    gnn06-14

2. Bootstrap

  • 1에서 훈련된 모델을 갖고, Test set을 bootstrapping!
    gnn06-15
    gnn06-16

3. Iterate

  • 3-a. Update relational features
    • Relational features 업데이트!
      gnn06-17
  • 3-b. Classify
    • 모든 노드들 Reclassify!
      • 기존의 분류
        gnn06-18
      • Reclassify!
        gnn06-19
  • 3-a, 3-b를 수렴할 때까지 Iterate -> Right classification!
    • 수렴!
      gnn06-20

Application of iterative classification framework: fake reviewer/review detection

  • 리뷰 사이트는 spam이 공공연하게 일어나는 곳임
    • 평가 점수 +1 점 당 수입이 5~9% 정도 상승!
    • 그래서 Paid spammer들은 ‘거짓으로’ 해당 상품들의 평가를 낮게 평가함으로써, 경쟁사를 꺾으려고 함
  • ‘어떻게 SPAM을 Detect할 것인가!’
    • Behavior 분석?
      individual features, geographic locations, login times, session history …
    • Language 분석?
      use of superlatives, lots of self-referencing, rate of misspellings, many agreement words …
    • 위 둘의 분석은 이미 분석자를 속이기 쉬운 영역 (Easy to fake)
      • individual behaviors, content of review -> Not reliable anymore!
      • 그렇다면 ‘속이기 어려운’ 영역은 뭘까? -> Graph Structure
  • Graph Structure
    Reviewers, Reviews, Stores … 그들간의 ‘관계’는 어렵다는 사고에 기인.
    • 문제 정의 방식
      • Input: 가중치 방향 그래프 형태의 이분 평점 그래프
        (Bipartite rating graph as a weighted signed network)
        • 노드: Users, Products
        • Edges: -1~1 사이의 rating scores

      • Output: 거짓으로 평점을 평가하는 유저 집단

        gnn06-21

REV2 Solution Formation

  • 기본 아이디어
    이용자(Users), 물품(Products), 평점(Ratings)는 모두 고유한 품질 점수(Intrinsic Quality Score)를 가지고 있다.
    • Users: fairness scores
    • Products: goodness scores

    • Ratings: Reliability scores

    • (이 모든 값들은 처음에는 알려져있지 않음.)

    gnn06-22

    • 모든 노드와 간선들의 값들은 Iterative Classification 을 통해 계싼한다.

    Fairness of Users

    • Goodness와 Reliability를 고정하고, Fairness를 업데이트
      gnn06-23

    Goodness of Products

    • Fairness와 Reliability를 고정하고, Goodness를 업데이트
      gnn06-24

    Reliability of Ratings

    • Fairness와 Goodness를 고정하고, Reliability를 업데이트
      gnn06-25

이 값들을 구해가는 과정?

  1. Initialization to best scores
    • F, G, R 모든 값들을 1로 초기화
      gnn06-26
  2. Iteration1
    • 2-1. Goodness 업데이트!
      gnn06-27
    • 2-2. Reliability 업데이트!
      gnn06-28
    • 2-3. Fairness 업데이트!
      gnn06-29
  3. 수렴한다면
    gnn06-30
  • REV2는 수렴이 보장되어 있음!
  • 수렴하기까지의 총 Iteration 횟수도 상한이 있고, (Upper-bounded)

  • 시간복잡도도 그래프의 Edge의 수가 증가함에 따라 Linear하게 증가!

  • Low fairness users = Frausters

Collective Classification: Belief Propagation

3. Belief Propagation

이하 Loopy Belief Propagation에 대한 내용

  • Graphical 모델에서 조건부확률 queries에 답하는 Dynamic Programing approach!
  • Neighbor Variable들이 서로 간에 ‘Talk’하는, 이를테면 Passing Messages와 같은, Iterative Process

  • 합의에 도달하면, Final belief를 계산

  • 매커니즘
    gnn06-31

    • Task: 그래프 상에서의 노드의 개수 세기.
    • Condition: 각 노드들은 각자의 neighbor와만 interact (or Message passing) 할 수 있다.
    • Solution: 각 노드들은 각자의 neighbor들로부터 message를 전해듣고, 업데이트하고, 이 내용을 앞으로 전달한다!
      gnn06-32
      • 이와 같은 사고는 Primitive하지만 Powerful하다!
      • 이 그림에서, 동그라미로 표시해놓은 노드만이 실제 그래프의 길이를 알고 있음.
        gnn06-33
  • 이같은 사고는 Tree에서도 마찬가지로 적용될 수 있음.
    gnn06-34
    • 빨간색으로 표기된 노드는 ‘이 트리에는 14개의 노드가 있을거야!’라고 판단할 것.
    • 이 역시 Message Passing 매커니즘을 통해 알 수 있음.
    • 이와 같이 정확한 갯수를 세는 것 뿐만 아니라,
      • neighbor 노드가 ‘내 생각에는 그래프에서 Sampling을 해보니까 대략(Roughly) 10개의 노드가 있는 것 같아!’ 라거나

      • 그래프의 size 대신에 주변의 노드들이 ‘네 Label은 A같아! B같아!’와 같은 Labeling을 할 수도 있음!

      • 이 모든 Case들 역시 Belief Propagation
  • 다만 그래프에서 Cycle이 생기는 경우는 Loopy Belief Propagation이 잘 working하지 않음.
    gnn06-35
    • 하지만, 실제 graph들에서는 이런 Loop은 ‘드물게’ 발생하며,
    • Graph가 충분히 커서 Cycle의 Contribution이 그리 크지 않은 경우가 많음.
    • 또한, 이 Cycle을 제거하기 위한 Heuristic한 방법들도 존재.
      -> 최악의 경우에는 Cycle을 먼저 제거하고, Loopy Belief Propagation을 적용하기도.

Loopy BP algorithm

  • 다음과 같은 그림을 한 번 생각해보자.
    gnn06-36
    • i가 j에게 어떤 메시지를 보내는지는, i가 주변 k들로부터 듣는가에 기인
    • 각각의 k 노드들은 i에게 각자 state의 belief를 메시지의 형태로 전달한다.
  • Notation
    • ψ (Label-label potential matrix)
      • 어떤 노드와 그 neighbor 사이의 Dependency
      • ψ(Yi, Yj): 노드 j의 neighbor i가 state Yi에 있을 때, 노드 j가 state Yj에 속할 확률
      • 직관적으로 -> ‘노드 i와 j의 correlation’
    • Φ (Prior belief)
      • 노드 i가 state Yi에 속할 확률 Φi(Yi)
      • j가 state Yj에 있을 상태에 대한 i의 추정치
    • L: 모든 state들의 집합
  • Process
    1. 모든 message들을 1로 초기화 (네트우크에 대해 아무것도 모르는 상태)
    2. 각 노드에 대해 반복
      gnn06-37
    3. 수렴하면, 각 State에 대한 Belief를 계산
      gnn06-38

  • 다시 한 번, Loopy Belief Propagation은, Cyclic 그래프에서는 쓰지 않도록 하자!

  • Loopy BP의 장단점
    • 장점
      • 프로그래밍 및 병렬화 쉬움
      • 어떤 그래프 모델에도 보편적으로 적용 가능
    • 한계점
      • 수렴이 보장되지 않는다. (많은 Closed loop가 있을 경우)
        -> Trick 한가지: Clustering Coefficient를 확인해보고 계수값이 매우 크다면, Loopy BF는 여기에 쓰일 수 있는 테트닉이 아닐 가능성이 매우 높음
    • Potential functions
      • 파라미터 추정을 위해서 훈련이 필요
      • Graident-based 최적화 학습 -> 훈련 동안 수렴에 관한 이슈가 발생할 수 있음.

Application of Belief Propagation: Online Auction Fraud

  • 경매사이트: Fraud 장소로 상당히 매력적인 장소!
  • 종종 배달 안됐다는 리뷰를 남기는 사기를 치곤 함
    • 이런 사건 발생 하나당 평균 손실이 385 달러 정도
  • 단순히 Individual Feature들을 봐서는 해결 불가능한 문제
  • ‘하지만 Graph Structure을 속일 수는 없다!’
    • 주된 궁금증: 사기꾼들은 다른 유저들과, 또 사기꾼들끼리 어떤 식으로 상호작용 하는가?
      (+ 단순히 사고 파는 관계를 떠나서 더 복잡한 관계라는 것이 존재하는가?)
  • 매커니즘
    • 각 유저는 평판스코어 ‘Reputation score’라는 것을 갖고 있다.
    • 유저들은 각 유저들을 feedback을 통해 평가
    • 궁금증: ‘사기꾼들은 이 Feedback 시스템을 어떤 식으로 사용하는가?’
      • ‘사기꾼들끼리의 평판을 올려주는가?’
        -> No! ∵ 한 놈이 잡히면 우루루 다 잡힌다.
      • 그들은 흡사 이분그래프를 형서한다. (near-bipartite cores (2 roles))
        • Accomplice (꽤나 정상적인 행동 양태를 보이며, 선량한 유저들과 거래)
        • Fraudster (Accomplice와 거래하며 Honest를 등처먹는다(?)
          gnn06-39

    • 이 near-bipartite cores를 어떻게 찾아낼 것이며, honest, accomplice, fraudster를 어떻게 구분해낼 것인가?
      -> Belief Propagation 을 사용하라!

    • 이 관계에 대한 Prior Belief를 다음과 같이 가지고 있다고 가정하자!
      gnn06-40

      • 수렴할 때까지, Belief Propagation을 수행하면 다음과 같은 결과가 얻어진다.
        gnn06-41

      • (앞에서는 Binary-Classification이었지만, 이 경우는 Multi-class Classification!)

      • 다음과 같은 결과를 얻었고, Role에 대한 구분을 잘 해냈다고 볼 수 있겠다!

        gnn06-42

References

CS224W: Message Passing and Node Classification