전통적인 방법들 ▪ 노드 및 그래프 분류를 위한 그래프 통계량과 커널 방법 → 2.1 ▪ 관계 예측을 위한 노드 이웃 중첩 측정 방법 → 2.2 ▪ 군집화를 위한 스펙트럴 방법, 그래프 라플라시안 → 2.3
그래프 통계량m ▪ 기존의 그래프 데이터에서의 분류 문제는 전통적인 기계학습 패러다임을 따름 ▪ 그래프로부터 통계량 및 특징을 추출하고 분류기의 입력으로 활용 ▪ 노드-레벨 통계량과 그래프-레벨 통계량이 쓰임
커널 방법 ▪ 그래프 통계량에 커널 방법을 적용하여 확장 가능
▪ 가장 유용하고 필수적으로 확인해야 할 노드-레벨 통계량 ▪ 노드 u ∈ V에 대해 인접(incident)한 링크 수를 계산
$d_u = Σ_{v∈V}A[u,v]$
▪ 가중(weighted) 그래프: 위 식을 통한 일반화 가능 ▪ 유향(directed) 그래프: 인접 행렬의 행/열의 합으로 진출/진입 링크 수를 계산하여 정의
예제: Marriage Network ▪ 노드 연결수 → 메디치: 5, 스트로치: 3, 과다니: 2, ...
▪ 일반적으로 노드 분류 문제에서 연결 수보다 더 중요한 역할 ▪ 고유 벡터 중심성, 매개 중심성, 근접 중심성 등
고유 벡터 중심성 (Eigenvector-) ▪ 노드의 이웃이 얼마나 중요한지 고려하여 중심성 계산 ▪ 노드의 중심성이 이웃들의 중심성의 평균(또는 합)에 비례한다는 점화식을 통해 정의 (𝜆: 상수)