(8) GCN - What is Graph

 

 

 

 

What is Graph?¶

Graph란 Vertex의 Set과 Edge의 Set으로 구성되어 있는 구조를 말합니다.

Vertex는 꼭짓점을 말하며, 하나의 노드입니다.
Edge는 선분을 말하며, 각 노드간의 연결을 의미합니다.

예)
Social Graph: 나와 다른 사람간의 친밀도, 관계성을 나타내는 그래프
3D Mesh: 입체 구조를 삼각형이 여러 개 연결되어 있는 그래프의 형태로 나타내는 것
Molecular Graph: 화학에서 사용하는 분자 그래프

 

Types of Graph¶

1. Direction of Edge
   • Directed graph(유향 그래프) : Edge에 방향이 있어 어느 한 방향 또는 양 방향으로 이동할 수 있는 경우
   • Undirected graph(비유향 그래프) : Edge에 방향이 없고 양 방향으로 이동할 수 있는 경우
2. Strength of Edge
   • Weighted Graph(가중 그래프) : Edge에 값을 넣어 Vertex 사이의 거리(Distance) 혹은 Edge의 중요도(Weight)를 표현
   • Unweighted graph(비가중 그래프) : Edge에 값이 없으므로 모든 Edge가 동일함

 

How Computer Can Understand Graph Structure¶

이러한 그래프 구조를 컴퓨터가 이해할 수 있는 방법으로 전달하기 위한 방법의 종류에는 여러가지가 있습니다.
그 중에서 우리는 아래의 두 가지 행렬 표현으로 그래프 구조를 표현하도록 하겠습니다.

1. Adjacency Matrix
   • 노드 간의 Connectivity를 표현
   • 즉, 엣지의 정보를 나타내는 행렬
2. Node Feature Matrix
   • 각 노드에 담긴 정보들을 나타내는 행렬

아래의 그래프 구조를 예시로 들어, Adjacency Matrix와 Node Feature Matrix를 좀 더 자세히 알아보겠습니다.

 

Adjacency Matrix¶

Row와 Column 모두 노드인 행렬입니다.
두 노드가 연결되어 있으면 각 노드 간의 교점에서 1이상의 값을 갖고, 그렇지 않으면 0값 혹은 bonding 값을 가짐으로써 두 노드의 Connectivity를 나타냅니다.
(Weighted graph의 경우 weight값이 Adjacency Matrix의 값입니다.)

예를 들어 1번 노드의 경우 다른 모든 노드들과 연결되어 있어 Adajacency Matrix에서 모두 1의 값을 갖는 것을 알 수 있습니다.
또한 0번 노드는 1번, 4번 노드와 연결되어 있으므로 두 노드의 교점에서 1의 값을 갖습니다.

자기 자신에 대한 노드의 경우 1값을 가진 것을 주목해주시기 바랍니다.
원칙적으로 자신으로 회귀하는 엣지가 없는 경우 0값을 가져야 합니다.
(이는 바로 다음 파트인 Graph Convolution Network에서 그 이유를 설명하겠습니다.)

 

Node Feature Matrix¶

Row는 노드, Column은 노드가 갖는 특징(Feature)인 행렬입니다.
Row와 Column의 교점이 갖는 값은 각 노드의 Feature 값입니다.

위의 Feature Matrix를 보면 총 7개 Feature에 대해 5개의 노드가 갖는 값을 명시함으로써 각 노드의 성질을 나타내고 있습니다.

 

To Handle Graph Data¶

이제 처음에 예시로써 들었던 Social Graph와 같은 데이터를 딥러닝으로 분석하기 위해서 우리는 GCN (Graph Convolution Network) 이라는 구조를 알아보겠습니다.

(사실 GCN 이라는 구조에서 기존 CNN에서 사용하였던 Conv2D 레이어를 사용하지는 않습니다.
다만 Convolution을 사용하는 네트워크이므로 CNN 카테고리에 포함하였습니다.)