커뮤니티2

Graph Nerual Network (GNN)은 다양한 분야에서 사용되는 방법입니다. 예를 들면, 교통 통행량 예측이라던지, 신약 개발이라던지, 특정 분야에 국한되지 않고 직속적으로 확장하고 있습니다. 가장 익숙한 예시는 페이스북과 링크드인 같은 SNS의 친구 추천과 대형 식료품점의 상품 추천도 있다.

이번부터 시작하는 포스트는 시리즈 형태로 작성을 하여 GNN을 사용하는 어플리케이션과 예제까지 담아볼 예정입니다. 그러기 위해, 그래프 (Graph)가 어떤것인지, 어떤 특성을 가지고 있는지에 대해서 이번 포스트에 작성해보려 한다.

그래프라고 구글에 검색하면 가장 먼저 발견하는건, 이런 이미지와 같은 Graph가 보일겁니다.

이것도 그래프는 맞긴 한데, 사담을 조금 얹자면, 실상 업무를 진행하다 보면 단순히 "그래프 형태로 ~해서 ~합니다" 라고 커뮤니케이션을 하면, 같이 연구를 하고 개발을 하는 팀원이 아니면 정확하게 의미가 전달되지 않을 수도 있겠다 (동음어와 심리학의 항상성)라는 생각을 문득 한 적이 있어서,  최근에는 "그래프 데이터 구조로 ~해서 ~합니다" 라는 형태로 커뮤니케이션을 하려고 노력중이긴 합니다. 

자, 그래서 GNN의 Graph란 뭐라고 말해야 할까?

굳이 따지자면, Graph는 자료구조라고 말해야 할것 같다. 

그래프가 가지고 있는 특성을 한번 살펴보자.

[Figure.1]

위의 그래프를 보았을때 어떤 생각이 나는가?

A와 B가 연결 되어 있구나, C와 F가 연결되어 있구나, C는 3개와 연결되어 있구나 등등, 다양한 생각을 할 수 있다.

그렇다면, 다음 그래프는 어떤 의미가 있을까?

[Figure.2]

이 그래프는 15세기 피렌체의 가문간 결혼 관계를 그래프로 보여준 것이다.

자, 이제 우리가 이런 자료구조로 무언가를 표현 할 수 있다는 것을 인지 했다면, 이 데이터를 저장하도록 입력을 해야한다. 그래프 데이터 구조를 우리가 머리속에 "그린" 대로 이미지로 저장하는 것이 아닌, 자료구조형태로 저장을 하려면 그래프 데이터의 구조를 알아야 한다.

첫번째 그래프를 예시로 들면, [ A, B, C, D, E, F, G ] 의 7개의 점, 오브젝트가 있고, 각 오브젝트는 선으로 연결 되어 있다. 이 연결은 점의 위치가 바껴도 변함이 없어야 한다.

[Figure.3]

[Figure. 4]

과연, 이 그래프들이 [Figure.3, Figure.4] 가 기존의 그래프[Figure.1]와 같을까?

정답은, [Figure.1]과 [Figure.3]은 같으나, [Figure.4]는 다르다.

[Figure.1, 3, 4]는 모두  [ A, B, C, D, E, F, G ] 의 7개의 점, Node 또는 Vertex를 가지고 있다. (쓰는 곳마다 Node[컴퓨터 공학] 라고 표기하는곳이 있고 Vertex [수학] 라고 표기하는곳이 있지만 같은 뜻이다)

노드를 표현하는 방법은 간단하다.

[Figure.5]

노드만 추가 했기 때문에 시각화를 하게 되면, 노드만 표현된다.

노드를 추가 했다면, 노드간의 연결 (edge 또는 Link 또는 Connection)을 표현해보면, 다음과 같이 표현 할 수 있다.

엣지를 추가할때는 (U, V)의 형태로, U에서 V로 간다 라는 의미를 가진다. (방향성)

[Figure.6]

이렇게 [Figure.1]과 동일한 그래프를 저장 할 수 있다.

그래프의 기본적인 자료는 위와 같이 저장 할 수 있으며, 추가적으로 정보를 더 담을 수 있다.

어디에, 어떻게 정보를 더 담을 수 있을까?

바로, 각 노드와 엣지에 정보를 더 담는 것이다.

