1. Machine Learning with Graphs

1.1. Why Graph?

그래프는 객체(entity)와 객체 간의 관계(relation)/상호작용(interaction)을 설명하는 범용 언어입니다.

그래프 구조로 표현할 수 있는 데이터는 여러가지가 있습니다. 예를 들어서 컴퓨터 네트워크, SNS, 지식 그래프, 분자 구조 등이 그래프 구조로 표현될 수 있습니다. 복잡한 도메인일수록 그래프로 표현할 수 있는 풍부한 관계 구조를 갖고 있습니다. 그래프를 이용해 이러한 관계를 명시적으로 표현하면, 우리의 task에서 더 좋은 성능을 보일 것입니다.

1.2. Why is Graph Deep Learning Hard?

기존의 딥러닝 모델들은 이미지(grid)나 텍스트(sequence) 데이터를 처리하는데 집중해왔습니다. 대표적으로 CNN과 RNN이 있습니다. 그러나 모든 데이터들이 grid나 sequence로 표현 할 수 있는 것은 아닙니다.

그래프는 복잡한 구조를 갖고있기 때문에 딥러닝을 적용하기 어렵습니다.

• 그래프의 크기는 다양하며, 복잡한 위상구조를 갖습니다.
• Node에 정해진 순서가 없으며, reference point도 존재하지 않습니다.
• 그래프는 동적이며 다양한 종류(e.g. 이미지, 텍스트, 벡터)의 feature를 갖습니다.

1.3. Deep Learning in Graphs

위는 Graph Neural Network 중 하나인 GCN 입니다. GNN은 그래프(network)를 입력으로 받아서 node label, new link 등을 예측하거나 새로운 그래프나 서브 그래프를 생성합니다.

1.4. Representation Learning

Representation Learning은 neural network를 통해 그래프를 d차원으로 embedding 하는 방법을 학습합니다. 이 때, feature engineering은 사람에 의해서 수행되지 않고, 데이터로부터 모델이 학습합니다. 그래프를 d차원으로 embedding을 하게 되면 그래프 상에서 유사한 노드는 가깝게 embedding이 될 것입니다.

---

2. Applications of Graph ML

2.1. Different Types of Tasks

그래프의 task는 node level, community level, edge-level, graph-level로 나눌 수 있습니다.

2.2. Classic Graph ML Tasks

• Node classification
  Node의 label $y_u$를 예측합니다. $y_u$는 node의 type, category, 혹은 attribute가 될 수 있습니다. Standard supervised classification과 유사해보이지만, node가 다른 node와 연관되어있는 특징이 있습니다. (e.g. Categorize online users / items)
  그래프에서 node는 이웃 node와 attribute가 유사한 경향을 보입니다. 이를 homophily 라고 합니다. 그래프 모델을 만들 때, homophily 성질을 고려하여 이웃 node가 유사한 label을 갖도록 할 수 있습니다. Structural equivalence는 유사한 이웃 node 구조를 갖는다면 label이 유사한 경향을 보인다는 것을 의미합니다. 마지막으로 heterophily는 서로 다른 label을 갖는 node가 연결된다는 것을 의미합니다.

• Relation prediction
  Node 사이에서 존재할 수 있는 edge를 예측합니다. 부분적으로 존재하는 불완전한 edge 데이터를 활용하여 edge 데이터를 복원하는 것을 목표로 합니다. (e.g. Knowledge graph completion)
  

• Graph classification
  Graph 전체 구조를 활용하여 다른 graph와 분류합니다. (e.g. Molecule property prediction)

• Clustering : 여러 개의 node가 모여서 그룹을 생성할 수 있는지 감지합니다. (social circle detection)

• Other tasks:

  • Graph generation : 새로운 그래프를 생성합니다. (e.g. 신약 개발)
  • Graph evolution : 그래프를 진화합니다. (e.g. 물리 시뮬레이션)

---

3. Choice of Graph Networks

3.1. Components of a Network

그래프 $\mathcal{G}=(\mathcal{V},\mathcal{E})$는 node $\mathcal{V}$와 이를 연결하는 edge $\mathcal{E}$로 이루어져있습니다. $u\in \mathcal{V}$이고 $v\in \mathcal{V}$일 때, 두 node 사이의 edge는 $(u,v)\in\mathcal{E}$와 같이 표현합니다.

3.2. Directed vs Undirected Graphs

Undirected graph는 edge의 방향성이 존재하지 않는 그래프를 뜻합니다. 즉, $(u,v)\in \mathcal{E}\leftrightarrow (v,u)\in\mathcal{E}$ 입니다. 반면, directed graph는 edge의 방향성이 존재하기 때문에 위 식이 성립하지 않습니다.

3.3. Weighted Edges

어떤 그래프는 adjacency matrix의 값이 1이 아닌 weighted edge를 가질 수 있습니다. 이러한 weighted는 두 node 간 상관관계의 강도를 표현할 수 있습니다. 예를 들어서, 단백질 상호작용 그래프는 두 단백질 사이 연관성의 강도를 weighted edge로 표현할 수 있습니다.

3.4. Self-edges and Multigraph

Self-edges 는 node의 edge의 출발지와 도착지가 같은 것을 의미합니다. Adjacency matrix의 주대각성분의 값을 1로 표기하여 표현합니다. Multigraph는 두 node 사이에 edge가 여러 개 존재하는 것을 의미합니다. Weighted edge와 유사하게 adjacency matrix의 값을 조정하여 표현합니다.

