연구를 하면서 머신러닝에 사용되는 Graph에 관해 알아둘 필요가 있어, 관련 기초 내용을 알차게 다루는 Stanford CS224W 강의를 수강하고, 내용을 정리하려 한다.
유튜브 강의 링크는 다음과 같다.
https://www.youtube.com/playlist?list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn
Stanford CS224W: Machine Learning with Graphs
This course covers important research on the structure and analysis of such large social and information networks and on models and algorithms that abstract ...
www.youtube.com
목차
Graph Introduction
먼저, graph를 왜 사용하는지부터 알아보자.
Graph는 여러 entity 간의 관계(상호작용)를 나타내기 적합한 일반적인 '언어'이다.
그리고 어떤 관계든 표현할 수 있어 목적에 따라 범용적으로 사용할 수 있다.
그래프를 활용하는 다양한 예시를 살펴보자.
이중 특히 scene graph의 경우, 주요 연구 분야에 해당한다. 이미지 등의 scene에서 object를 node로 두고, 그 object들 간의 관계를 edge로 표현한다.
3D sahpes를 표현하기 위한 그래프도 computer graphics에서 많이 사용되는 것으로, 3D Vision 분야와 관련이 있을 것이다. (Mesh 형태의 3D 데이터, 2D skeleton 데이터 등을 그래프로 나타낼 수 있을 것이다.)
그래프에 포함된 정보의 종류만 바꿔주면 다양한 domain에서 사용될 수 있다.
예를 들어, web/mobile, bio/health, medical 등에 응용할 수 있다.
또한 그래프 표현이 주요하게 활용되는 분야는 social network, drug design (protein), AI reasoning 등이 있다.
Machine Learning with Graphs
머신러닝에서 그래프를 활용할 때 중요한 점은, 더 나은 prediction을 위해 graph의 관계 구조를 어떻게 활용할 것인가이다.
현대의 machine learning, 특히 deep learning 과정은 network가 매우 복잡하다. Size가 정해져있지 않고, 복잡한 topological structure를 갖는다. (grid로 표현 가능한 image, text등과 상반된다.)
node들이 고정되어 있거나 reference point가 있지도 않고, dynamic하거나 multimodal feature를 갖는 경우도 있다.
Graph를 사용한 딥러닝은 대표적으로 사람의 개입(feature engineering) 없이 end-to-end로 network를 학습하는 아키텍쳐를 말한다.
즉, network를 input으로 주었을 때 graph convolution 등의 과정을 거쳐 node label, 새로운 link, 생성된 그래프(혹은 subgraph) 등을 예측한다.
달리 말하면, node를 d차원의 embedding으로 맵핑하는 과정을 학습한다. 이때 embedding이란, network에서 비슷한 노드를 embedding space(벡터 형태)에 서로 가까이 끼워넣는 것을 말한다. 이 결과로 나온 벡터는 feature representation, embedding 등으로 불린다.
Different Types of Tasks
Deep learning에 그래프 형태의 데이터(graphical representation)를 적용하여 풀 수 있는 문제는 다음과 같다.
- Node-level prediction
- Node classification : node의 특성을 예측한다.
- 예시 - protein folding problem (아미노산 순서가 주어졌을 때 단백질의 3차원 구조 예측)
- Link(edge)-level prediction
- Link prediction : 두 노드 간의 관계를 예측한다.
- 예시 - Graph-based recommender system, 여러 약 복용 시 side effects 예측(biomedical graph link prediction)
- (Sub)Graph-level prediction
- Graph classification : 서로 다른 graph를 분류한다. (예시 - 분자의 특성 예측)
- 예시 - Traffic prediction
- Other tasks
- Graph generation : 그래프를 생성한다.
- Graph evolution : 그래프를 확장시킨다.
Choice of Network Representation
데이터를 그래프로 나타내기 위해서는 우선 구조를 알아야 할 것이다.
그래프의 구조를 자세히 알아보자.
Structure of Graphs
Graph는 다음과 같이 구성된다.
- Objects \(N\) : nodes, vertices
- Interactions \(E\) : links, edges
- System \(G(N,E)\) : network, graph
간단히 node set과 edge set이 모여 graph가 되는 것이다.
여기서 network는 실제 system을 나타내며, graph는 network를 수학적으로 표현한 것이다.
위 그림에서, 파란색, 빨간색, 초록색으로 나타낸 것이 실제 system, 즉 network이며, 이를 수학적으로 표현하면 검은색의 graph가 된다.
Graph를 구성하기 위해서는 node가 무엇인지, edge가 무엇인지를 정의해주어야 한다.
이때, 주어진 domain(혹은 problem)에 따라 적절한 representation을 골라야 효율적인 학습을 진행할 수 있을 것이다.
따라서 같은 시스템(network)을 표현하더라도, graph의 구성 요소로 어떤 것을 선택하는가(choosing proper representation)가 매우 중요하다.
Types of Graphs
Graph의 종류를 알아보자.
Graph는 방향성 유무에 따라 다음 두 가지로 나뉜다. 주로 이 분류를 사용한다.
- Undirected Graph
- 말그대로 link(edge)의 방향성이 없다. (symmetrical, reciprocal)
- 예시 - collaboration
- Directed Graph
- Link(edge)의 방향성이 존재한다. 즉, 시작 노드와 도착 노드가 존재한다. (arcs)
- 예시 - Phone calls, Following, Like
또한, edge에 가중치의 유무에 따라 다음과 같이 나누기도 한다.
Graph를 행렬로 표현할 수 있는데(자세한건 곧 다룰 것이다.), 가중치가 없는 경우에는 edge가 있으면 1, 없으면 0으로 표현하고, 가중치가 있다면 edge가 있을 때 해당하는 가중치까지 표현을 해준다.
이외에도 self-loop(self-edge)를 갖는 node를 포함하는 graph, Multigraph(같은 두 노드에 대해 edge가 여러 개 있는 경우) 등 다양한 그래프가 존재한다.
Property of the components of a graph
Node와 edge는 다양한 특성을 갖는다.
먼저, node부터 살펴보자.
Undirected graph에서 node의 degree \(k_i\)는 node \(i\)가 갖는 연결된 edge의 개수이다.
위 그림의 graph에서 \(k_A = 4\)일 것이다. 그리고 average degree란, 해당 graph에서 노드들이 갖는 평균 degree를 말하며, 다음과 같이 계산한다.
\( \bar{k} = \left\langle k \right\rangle = \cfrac{1}{N} \sum\limits_{i=1}^N k_i = \cfrac{2E}{N} \)
여기서 \(N\)은 node의 개수, \(E\)는 edge의 개수이다.
Directed graph에서의 edge는 두 가지로 나뉜다. Node로 들어오는 in-degree \(k_i^{in}\)과 node에서 나가는 out-degree \(k_i^{out}\)이다. (directed graph에서 degree는 total degree, 즉 in-degree와 out-degree의 합을 나타낸다.)
이때 \(k^{in} = 0\)인 node를 source, \(k^{out} = 0\)인 node를 sink라 한다.
위 그림에서 노드C에 대한 degree는 \(k_C^{in} = 2, k_C^{out} = 1, k_C = 3\)이다.
Average degree는 다음과 같이 구한다.
\( \overline{k^{in}} = \overline{k^{out}} = \bar{k} = \cfrac{E}{N} \)
그리고 edge가 갖는 특성을 알아보자.
- 가중치(weight) : 노드 간 관계의 빈도를 나타낸다.
- 순위(Ranking) : 노드 간 관계의 순위를 나타낸다.
- 종류(Type) : 연결의 종류를 나타낸다. 예를 들어, 가족인지, 친구인지 등을 다르게 나타낼 수 있다.
- 부호(Sign) : 서로 상반되는 관계를 부호로 나타낼 수 있다. 예를 들어, 믿는 것을 +, 믿지 않는 것을 -로 둘 수 있다.
Bipartite Graph
Bipartite graph란, 서로 다른 종류의 독립된 두 node set으로 구성된 그래프를 말한다.
서로 다른 node set 간에는 상호작용을 하지만, set내에서의 상호작용은 하지 않는다.
위 그림에서 가운데와 같은 그래프를 bipartite graph라 한다. \(U\)에 속하는 노드는 \(V\)에 속한 노드에게만 연결되고, \(U\)끼리는 독립이며, \(V\)도 마찬가지이다. 또한 \(U\)와 \(V\)는 서로 독립이다.
이러한 그래프는 실제 system에서 많이 나타나며, 특히 추천시스템에서 많이 사용된다. (예를 들어, \(U\)는 customer, \(V\)는 product)
그림에서 왼쪽과 오른쪽 그래프는 가운데의 bipartite graph를 펼쳐서, 서로 다른 set에 공통으로 연결된 node를 연결시킨 folded(=projected) graph이다. 예를 들어, \(U\)의 1, 2, 3 node들은 공통적으로 \(V\)의 A에 연결되어 있으므로, 서로 연결된다.
왼쪽은 \(U\)의 노드만 가져온 graph이며, 오른쪽은 \(V\)의 노드만 가져온 graph이다.
Representations of Graphs
그래프를 neural network 등에서 처리하기 위해서는 수학적, 혹은 프로그래밍이 가능한 방법으로 표현해야 한다.
표현하는 방법은 다음과 같다.
- Adjacency Matrix (인접 행렬)
- Edge List
- Adjacency List
Adjacency Matrix
인접 행렬은 행렬의 index를 node의 index로 보고, edge에 해당하는 요소가 서로 연결되어있으면 1, 연결되어있지 않으면 0으로 표현하는 방법이다.
위 그래프를 행렬로 나타내는 방법을 식으로 표현하면 다음과 같다.
\( \begin{cases} A_{ij} = 1 \quad \text{if there is a link from node } i \text{ to node } j \\ A_{ij} = 0 \quad \text{otherwise} \end{cases} \)
그림의 그래프를 표현한 인접 행렬을 각각 \(A\), \(A'\)이라 하면, 그 결과는 다음과 같다.
\( A = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}, \quad \quad A' = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \end{pmatrix} \)
Undirected graph의 인접 행렬은 symmetric임에 주목하자.
즉, \(A_{ij} = A_{ji}\)이며, 대각성분은 모두 0이다.
그리고 symmetric matrix이므로 degree를 행에서 계산하든, 열에서 계산하든 똑같다. 따라서 average degree를 계산할 때에도 행에 대해, 열에 대해 구해도 똑같으며, 단순히 모든 원소를 더하여 2로 나누는 방법도 있다.
\( k_i = \sum\limits_{j=1}^N A_{ij}, \quad \quad k_j = \sum\limits_{i=1}^N A_{ij} \)
\( L = \cfrac{1}{2} \sum\limits_{i=1}^N k_i = \cfrac{1}{2} \sum\limits_{j=1}^N k_j = \cfrac{1}{2} \sum\limits_{i,j}^N A_{ij} \)
Directed graph는 symmetric matrix가 아니므로, in-degree를 구할 때와 out-degree를 구할 때 각각 행을 따라 더하거나 열을 따라 더한다.
\( k_i^{out} = \sum\limits_{j=1}^N A_{ij} \)
\( k_j^{in} = \sum\limits_{i=1}^N A_{ij} \)
그리고 average degree는 다음과 같이 구한다.
\( L = \sum\limits_{i=1}^N k_i^{in} = \sum\limits_{j=1}^N k_j^{out} = \sum\limits_{i,j} A_{ij} \)
그런데, adjacency matrix는 그래프의 노드 수가 많아질수록(행렬의 size가 커질수록) 행렬이 sparse해진다. Sparse하다는 것은 matrix에서 의미있는 값인 1의 개수가 매우 작다는 뜻이다.) 실생활에서는 이와 같은 경우가 매우 많다.
이럴 때에는 나머지 방법인 edge list 혹은 adjacency list를 사용한다.
Edge List, Adjacency List
Edge list는 그래프를 edge, 즉 연결된 두 노드의 쌍의 list로 표현하는 방법이다.
위 그래프는 deep learning framework에서 다음과 같이 2차원 matrix를 통해 표현할 수 있다.
[(2,3), (2,4), (3,2), (3,4), (4,5), (5,2), (5,1)]
하지만 주어진 노드의 degree 계산이 어려워서 그래프를 조작하거나 분석하기 힘들다는 단점이 있다.
따라서 그래프를 조작하거나 분석할 때에는 인접 리스트를 사용한다.
인접 리스트는 출발 노드를 key값으로, 도착 노드를 value로 갖는 dictionary 구조이다. ('node : neighbor nodes' 형태)
위 예시 그래프를 adjacency list로 나타내면 다음과 같다.
{1 : [],
2 : [3, 4],
3 : [2, 4],
4 : [5],
5 : [1, 2]}
이에 따라 인접 리스트는 단방향 그래프를 표현하거나, 매우 큰(sparse한) 그래프를 나타낼 때 적합하다.
Connectivity of Undirected Graphs
그래프가 다음과 같이 연결되지 않은 두 개 이상의 connected component로 구성된 경우가 있다.
그 구성요소 중에서 가장 크기가 큰 component를 giant component라 하고, node H와 같이 edge 없이 고립된 node를 isolated node라 한다.
그리고, A와 F를 잇는 edge가 있다면, 삭제될 경우 connected graph에서 disconnected graph로 바뀌게 된다. 이를 bridge edge라 한다.
또한 node A와 같이 삭제될 경우 connected graph에서 disconnected graph로 바뀌는 node를 articulation node라 한다.
Disconnected graph의 경우 위와 같이 block-diagnoal 형태의 행렬로 표현된다. 그림을 보면 대각선 방향의 두 block 이외 요소들은 모두 0임을 알 수 있다. (각각의 block이 두 subgraph의 adjacency matrix가 될 것이다.)
Connected (direct) graph는 다음과 같이 나뉜다.
- Strongly connected directed graph
- 각 노드에서 다른 모든 노드로 가는 path가 있는 graph를 말한다. 즉, 어떤 노드에서 출발하던 edge 방향을 지키면서 다른 모든 노드로 갈 수 있다.
- (Connected) Undirected graph는 모두 여기에 해당될 것이다.
- 위 그림에서 A, B, C 부분만 떼내서 본다면, 해당 부분이 strongly connected일 것이다.
- Weakly connected directed graph
- 어떤 노드 하나라도 다른 모든 노드로 가는 path가 없을 경우를 말한다. 즉, 어떤 노드에서 출발하던 'edge 방향을 무시한다면' 다른 모든 노드로 갈 수 있다.
따라서 그래프의 하위 그래프(subgraph)를 strongly connected components (SCCs)로 구분할 수 있다.
외부에서 SCC로 들어올 수 있다면, 해당 노드는 in-component이고, SCC에서 해당 노드로 나갈 수 있다면, out-component이다.
최근댓글