[CS224W] 1.Graphs

Graphs

그래프(Graph)는 객체(entity)들을 관계와 상호작용으로 표현하고 분석하는 언어이다.

그래프의 종류는 매우 다양하고 광범위하다. 실세계의 엔티티(객체)와 그들 간의 관계를 나타낸 지식 그래프, 소스 코드의 구조나 실행 흐름을 나타낸 코드 그래프, 심지어는 분자 구조, 3D Shapes도 그래프의 일종이라 할 수 있다.

그래프를 활용한 머신러닝은 관계 구조의 이점을 어떻게하면 예측에 잘 활용할 수 있는가에 대한 질문에서 시작한다. 복잡한 도메인일수록 관계형 구조는 복잡해지고 이는 관계 그래프로 표현된다. 관계를 명확히 모델링 할 수 있다면 더 나은 성능을 이룰 수 있다.

현대 딥러닝 모델을 보면 text나 speech처럼 간단한 시퀀스, 이미지처럼 정해진 grid구조에 맞춰 design되어 있다. 하지만 그래프는 이보다 훨씬 복잡하다. size도 임의고, 위상학적 구조도 복잡하다. gird처럼 공간상의 특정이 없다. 이처럼 보다 보편적으로 적용할 수 있는 신경망을 설계하기 위해서는 그래프를 사용해야 한다.

Deep Learning in Graphs

결국 우리는 그래프를 입력으로 받아 end-to-end로 예측값을 내는 모델을 만들어야 한다. 이는 그래프 데이터를 통해 기존에 사람이 했던 feature engineering 작업을 거치지 않고 그래프의 representation을 학습하게 하는 것을 의미한다.

이를 위해서 유사한 노드들끼리 $d$차원으로 embedding한다. 이렇게 embedding된 벡터는 그래프의 feature, node, link 등의 정보를 담게 된다.

Choice of Graph Representation​

Components of a Graph(Network)

1. Objects: nodes, vertices $N$
2. Interactions: links, edges $E$
3. System: network, graph $G(N, E)$

Node Degrees

Node Degrees $k_i$는 node $i$와 연결된 edge의 수를 의미한다. Undirected graph의 경우 Avg.degree는 다음과 같이 구해진다.

\[\bar{k}=\langle k \rangle = \frac{1}{N} \sum_{i=1}^N k_i = \frac{2E}{N}\]

이처럼 구해지는 이유는 degree를 구할 때 각 node 기점으로 한 edge가 두 번씩 구해지기 때문이다.

Directed graph의 경우 in-degree와 out-degree를 따로 정의한다. 위 그림의 node A의 경우 $k_C^{in}=1$, $k_C^{out}=2$이고 total degree of a node는 $k_C=3$이다. 평균의 경우 $\bar{k}=\frac{E}{N}$, $\bar{k^{in}}=\bar{k^{out}}$이다.

Bipartite Graphs

Bipartite Graphs는 두 개의 독립인 set $(U, V)$에 대해 $U$의 node가 $V$의 node로 연결되는 그래프이다. 위 그림처럼 Bipartite Graphs가 있으면 한쪽의 Projection graph를 만들 수 있다. set $U$를 예로 들면 1, 2, 3 노드의 경우 모두 set $V$의 A노드로 연결되므로 Projection U에서 1, 2, 3 노드가 서로 연결되어 있음을 확인할 수 있다. 또한 Bipartite에서 3, 4노드는 서로 다른 노드로 연결되므로 Projection U상에서 3과 4노드는 서로 연결되지 않음을 알 수 있다.

Representing Graph

Adjacency Matrix

그래프의 표현은 인접행렬로 나타낼 수 있다. node i에서 node j로의 link가 있다면 $A_{ij}=1$이고 아니면 $A_{ij}=0$이다. 따라서 무방향 그래프는 항상 대칭행렬이다. 인접행렬을 이용해 Node Degrees를 행의 합, 열의 합으로 쉽게 구할 수 있다. 인접행렬의 단점은 real-world의 네트워크를 인접행렬로 표현했을 때, 매우 sparse하다는 것이다.

Edge List & Adjacency List

그래프를 표현하는 다른 방법으로 Edge list와 Adjacency List가 있다. Edge list는 2차원 행렬로 표현하는 방식으로 간단하긴 하지만 연산이 복잡하다. Adjacency List는 네트워크가 large하고, sparse할 때 유용하다. 주어진 node와 인접한 node에 접근하기 용이하다.

14:00

Reference

https://jhtobigs.oopy.io/cs224w_week1