[CS224W] Lecture01 Introduction: Machine Learning for Graphs

들어가면서

다양한 자료 구조 (특히 회로)들은 그래프로 표현하는 것이 직관적으로 더 좋고 성능도 더 잘 나온 것으로 알려져서 스탠포드에서 graph representation leraning 강의가 올라와 있어서 이를 공부하며서 정리하고자 한다.

https://web.stanford.edu/class/cs224w/index.html

CS224W | Home

 

왜 그래프를 사용해야 하는가?

기존의 Machine learning 및 Deep learning의 경우 grid(image), sequence(text나 audio) 형태의 input만 주로 활용했지만 세상에는 grid, sequence로 표현되지 않는 것도 많다.

그래프는 relation, interaction을 표현하기 좋은 수단으로 더 나은 prediction 결과를 낼 수 있다.

 

그래프 표현의 예

그래프를 활용한 Neural Network의 모습

그래프를 직접 convolution할 수 있다.

그래프 정보 (node, edge, graph)를 임베딩으로 변환하여 활용할 수 있다.

Graph structure를 활용하면 간접적으로 어떤 feature가 중요한지 알아낼 수 있다.

 

그래프를 가지고 할 수 있는 task들

다양한 level에서 task를 수행할 수 있다.

• Node classification: 특정 노드가 어떤 특징(feature)를 가지고 있는지 예측 (online user/item categorization)
• Link prediction: 두 노드간 link가 있을 것인지 없을 건인지 관계를 에측 (Knowledge graph completion, recommendation system, drug side effect prediction)
• graph classification: 그래프가 어떤 property를 가질 것인지 구분 (molecule/drug property prediction)
• clustering: 특정 sub-graph를 찾아낸다. (social circle prediction, traffic prediction)
• graph generation: 특정 조건을 만족하도록 새로운 그래프를 생성 (Drug discovery)
• graph evolution: 그래프가 어떻게 변화해 갈 것인지 예측 (physical simulation)

 

그래프의 구성 요소

Node, Edge, Graph

 

그래프를 표현하는 방법들

(1) Adjacency matrix

각 노드에 index를 부여하고 index의 개수만큼 row와 column을 가지는 매트릭스를 만든다.

- undirected graph일 경우 adjacency matrix는 symmetric하다.

- 만약 edge에 가중치를 준다면 1이 아닌 다른 숫자를 넣으면 된다.

 

성질

1. row (혹은  column) 값을 다 더하면 해당 노드의 degree가 된다.

$$k_i=\sum _j^N{A}_{ij}$$

보통 node의 개수에 비해 edge의 개수가 훨씬 적으므로 "sparse matrix"가 된다 => memory, computation에서 손해

 

(2) Edge list

(따로 떨어져 있는 노드 없이 노드들이 모두 연결되어 있다는 가정 하에) edge들의 list만으로 그래프를 표현할 수 있다.

ex: [(1,2), (2,3), (1,3), (3,4)]

 

(3) Adjacency list

각 노드들의 neighbor들을 표기해준다.

1: 2,3

2: 1,3

3:, 1,2,4

4: 3

 

다양한 그래프들

• Directed Vs. Undirected: edge에 방향성이 있나 없나
• Heterogenous graph G = (V, E, R, T)
• Bipartite graph: 노드가 두 그룹 (U, V)로 나뉘어져 edge가 같은 그룹내에서는 없고, 서로 다른 두 그룹 사이에만 존재 (user와 iterm, actors & movies
• weighted vs unweighted
• self-edge를 허용할 것인가? multiple edge를 허용할 것인가?