[CS224W] 5. Label Propagation for Node Classification

 

 몇 개의 노드에 대한 라벨을 가진 네트워크가 있을 때, 정보가 없는 노드들을 어떻게 처리할 것인가?

위 그래프처럼 초록과 빨강이란 node label 이 그래프의 일부 노드에만 주어져 있을 때 오른쪽처럼 어떤식으로 node classification을 할 수 있을까? 일부 정보만 주어져 있기 때문에 semi-supervised node classification 문제라고 볼 수 있다.

Message passing

message passing이란 것을 이용해 문제를 해결하고자 하는데 노드들의 correlation을 이용하자는 게 아이디어이다.
간단히 말해 변수간의 상관관계처럼 노드 간의 similarity가 있다면 correlated라고 것이고 이는 곧 노드 간의 connection을 보자는 것이다. 앞서 살펴봤던 node degree를 이용하는 PageRank 알고리즘과 유사하다.

관련해서 네트워크 이론에서 쓰는 용어가 두 가지를 정리하고 가자

1. Homophily 

individual characteristics 가 social connections 에 영향을 주는 것을 의미한다. 직역하면 '동종애', 유유상종이란 의미다. 
비슷한 나이, 성별, 음식에 대한 기호를 가진 사람끼리 집단을 형성하기 쉽고, 그래프 관련 포스팅을 읽는 사람들도 그래프에 관심이 있는 사람들일 것이다.

 

다음은 특정 고등학교의 학생들의 네트워크를 시각화한 것이다. 
이 경우 노드는 학생들이고 엣지는 친밀도, 노드의 색은 스포츠, 미술 , 음악 등의 관심 분야이다.
관심 분야의 학생들끼리 cluster가 형성되는 것도 homophily 때문이라고 볼 수 있다.

 

2. Influence

homophily 의 반대이다. Social connection이 individual characteristics 에 영향을 주는 경우다. 
친구가 가수나 음악을 추천해줘서 듣다보니 특정 장르에 대한 기호가 증가한다면 influence 의 예시가 될 것이다.

 

Collective classification

계속해보자. 결국 unseen node에 대한 label classification을 하기 위해서는 노드 간의 correlation leverage를 구해야 할 것이다.
motivation1 : 비슷한 노드끼리 연결되어 있을 학률이 높다. 앞서 계속했던 얘기이다.
motivation2 : node v에 대한 분류를 하려면 일단 1.노드 v의 feature , 2. v의 이웃 노드들의 labels , 3. v의 이웃 노드들의 feature 를 봐야 한다.
네트워크 이론에서 위의 motivation 을 이용하여 multiple object 에 대한 lable prediction을 하는 것을 collective classification
이라고 한다. 어떻게 node correlation 을 이용해서 분류를 할까

Markov Assumption은  노드v 의 라벨을 이웃노드들의 라벨에 기반하여 조건부 확률을 계산한다. 여기서의 이웃노드는 degree가 1인 최근접 노드들이다. 
Local Classifier - Relational Classifier - Collective Inference 의 3 step 를 따른다.
Local classifier 은 노드의 label 정보만을 가지고 분류를 한다.

 

1. Relational Classifier

Relational classifier은 node label 외에도 network information 을 이용하는데 네트워크 정보라는 것은 결국 이웃 노드와의 relation 인 edge 정보를 쓰는 것에 해당한다. 뒤에 나오겠지만 여기서는 node feature 정보를 사용하지 않는다.
기본 아이디어는 node v에 대한 class 확률분포는 v의 이웃노드들의 클래스 분포에 대한 가중 평균의 합이라는 것이다.

• labeled node : ground-truth label 
• unlabeled node : y= 0.5 로 initialize
• node convergence 될 때까지 random order update

자세한 update 예시는 강의에 나와있으므로 생략하겠다.
relational classifier는 수렴이 보장되어있지 않고, 노드 피쳐 정보를 사용하지 않는다는 단점이 있다.

2. Iterative Classification

iterative classifier 는 node v의 feature vector ${f_v}$ 를 사용하며 feature vector 만 사용하여 분류하는 ϕ1​(fv​) 과 feature vector 뿐만 아니라 neighbor labels에 대한 summary vector인 z를 함께 사용하는 ϕ2(fv,zv​) 의 두 가지 classifier를 이용한다.