예를 들어, A가 노드들 중에서 첫번째라는 것을 표현하기 위해 [1, 0, 0, 0, 0, 0, 0] 이라는 정보를 가지고 있다고 하자. 그럼 이런식으로 데이터를 표현 할 수 있다.

노드뒤의 data라는 Attribute는 임의로 지정이 가능하다.

이렇게 표현해도 동일한 그래프이다.

추가적으로, 모든 노드들이 동일한 특성 (Attribute 또는 Feature)를 가지고 있는 그래프를 "Homogeneous Graph" 라고 한다. 반대는 "Heterogeneous Graph"라고 한다.

그래프에서 노드와 노드의 정보를 추출 하려면 다음과 같이 확인 할 수 있다.

설명을 위해서 Networkx (링크) 라는 패키지를 사용하지만, 추후 GNN을 설명 할때에 Pytorch Geometric의 데이터 형태를 추가적으로 설명할 예정이다.

노드에 정보를 넣어봤으니, 엣지에도 정보를 넣어보자.

엣지는 연결을 표현하는 정보인데, 노드와 동일하게 정보를 넣을수 있다.

예시는 Importance라는 명으로 데이터를 넣었다.

엣지의 정보는 다음과 같이 확인 할 수 있다.

위와 같이 노드와 엣지에 추가적인 정보를 담을 수 있다. 

추가적인 정보, Attribute, Feature는 여러개를 가질수 있다.

그 외의 추가적인 정보가 무엇이 있을까? 

이번에는 SNS의 팔로우를 생각해보자. 팔로우 10만명인 인플루언서가 있는데, 이 사람은 10만명 모두와 연결되어 있을까? 그럴수도 있지만, 그렇지 않은 경우가 있을 것이다. 엣지를 데이터화 할 때, 사용했던, (U와 V)의 연결의 방향성 "U에서, V로 간다" 라는 것은 화살표로 표현하면, 이렇게 표현 할수 있다.

[Figure.7]

U에서 V로 가는 엣지를 화살표 방향으로 방향성을 표현하는 것인데, 이렇게 방향성이 있는 그래프를 Directed Graph라고 표현하고, 방향성이 없는, 또는 항상 양뱡향을 의미하는 그래프를 Undirected Graph라고 한다.

이전에 코드로 작성한 데이터는 Directed Graph로 표기하면, 아래와 같은 그림을 가지게 된다.

[Figure.8]

지금까지 위의 그래프를 데이터로 저장하기 위해 Networkx를 통해 데이터를 저장하는 방법을 알아보았다.

그런데 일반적으로 자료구조를 저장할때에는 특정 패키지가 아닌 다른 구조를 사용하는게 일반적이다.

노드와 엣지를 일반적인 형태로 저장한다면 다음과 같이 저장 할 수 있다.

노드와 attributes

 배열로 노드를 저장할때에는, 노드의 순서 (index)를 고려해야한다.

엣지는 두가지 방법으로 나타낼수 있다.

첫번째 방법은 edge_list 형식으로 U, V 패어 형식의 리스트이다.

두번째 방법은 Adjacency Matrix 형식으로 아래와 같이 표현 할 수 있다.

Adjacency Matrix형식에서 Row와 Column은 각 노드의 인덱스를 지칭한다.

예를 들어 첫번째 줄에 있는 [0, 1, 1, 0, 0, 0, 0]은

0번째 노드는 1번 노드, 2번 노드와 연결 되어 있다라는 의미이다.

0번째 노드는 A이고, 1번 노드는 B, 2번 노드는 C로 노드를 정의 했었다.

연결이 되어 있다면 1, 그렇지 않다면 0으로 표기하는 희소행렬 형태이다.

만약 Importance라는 엣지 피쳐를 추가 한다면, 다음과 같이 저장 할 수 있다.

이렇게 표기된 Adjacency Matrix는 Weight Matrix라고 표현하기도 한다.

지금까지 그래프 데이터의 의미와 타입, 데이터를 저장하는 방식에 대해서 알아보았다.

그래프 데이터 구조는 노드와 엣지에 다양한 속성을 저장 할 수 있고, 노드간의 관계를 저장할수 있는 데이터 구조로 현실의 복잡한 시스템을 표현하는데 좋은 데이터 구조같다. 아래 표는 그래프 데이터, 이미지, 테이블 데이터의 비교표이다.

다음 포스트는 그래프 데이터를 통해 그래프를 통계적으로 분석하는 방법에 대해서 알아보는 포스트를 작성해보려 한다.