Graph Machine Learning #2 - Vs traditional ML(Stanford CS224W)

본 블로그는 Stanford의 'CS224W: Machine Learning with Graphs'를 요약한 글임을 밝힙니다.

출처:http://web.stanford.edu/class/cs224w/

CS224W | Home

---

1. Goal

• Goal: objects 집합에 대한 예측을 만드는 것
• Features: d-차원의 벡터
• Objects: 노드, 엣지, 노드 집합, 그래프 
• 목적 함수: 어떤 문제를 풀기 위함인지

---

2. Node-level Features

• 목적: 네트워크 상에서 노드의 위치와 구조를 확인하기 위한 작업 

 

(1) 노드 Degree: 노드가 몇개의 엣지를 보유하고 있는지

• 특징: 모든 연결성을 동일하게 판단함 

 

(2) 노드 Cenrality: 노드 중요성 계산

• 특징: 노드 degree가 판단하지 못하는 중요도 문제를 해결함

 

[1] Eigenvector centrality

• 중요한 이웃 주변에 있다면 중요한 노드로 간주 

 

[2] Betweenness centrality

• 다른 노드 N개들로 가는 길에 가장 가까운 길을 제시하면 중요

 

[3] Closeness centrality

• 다른 모든 노드들로 가는 길에 가장 가까운 길을 제시하면 중요

 

[4] Clustering coefficient

•  노드 v의 이웃 노드들의 연결성 정도를 기준으로 파악 

(3) Graphlets (sub-graph)

• 네트워크 내부의 sub-graph(triangles) 개수를 토대로 상관계수를 군집화하는 방식
• Goal: 노드 u를 둘러싼 네트워크 구조를 묘사한다. 
• graphlet degree vector는 노드들의 local 네트워크 연결방식(topology)를 측정하는 방식을 제시한다.
• Induced subgraph
  • 모든 노드들끼리 서로 연결된 subgraph

• Graph Isomorphism
  • 그래프 동형
  • 다른 내용/데이터를 담고 있으나 형태/구조는 동일한 형태

---

(2) 정리

• 1) Importance-based features
  : 그래프 내부 노드의 중요도를 확인함 
  
  • Node degree
    • 단순하게 이웃 노드를 세어봄
  • Node centrality
    • (1) 이웃 노드들의 중요도 고려
    • (2) 다른 방식의 centrality 계산 방식 활용 
    • 그래프 내부에서 가장 영향력이 높은 node를 예측하는 데에 효과적임 
• 2) Structure-based features
  : 노드 주변의 지역적 연결성/특성을 잡아냄  
  • Node degree
    • 이웃하는 노드의 갯수를 셈
  • Clustering coefficient
    • 이웃들간의 연결성을 확인 
  • Graphlet count vector
    • 다른 graphlets이 출현하는 빈도를 계산
  • 특정 노드가 그래프 내부에서 담당하는 역할을 예측하는 역할을 진행

---

2. Link Prediction Tasks

• (1) Link Missing at Random
  • 랜덤한 연결 집합을 제거한 후 예측하는 목표 
• (2) Links over time
  • G[t0, t'0]가 주어졌을 때 G[t1, t'1]에 어떤 예측 값이 나타날 지 예측하는 작업

1) Distance based Feature

• 2개의 노드 간 가장 가까운 거리 계산
• But, 이 방식은 이웃간 overlap계산 불가  
• 최소 거리를 알려주지만 이웃이 어떻게 겹쳐있는지 알려주지 못함 

2) Local neighborhood overlap

• Common neighbors
• Jaccard's coefficient
• Adamic-Adar index
• 이웃이 어떻게 겹쳐있는지 알려주지만 이웃이 없는 경우에는 정보를 얻을 수 없음

3) Global neighborhood overlap

• Local에서는 이웃이 없으면 항상 수치가 0이 된다는 한계가 있음 
• 하지만 미래에는 노드간 결합이 일어날 수도 있음 
• 때문에 Global neighborhood overlap은 전체 그래프를 고려하여 한계를 해결한다. 
• 모든 경우를 고려하여 walk를 잡아준다 
• Katz index: 
  • 모든 노드 쌍들의 길이를 고려함 
  • adjacency matrix를 활용하여 계산 

---

3. Graph-level Features & Graph Kernels

1) Kernel methods 

• 특징 벡터 대신 커널을 디자인하는 방식
• K(G, G')커널 방식은 데이터 간 유사도를 측정한다.
• feature 대푯값 phi가 존재한다. 
• 커널이 정의되고 나면 Kernel SVM과 같은 방식을 활용할 수 있다. 

핵심 아이디어:

• Goal: 그래프 특징 벡터 phi를 디자인한다. 
• Key Idea: Bag-of-Words (BoW)
  • BoW는 단순하게 단어등장 빈도를 문서 특징으로 활용함
  • 단순한 표현 방식
• Word 숫자 대신 Degree를 넣어서 계산하면 되지 않을까?

 

(1) Graphlet Kernel 

• 그래프 내부의 graphlet 개수를 세는 방식으로 접근 
  • 연결되지 않은 isolated node들도 포함
  • rooted 되지 않은 graphlet들도 포함 
  • 문제: G와 G'사이즈가 다른 경우 왜곡 심함 → 정규화로 해결
  • 한계: graphlet 계산은 비싸다 
  • graphlet 예시들

(2) 리만 커널

• 효율적인 그래프 특징 표현 방식 phi 도출 
• 반복적으로 부유한 node 정보를 도출하기 위해 이웃 노드 구조 정보를 활용함
• color refinement 알고리즘 활용
  • 최초의 색을 initialize한 후에, 반복적으로 노드 색깔을 재정의 함
• 컴퓨팅 계산 측면에서 효율적임