[Graph Neural Networks] Basics of Graph

안녕하세요? 이번 포스팅에서는 Graph Neural Network에 관련된 첫번째 시리즈 내용을 적으려고 합니다.  주요 내용이나 자료들은 standford의 OCW cs224(Machine Learning with Graphs; Jure Leskovec)를 참고 했습니다. 

https://web.stanford.edu/class/cs224w/

CS224W | Home

 

오늘의 내용은 Graph의 기초입니다. Grah Neural Network에 들어가기 앞 서 기초적인 그래프 이론을 살펴보는 시간입니다.  그래프의 가장 기초적인 객체(object)는 node 혹은 vertex라고 불리는 정점이 있고, 이 정점들 간의 연결관계를 나타내는 link 혹은 edge가 있습니다.  각각 보통 N, E라는 문자로 대표해서 표기하는 경우가 많구요, 정점과 연결관계라는 구성요소를 통해 구성된 Graph 전체 시스템은 G(N, E)라고 표기합니다. 

 

그래프를 정량적으로 분석한다고 할 때, 가장 먼저 떠올릴 수 있는 것이 node에 얼마나 많은 link가 연결되었는지 그 연결 정도 일텐데요. 이것을 (Node) degree 라고 합니다. 이 degree라는 것은 개별 node에서 따져볼 수도 있고 그래프 전체에서 average degree를 생각해볼 수도 있습니다. 그런데, 여기서 주의할 점이 graph는 directed graph/undirected graph로 나뉜다는 점인데요. 예를들어 영화배우들의 네트워크를 생각해보고 이 배우들이 같이 출연했을 경우에 edge로 연결한다고 생각해 봅시다. 이런 경우 로버트 다우니 주니어(아이언맨)는 스칼렛 요한슨(블랙 위도우)와 연결될 수 있을테고, 이런 연결관계는 일방향의 성격이 아니기 때문에 방향성이 없는 undirected graph일 것입니다. 반대로, 우리 학계에서 논문저자들의 네트워크를 생각해볼까요? citation(인용) 관계는 인용을 하는 저자와 피인용을 당하는 저자가 있죠? 이런 경우에는 방향성이 존재할 것입니다. 이런 네트워크는 directed graph가 될 것입니다. 

 

 

Node 타입이 상이한 경우도 있습니다. 예를 들어 단백질과 화학약품 간의 관계를 나타내는 그래프가 있다면 여기서 node는 단백질이냐 혹은 화학약품이냐에 따라 서로 상이한(heterogenous)특성을 갖게 됩니다. 이런 그래프를 heterogenous graph라고 합니다. (node의 특성이 상이하지 않은 균질한 그래프는 homogenous graph라고 합니다)

 

자 지금까지 기본적인 용어와 그래프 타입에 대해서 말씀드린 것이구요(사실 그래프를 나누는 기준은 정말 많고 그에 따라 지칭하는 용어도 다양하지만 일단 가장 기본적 부분에 집중해보겠습니다). 이런 그래프를 수학이나 데이터 사이언스에서 다루려면 뭔가 수학적으로 정량화해서 그래프를 표기할 수 있는 방법이 필요할 것입니다. 

Adjacent Matrix(인접행렬) : 행/열을 그래프의 node에 대응시켜서 그 연결관계를 표시한 행렬입니다. 보통 A로 표기합니다. 사실 정의를 글씨만 봐서는 감을 잡기가 어렵고 예시를 보시면 쉽습니다. 

연결되어 있는 node 간에는 1 그렇지 않은 node 간에는 0을 부여하는 겁니다. undirected graph라면 연결되는 2개의 node끼리 방향이 없기 때문에 Adjacent matrix는 Transpose해도 동일한 symmetric형태여야 합니다. 

 

Adjacent matrix도 그래프의 특성에 따라 다양한 양상으로 나타날 수 있는데요. 가장 기본적인 unweighted이면서 undirected graph의 경우, edge의 개수는 adjacent matrix의 원소를 모두 더한 후 반으로 나누어주면 됩니다. (당연하겠죠? 어떤 edge에 대응되는 2개의 node 각각에 대해서 한번씩 세어졌을테니 반으로 나누면 원하는 값이 됩니다) average degree는 edge의 개수에 2배를 한 값을 node의 개수로 나누어주면 됩니다(이해가 안 가시면 노드 2개가 있고 연결되어 있는 미니 그래프를 한번 생각해보시죠). 

 

weighted, self-edge, multi-graph의 경우에도 비슷하지만 약간 다른형태로 Adjacent matrix로부터 edge의 개수, average degree를 계산해 낼 수 있습니다. 사실 뒤에서 다시 말씀드리겠지만 Adjacent matrix는 단지 이 값들을 계산하는데만 쓰이는 것이 아닌데요. 굉장히 중요한 역할들을 하게됩니다. 이건 뒤에서 다시 말씀드리도록 하겠습니다.  

 

Graph Isomorphism : 그래프 이소모피즘(Graph Isomorphism)은 두 그래프가 같은 구조인지 판단하는 개념입니다. 두 그래프가 이소몰픽(동형)이라면, 두 그래프는 동일한 노드 개수와 엣지 개수를 가지며, 노드 간의 연결 방식이 서로 대응됩니다. 자연계열 전공을 하신분들이라면 고등학교/학부1학년 때 배웠던 일반화학 기억하시겠죠? 이성질체냐 아니냐 열심히 따지셨을 겁니다. 그것과 비슷한 작업이라고 보시면 됩니다. 

 

사실 그래프의 기본이라고 해도 더 적자면 끝도 없지만, 일단 기초 개념은 이정도로 하겠습니다. 다음 포스팅에서는 Traditional (Graph) Machine Learning Scheme에 대해서 말씀드리겠습니다.