[CS224W] 2-2. Link-level Prediction

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

link-level 예측은 기존 link들에 기반하여 새로운 link들을 예측하는 task로,
모든 node pair들에 대해 순위를 매기고 그 중 상위 K개 node pair를 link로 예측하는 식으로 진행된다.
따라서 node pair들에 대한 feature를 구상하는 것이 핵심이다.

link prediction task는 세부적으로 두 가지로 나눌 수 있다.

• link missing at random
  : 랜덤으로 지워진 link 예측
• links over time
  : 시간이 지남에 따라 진화되는 네트워크가 있을 때, 시간 경과에 따라 link 예측
  (미래에 나타날 link 순위 목록 생성)

사용될 수 있는 feature들은 다음과 같다.

distance-based features

두 node 사이 최단 거리를 나타내는 feature로,
간단하지만 이웃 node 개수 등을 담지 못하는 단점이 있다.

local neighborhood overlap

공통으로 공유하는 이웃 node 개수와 관련된 feature로, 표현 방식에 따라 크게 3가지로 나눌 수 있다.

• Common neighbors : node pair 간 공통 node 개수
• Jaccard's coefficient : Common neighbors의 정규화된 버전
• Adamic-Adar index : 이웃이 많은 node보다 이웃이 적은 node가 주변에 있는 것이 중요함을 나타낸 지표

하지만 node pair가 공통으로 가지는 이웃이 없다면 해당 metric은 항상 0인 단점이 있다.

global neighborhood overlap

local neighborhood overlap의 단점을 보완하고자, 그래프 전체의 구조를 반영한 feature이다.
대표적으로 node pair 사이의 모든 경로 수를 계산한 Katz index가 있다.

- discount factor(β)는 경로가 더 길수록 낮은 중요도를 부여한다