GraphRNN은 graph generative model의 하나로, RNN처럼 sequential하고 autoregressive하게 노드와 엣지를 추가함으로써 그래프를 생성하는 모델을 말한다. 이번 글에서는 GraphRNN이 무엇인지에 대해서 GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models 논문을 리뷰하면서 알아보겠다.
* 이 글은 RNN에 대한 기본적인 이해가 있다고 가정한다.
배경
우선, GraphRNN이 제안된 배경에 대해 먼저 살펴보겠다. GraphRNN은 아래 그림과 같이 sequential하고 autoregressive하게 노드와 엣지를 추가함으로써 그래프를 생성한다. (Autoregressive는 앞서 만들어진 past value들에 dependent하게 future value들이 결정되는 것을 말한다.)
그렇다면 이렇게 그래프를 sequential하고 autoregressive하게 만들어야 하는 이유는 무엇일까? 그것은 그래프 내의 노드들과 엣지들은 서로 independent하지 않기 때문이다. 그래프 안에 있는 노드들과 엣지들은 서로 독립적인 포인트들이 아니라, 서로 연관이 있는 dependent한 관계에 있기 때문에, 그래프를 만들 때에도 이러한 관계를 고려해야 한다. 그러므로 그래프를 autoregressive하게 이미 만들어진 노드와 엣지를 고려하여 노드와 엣지를 추가하는 방식으로 generate함으로써 그들 사이의 dependent한 관계까지 고려할 수 있는 것이다.
Approach
GraphRNN은 1) 그래프를 sequence로 표현하고 (modeling graphs as sequences), 2) 이 sequence에 대해 autoregressive한 generative model을 만드는 (build autoregressive generative models) 두 가지 단계로 이루어져 있다.
그래프를 sequence 형태로 표현함으로써 RNN을 적용할 수 있게 되고, 결과적으로 autoregressive generative model을 적용할 수 있게 되는 것이다. 이 두 단계에 대해 좀 더 자세히 알아보도록 하겠다.
Modeling graphs as sequences
첫 번째 단계는 그래프 G를 노드와 엣지의 addition으로 이루어진 sequence S_pi로 표현하는 것이다. 이 때, 노드 간의 순서가 정해져 있지 않다면, 하나의 그래프를 표현하는 sequence가 매우 많아질 것이다. 그래서 우리는, 노드 ordering pi를 따르는 그래프 G를 sequence S_pi로 표현한다. 이를 식으로 나타내면 다음과 같다.
위 식에서 f_S는 그래프를 sequence로 매핑하는 함수이고, 각 S_i^pi는 i번째 노드가 이전에 만들어진 노드와 가지는 adjacency vector이다. 예를 들어, 다음과 같은 그래프가 있다고 하자.
이 그래프의 node ordering이 위 그림에 써있는 노드 숫자와 동일하다고 할 때, 우리는 이 그래프를 다음과 같은 sequence 형태로 표현할 수 있다.
위 그림에서, S_3^pi를 예시로 들면, 이는 노드 3이 노드 1과 연결되고, 노드 2와 연결되지 않음을 표현해야 하므로 (1 0)^T로 표현되는 것이다.
이렇게 그래프를 sequence 형태로 표현함으로써 우리는 graph generation 문제를 sequence generation 문제로 바꿔서 볼 수 있다. 즉, p(G)를 학습하는 것이 아니라 p(S^pi)를 학습하는 것을 우리의 목적으로 삼을 수 있는 것이다. 이는 식으로 나타내면 아래와 같다.
즉, 그래프 G의 분포는 그래프 G를 나타낼 수 있는 모든 sequence의 분포의 합으로 표현할 수 있는 것이다. 위 식에서 p(S^pi)는 다음과 같은 식으로 표현할 수 있다.
즉, 앞에 만들어진 노드의 adjacency vector가 주어졌을 때, 현재 노드의 adjacency vector가 가질 conditional distribution의 곱으로 표현할 수 있는 것이다. 여기서 우리는 GraphRNN의 autoregressive한 특성을 알 수 있다.
Breadth-first-search (BFS) node ordering
우리는 위에서 node ordering이 주어졌을 때 그래프를 sequence 형태로 어떻게 표현할 수 있는지에 대해 알아보았다. 하지만 우리는 수많은 node oredering들을 가질 수 있고, 이 모든 node ordering에 대해 네트워크를 학습하는 것은 굉장히 비용이 많이 드는 일일 것이다. 그렇기 때문에 우리는 BFS node ordering을 사용한다. 즉, 주어진 node ordering pi에서 첫 번째 노드를 뽑고, 그 노드의 이웃들을 하나씩 queue에 더하는 BFS를 따르는 node ordering을 사용하는 것이다. 이 때, 이웃들 간의 순서는 pi에서 정해진 순서를 따른다. 이를 식으로 나타내면 아래와 같다.
예를 들어, 아래 그림에서 왼쪽의 그래프는 BFS node ordering을 따른 그래프, 오른쪽은 그렇지 않은 그래프이다.
이렇게 BFS node ordering을 따르면, 학습 단계에서 BFS ordering을 따르는 sequence만 학습하면 되기 때문에 그 complexity가 굉장히 낮아지게 된다.
Autoregressive generative models
이렇게 sequence 형태로 그래프를 표현함으로써 우리는 autoregressive한 형태로 그래프를 generate할 수 있게 되었다. 이 단계에서 우리는 graph-level RNN, edge-level RNN의 2개의 RNN을 사용하게 된다. (full GraphRNN만 설명하겠다.)
여기서 graph-level RNN은 edge-level RNN의 input으로 사용되는 initial state를 만드는 역할을 하고, edge-level RNN은 다음 단계에서 추가될 새로운 노드가 기존에 만들어진 노드들과 어떻게 연결되어 있는지를 표시하는 adjacency vector를 만드는 역할을 한다. 이 autoregressive generative model은 다음과 같은 순서로 진행된다.
- Graph-level RNN을 통해 새로운 노드를 하나 만든다.
- Edge-level RNN을 통해 1에서 만들어진 새로운 노드를 위한 엣지들을 만든다.
- 1과 2의 결과를 바탕으로 또다른 새로운 노드를 만든다.
- 1, 2, 3을 반복한다.
- Edge-level RNN이 모든 노드들에 대해 0을 만들어내면 (새로 만들어진 노드가 기존 모든 노드에 연결되지 않는다는 의미 - End Of Sequence) 종료한다.
이를 pseudo code로 표현하면 아래와 같다.
여기서 h_i는 현재까지 만들어진 graph의 state를 표현하고, f_trans는 graph-level RNN, f_out은 edge-level RNN을 말한다. 이 때, 이 edge-level RNN은 다음과 같은 식을 따른다.
Experiment
GraphRNN이 잘 작동하는지에 대한 실험 결과는 아래와 같다.
위 그림을 보면, training data가 regular한 grid 형태이든, realistic한 ego network 형태이든 GraphRNN으로부터 만들어진 graph들이 각각의 training data 특성을 잘 따르는 것을 알 수 있다. 즉, GraphRNN은 그래프의 다양한 구조적 특징을 모두 잘 capture할 수 있는 것이다.
이번 글을 통해 우리는 graph를 autoregressive하게 generate하는 GraphRNN이 어떻게 작동하는지에 대해 알아보았다.
References
You, J., Ying, R., Ren, X., Hamilton, W., & Leskovec, J. (2018, July). GraphRNN: Generating realistic graphs with deep auto-regressive models. In International conference on machine learning (pp. 5708-5717). PMLR.
최근댓글