Chat HoPT 5

[Road to Graph Neural Network] 1. What is Graph? 본문

Graph/Road to Graph Neural Network

[Road to Graph Neural Network] 1. What is Graph?

thisis05 2024. 3. 10. 14:22

1. Graph?

우린 수많은 네트워크들 내에서 존재하며 살아간다. 우리가 많이 사용하는 인스타그램, 링크드인 등등의 SNS 역시 네트워크이고, 우리의 뇌, 세포, 정보 모두 네트워크를 이루고 있다. 이러한 네트워크를 Complex system, 즉 복잡계라고 한다.

이러한 Complex system의 공통점은 바로 구성 요소들끼리 복잡한 상호작용을 한다는 것이다. 이러한 복잡한 상호작용을 표현하는 일종의 “언어”가 그래프라고 생각하면 된다. 그래프의 예시를 보면서 차차 알아가보자.

소셜 네트워크 관계망

 

위 그림은 소셜 네트워크 관계망에서 주로 나타나는 상호작용을 표현한 것이다. 페이스북, 링크드인, 카카오톡 등 이런 소셜 네트워크에서는 사람들과 사람들 간의 상호작용이 일어난다. 여기서 구성요소는 사용자, 상호작용은 연락, 팔로잉 등등이 될 수 있을거다.

이커머스 [전자 상거래] 네트워크

 

위와 같이 이커머스 시스템 속에서도 사용자와 상품 간의 상호작용이 일어난다. 여기서 구성요소는 사용자, 상품 2가지 종류가 될 것이고 상호작용은 구매 여부, 평점 등이 될 수 있다.

 

이외에도 다양한 Complex system을 그래프로 표현할 수 있다. 일종의 비정형적인 네트워크 데이터들을 그래프라는 언어를 통해 나타낼 수 있는 것이다. 우리가 어떤 추상적인 개념을 언어로 나타내는 것처럼, 네트워크라는 추상적인 개념을 그래프를 통해 명시적으로 표현했다고 생각하면 된다.

따라서, 우리가 어떤 Complex system에 대해서 이해하고 이를 이용하여 어떤 Task를 진행하기 위해서는 이를 그래프에 잘 나타내고 그래프를 잘 분석할 수 있어야 하므로 그래프에 대한 이해가 굉장히 중요하다고 볼 수 있다.

2. Graph Notation

이제 그러면 그래프의 기본적인 개념들에 대해 알아보자.

 

$G = (V, E)$

그래프 예시

 

그래프는 기본적으로 Vertex와 Edge, 즉 노드와 엣지로 이루어져 있다. 앞서 설명했듯이, 어떤 복잡계를 이루는 구성요소들은 노드이고, 이 노드 간의 관계를 나타내는 것이 바로 Edge이다. 기본적으로는 위와 같이 노드들이 그래프 내에 존재할 때, 어떤 네트워크의 정의에 따라 두 노드가 연결되어 있다고 한다면 이를 Edge로 연결하여 위와 같이 표현한다.

