CS224W 5.1 Message passing and Node Classification

1. Outline

1.1. Main question

• 일부 노드에 레이블이 할당된 그래프가 주어졌을 때,
  어떻게 모든 다른 노드에 대해 레이블을 할당할 수 있을까?
  • 예시 : 네트워크에서 신뢰할 수 있는 노드와 '사기꾼' 노드를 어떻게 찾아낼 수 있을까?
  • 위 문제는 Lecture 3 Node embedding을 통해 이미 해결할 수 있지만, 다른 방식으로 접근할 예정

1.2. Node classification

semi-supervised node classification에 대해 알아보자

• 일부 노드들이 레이블이 주어진 상황에서
• unlabeled된 노드의 레이블을 예측하는것 = semi-supervised classification
• Message passing을 통해서 이를 수행할 것

1.3. Message passing?

• 직관 : 네트워크의 상관관계를 활용하고 싶음
  • 유사한 노드들이 서로 연결되어있다는 가정 $\rightarrow$ 이웃의 레이블을 기반으로 자신의 레이블을 업데이트
  • 집합적 분류(collective classification) 컨셉
    • Pagerank에서 rank가 이웃의 점수에 기초해서 갱신되던것과 유사
• 다양한 Approaches
  • Relational classification (관계형 분류)
  • Iterative classification (반복 분류)
  • Belief propagation (믿음 전파)

2. Correlations Exists in Networks

2.1. correlation

• 상관관계 : 근처 노드가 동일한 색상, 동일한 레이블을 갖는 경향이 있음, 같은 클래스에 속하는 경향이 있음

2.2. 상관관계가 발생한다는 근거

소셜네트워크 이외의 그래프에서도 correlation이 존재할까?

• homophily (동질성)
  • 비슷한 특성을 가진 사람들이 서로 연결되는 경향을 갖음
  • "Birds of a feather flock together"
• influence (영향력)
  • 사회적 연결이 우리 자신의 특성이나 행동에 영향을 미침
  • 일단 연결이 된 후 노드들의 특성이 비슷해져가는것
• 즉 상관관계란:
  • 연결된 노드는 동일한 레이블을 갖는 경향이 있음

3. classification with network data

3.1. example

• 👇 회색 노드의 색상을 예측하는 알고리즘 어떻게 구성?
  

3.2. Motivations

• 유사한 노드는 네트워크 상에서 가깝거나, 직접 연결됨
  • Guilt-by-association (연관성에 의한 유죄)
    • 어떤 정치인이 특정단체의 회원이거나 지원자라는 이유로 비판받을 수 있음 (논리적 오류)
    • label X의 노드와 연결되면, 이와 비슷해질 가능성이 높다
  • 예시: 악성 웹페이지의 사례
    • 악성 웹페이지와 연결된 다른 페이지들도 악성인 경향이 있을 것이라고 생각하는 것

3.3. Semi-supervised Learning

• Given : Graph, Few labeled nodes
• Find : unlabeled 노드들의 class (red/green)
• Main assumption: 네트워크에 어느정도 homophily가 있음을 가정
• Example tasks

  $A:$ $n\times n$ adjacency matrix of $n$ nodes
  $Y=\{0,1\}^n$ 레이블들의 벡터 (1=녹색, 0=빨강)

3.3.1. Overview

• Intuition : 연결된 노드를 동시에 분류하고, edge를 통해 정보를 전파하기를 원함
• Markov Assumption

  $P(Y_v) = P(Y_v|N_v)$
  노드의 레이블이 이웃 노드의 레이블에만 의존한다는 것을 의미 (=1차 마르코프 가정)

4. Collective Classification의 응용사례

• Document classification
• Part of speech tagging
• Link prediction .....

5. Overview

• 다음 3가지 approaches들에 대해 다룰 것
  • Relational classification
  • Iterative classification
  • Correct & Smooth