3.4. Multi-relational Graphs

그래프의 edge는 directed, undirected, weighted 뿐만 아니라 type 자체가 다양할 수 있습니다. 이러한 경우 edge에 대한 표현을 edge relation type $r$을 포함하여 $(u,r,v)\in\mathcal{E}$ 과 같이 정의합니다. 이러한 그래프를 $multi~relational$ graph 라고 하며 edge type에 따라 adjacency matrix $A$를 각각 하나씩 정의할 수 있습니다. 이 때, $\mathcal{R}$이 relation type 을 나타낸다면 $A\in\mathbb{R}^{|V|\times|R|\times|V|}$ 입니다.

3.4.1. Heterogeneous Graphs

Heterogeneous graph는

로 정의합니다.

• Nodes with node types $v_i \in \mathcal{V}$
• Edges with relation types $(v_i,r,v_j)\in\mathcal{E}$
• Node type $\mathcal{T}(v_i)$
• Relation type $r\in\mathcal{R}$

여기서는 node 또한 type을 갖고있기 때문에 독립된 type의 node $V_i$의 집합인 $\mathcal{V}=\mathcal{V_1}\cup\mathcal{V_2}...\cup\mathcal{V_k}$ 로 표현할 수 있습니다. 일반적으로 heterogeneous 그래프의 edge는 type을 갖고있는 두 node를 연결하는 조건을 만족합니다. i.e., $(u,r_i,v)\in\mathcal{E}\rightarrow u\in V_j, v \in V_k$

3.4.2. Multiplex Graphs

Multiplex graph는 그래프가 k개의 layer의 집합으로 분해될 수 있다고 가정합니다. 각 레이어는 고유한 relation을 표현하며, 그 layer 내부의 edge를 표현합니다.

3.5. Node Degrees

Node degree, $k_i$는 node $i$와 연결된 edge의 개수를 나타냅니다. 위 그림의 Undirected graph에서 $k_A$=4 입니다.

AVG.degree: $\bar{k}=\cfrac{1}{N}\sum^N_{i=1}k_i=\cfrac{2E}{N}$

Directed graph에서는 node는 in-degree와 out-degree 를 갖습니다. Degree의 총합은 in, out-degree의 총합입니다. 또한, node에서 나간 edge가 다른 node로 들어오게 되므로 in-degree와 out-degree의 총합은 같습니다. 위 예시에서는 $k^{in}_C=2$이고 $k^{out}_C=1$입니다.

AVG.degree: $\bar{k}=\cfrac{E}{N}$

3.6. Bipartite Graph!

Bipartite graph는 node가 2개의 disjoint set U, V로 나뉘고, 모든 edge는 $U\leftrightarrow V$ 두 노드 사이에서만 존재합니다. U끼리, 혹은 V끼리는 연결되지 않습니다.

Bipartite graph를 위와 같이 projection 할 수 있습니다. Projection U를 살펴보면 node A에 연결되었던 node 1, 2, 3이 edge로 연결된 것을 관찰할 수 있습니다. 또한 node 2, 5는 node B와 연결되어 있어서 node 2와 5 사이를 연결하는 edge가 존재하는 것을 관찰할 수 있습니다.

3.7. Representing Graphs

현실 세계의 데이터는 대부분 굉장히 sparse 하기 때문에 adjacency matrix는 대부분 0으로 채워집니다. 이러한 데이터를 효과적으로 표현할 수 있는 법은 없을까요?

3.7.1. Adjacency Matrix

그래프는 adjacency matrix $A\in\mathbb{R}^{|V|\times|V|}$로 표현할 수 있습니다. 이 때, $A$는 두 node $u, v$ 사이에 edge가 존재하면 $A[u,v]=1$이고, 그렇지 않으면 $A[u,v]=0$ 입니다. 그래프가 undirected graph라면 adjacency matrix $A$는 주대각선을 기준으로 대칭인 symmetric matrix 입니다. 그러나 그래프가 directed graph라면 양방향으로 edge가 존재하지 않으면 symmetric matrix 가 아닙니다. Adjacency matrix는 간단하지만 sparse 하기 때문에 공간을 불필요하게 많이 차지합니다.

3.7.2. Edge list

Edge들의 list로 그래프를 표현할 수 있습니다.

3.7.3. Adjacency list

Adjacency list는 각 노드에 연결된 edge를 저장합니다. Network가 크고 sparse하더라도 빠르게 검색할 수 있고, memory를 아낄 수 있습니다.

3.8 Connectivity of Undirected Graphs

Connected graph는 graph 내의 모든 node들이 다른 node로 이동할 수 있는 path가 존재하는 그래프를 말합니다. 반대로, disconnected graph는 다른 node로 가는 경로가 없는 경우가 존재하는 경우를 말합니다. Disconnected graph는 connected components로 이루어집니다.

3.8.1. Strongly connected directed graph

임의의 node A로부터 임의의 node B로 가는 경로와 B에서 A로 가는 경로가 모두 존재하는 그래프를 말합니다.

3.8.2. Weakly connected directed graph

임의의 node A로부터 임의의 node B로 가는 경로가 존재하지만, 역은 성립하지 않는 경우를 말합니다.

3.8.3. Strongly connected components

그래프의 일부분이 strongly connected 인 경우를 말합니다. 모든 node가 조건을 만족하지는 않습니다.