[CS224W] 2-1. Node-level Prediction

이 포스트는 CS224W : Machine Learning with Graphs 강의를 기반으로 작성되었습니다.

2강에서는 전통적인 머신러닝 파이프라인에서 사용한 feature들을 알아보고자 한다.
node-level 예측은 node classification 등과 같은 task로, 아래와 같은 feature를 사용한다.

node degree

node가 갖고 있는 edge 개수로, 모든 이웃 node들을 동등하게 취급한다.

node centrality

그래프 내 node의 중요도로, 기준에 따라 다양하게 정의할 수 있다.

• eigenvector centrality
  : 중요한 node 사이에 둘러싸인 node일수록 중요

• betweenness centrality
  : 다른 node 사이 많은 최단 경로가 있는 node일수록 중요

• closeness centrality
  : 다른 모든 node에 대한 경로 길이가 짧을수록 중요 (중심에 있을수록 다른 node로 가는 길이 짧다)

clustering coefficient

node 주변 구조 (local structure) 를 고려하여, 이웃 node들끼리 얼마나 연결되어 있는지 측정한다.

graphlets : rooted connected non-isomorphic subgraphs

node 개수에 따라 각 node가 취할 수 있는 위치를 나타낸다.

• GDV (Graphlet Degree Vector)
  : 해당 node에서 rooted된 graphlet 개수 (Graphlet-based features for nodes)

- degree는 edge 개수를,
- clustering coefficients는 triangle 개수를,
- GDV는 graphlet 개수를 나타낸다.