또한 어떤 노드 A에 대해 Edge를 통해 연결되어 있는 노드의 집합을 $N_A$, 즉 A에 대한 Neighbor라고 정의한다. `

예를 들어 위 그래프에서의 $N_C$ = $\{A, B, D\}$가 될 것이다.

3. Graph Type

그래프는 여러 복잡한 네트워크를 표현하기 때문에, 좀 더 복잡한 종류로 표현되기도 한다. 아래와 같이 여러 카테고리 하에서 그래프의 종류를 구분할 수 있다.

(1) Homogeneous VS Heterogeneous

이름에서도 알 수 있듯이 동일한 종류로 구성된 그래프와 다양한 종류로 구성된 그래프로 나눌 수 있다. 이 “종류”는 노드와 엣지의 타입을 말한다.

영화 배우 그래프

 

위 그래프는 배우들의 관계를 나타낸 Homogeneous graph의 한 예시이다. 여기서 노드의 타입은 ‘배우’ 하나로 구성되어 있고, 엣지의 타입 역시 ‘영화’ 하나로 두 배우가 같은 영화에 등장했다면 연결되어 있음을 알 수 있다. 이처럼 노드와 엣지의 타입이 하나인 경우를 Homogeneous graph라 한다.

 

Academic 그래프 예시

 

위 그래프는 Paper들의 관계도를 표현한 Academic graph로 Heterogeneous graph의 한 예시이다. 여기서 노드의 타입은 논문, 논문의 제목, 저자 등 여러 타입이 존재하고, 엣지 역시 이 노드의 타입에 따라 여러 연결성이 존재하게 된다. 이렇게 노드와 엣지의 타입이 여러 개인 경우를 Heterogeneous graph라고 한다.

그렇다면 아까 봤던 이커머스에서의 전자상거래를 나타내는 그래프는 어떤 형태의 그래프일까?

이 역시 Heterogeneous graph이다. 다만, 이 경우 노드의 타입이 2개, 엣지의 타입이 1개인 특이 케이스로 Bipartite graph : 이종 그래프 라고 명명하고 있다. 추천 시스템에서 자주 쓰이는 그래프 형태이다.

 

(2) Directionality : directed VS undirected

 

우리는 인스타그램에서 내가 팔로우 하고 있지만 상대방은 날 팔로우하고 있지 않은 경우도 존재함을 알 수 있다. 이를 그래프적으로 해석하면, 팔로잉이라는 엣지가 무조건 양방향으로 존재하지는 않는다는 것이다. 즉 엣지의 방향성이 존재하는 경우가 생긴다. 이를 directed graph라고 한다.

 

undirected graph [왼쪽] / directed graph [오른쪽]

 

딱 보면 보이겠지만, 왼쪽이 방향성이 없는 undirected graph이고, 오른쪽이 directed graph이다. directed graph의 경우, 위와 같이 화살표를 통해 방향성을 표현해준다.

 

(3) weighted VS unweighted

또한 엣지가 단순 연결을 표현하는 것일수도 있지만, 연결 빈도를 고려한 연결, 혹은 평점 등으로 어떤 가중치가 부여되어 있을수도 있다. 이에 따라 unweighted와 weightd graph로 나눌 수 있다. 이 경우 그래프를 이용한 downstream task를 진행할 때 이 edge의 weight를 고려하여 진행해준다.

unweighted graph [왼쪽] / weighted graph [오른쪽]

 

왼쪽의 unweighted graph의 경우, 우리가 흔히 사용하는 페이스북 친구 , 가족 관계 여부 등 단순 연결을 표현하는 경우를 나타낼 수 있고, weighted graph의 경우 사람 간의 전화 연결 횟수, 두 오브젝트 간의 유사도 등 어떤 수치를 관계로 표현하여 나타낼 수 있다.

또한 위 분류는 엣지를 어떻게 표현하냐에 따라 한 네트워크에서 weighted와 unweighted 둘 다 표현할 수 있다.

이 외에도 그래프가 시간에 따라 변하는지를 기준으로 Static Graph와 Dynamic Graph로 나누는 등 여러 기준이 존재한다.

4. Adjacency Matrix

위와 같이 그래프를 표현할 수 있지만, 상당히 추상적인 부분들이 존재한다. 따라서 저차원적인 행렬 형태로 표현하는데 이를 Adjacency Matrix, 즉 인접행렬이라고 한다.

 

예시 그래프와 인접행렬

 

노드의 개수 N만큼 NxN Matrix를 통해 인접행렬을 표현한다. 각 행과 열에 있는 노드가 연결이 되어 있다면 1, 아니면 0이다. 물론 자기자신과는 따로 Edge가 있지 않은 이상 0으로 처리한다. 만약 이 그래프가 Weighted라면, 단순 1이 아닌 Weight를 넣어줄 수 있다. 또한 Directed Graph라 In degree와 Out degree, 즉 들어오거나 나가거나 2개로 나뉜다면 이에 따라 Adjacency Matrix를 2개를 만들 수 있다.

 

다만 보다시피 위 인접행렬은 0이 과도하게 많을 수 밖에 없기때문에 Sparsity, 즉 희소성을 갖게된다. 즉 이 말은 많은 0 때문에 실제로 정보를 포함하고 있는 것보다 훨씬 많은 양의 메모리를 쓴다는 단점이 있다.

그럼에도 불구하고 그래프의 고차원적 구조를 단순 행렬로 나타낼 수 있다는 장점이 있기에 아직까지 그래프 연산에서 많이 활용되는 행렬이라고 알고 있으면 된다.

 

 

기본적으로 앞으로 설명하는 내용은 (1) Homogeneous (2) Undirected (3) Unweighted 한 그래프를 대상으로 설명한다. 따로 언급하지 않는 이상 위와 같이 기본적인 형태의 Graph를 다루고 있다고 생각하면 된다.

 

  • Reference
  1. https://m.boostcourse.org/ai211/lecture/1163363
    네이버 부스트캠프 - 그래프와 추천시스템 신기정 교수님 강의 교안
  2. Stanford CS224W: Machine Learning with Graphs | 2021 | Lecture 1.1 - Why Graphs
    Stanford cs224w lecture