작성자 : 신민정

Content
0. Intro
1. The Probelm : Graph Generation
2. Machine Learning for Graph Generation
3. GraphRNN : Generating Realistic Graphs
4. Applications and Open Questions

지난 강의에서는 Graph를 vector로 encoding하는 방법을 배웠습니다. Deep Graph Encoders

이번 강의에서는 graph를 generate하는 과정을 배우보겠습니다. Deep Graph Decoders

encoding된 vector으로 부터 grpah structure를 생성할 수 있습니다.

1. The Probelm : Graph Generation

graph generation의 목표는 realistic한 grpah를 생성하는 것입니다.

graph generation이 갖는 의의는 다음과 같습니다.

• Generation : graph 형성 과정에 대한 insight를 얻을 수 있습니다.
• Anomaly detection - 비정상적인 부분/동작이 발생하는 이유를 발견할 수 있습니다.
• Predictions - 과거로부터 미래를 예측할 수 있습니다.
• 새로운 구조를 발견할 수도 있습니다.
• Graph completion - many graphs are partially observed
• "What if" scenarios

graph generation의 목표에 따라 모델이 달라 질 수 있습니다.
Task1 : Realistic graph generation
->reference graph와 동일한(유사한) graph를 만들어야 합니다.
Task2 : Goal-directed graph generation
-> 주어진 조건과 제약에 맞게 graph를 만들어야 합니다. (예.Drug molecule generation/optimization)

이번 강의에서는 Task1 : Realistic graph generation에 대한 내용을 주로 다루겠습니다.

Graph Generation을 사용하는 task의 대표적인 예는 Drug Discovery입니다. 기존 분자 구조를 완성하여 desired property에 최적화된 새로운 약물을 발견할 수 있습니다.

이외에도 Discovering novel sturctures, Network Science(Null momdels for realistic networks) 같은 분야에도 사용됩니다.

하지만, 그래프를 생성하는 작업은 그리 쉽지 않습니다.
Grpah Generation은 왜 어려울까요??
output space가 크고 다양하기 때문입니다. $n$개의 node를 위해 $n^2$개의 값을 생성해야합니다. (인접행렬)

또한 7강에서 언급한 바와 같이, Graph의 표현은 고정되어있지 않습니다. 또한 정해진 순서도 없습니다. 같은 그래프이지만, node의 index가 다르면 다르게 표현되고, 이는 objective function으로 최적화하는데 어려움이 있습니다.

또한 복잡한 의존성(complex dependency)문제도 있습니다.(long-range dependencies) 만약 6개의 node가 있는 링 그래프를 생성하려면, 먼저 node가 있어야하고 그 node를 연결해야합니다. 연결하는 과정에서 우리가 현재 처리하고 있는 node의 수를 기억해야합니다. 그렇지않으면 우리가 원하는 조건을 만족하지 못할 수도 있습니다.
it's hard to generate a graph with respect to some specific conditions.

2. Machine Learning for Graph Generation

Graph Generative Model은 말 그대로 graph를 생성하는 모델입니다. 특정graph의 구조와 특징을 잘 닮은 현실적인 그래프를 생성하려고 합니다. reference graph들의 확률분포 $p_{data}(G)$가 있을 때, $p_{data}(G)$와 유사한 $p_{model}(G)$을 만들면됩니다. $p_{data}(G)$에서 sampling한 graph들이 주어지고, 이 그래프들로 $p_{data}(G)$를 만들면, $p_{data}(G)$에서 generated graph를 sampling합니다.

만약 "어떤 특징을 가지고 있는 분자"들의 확률 분포를 $p_{data}(G)$라고 하면, 그 확률 분포에서 sampling해온 reference graph들은 동일한 "어떤 특징"을 가지고 있을것입니다. $p_{data}$와 비슷하도록 학습된 $p_{model}$에서 sampling한 generated graph들도 "어떤 특징"을 가지고 있도록 하는것이 generation의 목표입니다. graph 도메인에서의 generative model은 graph의 node를 생성하는 것이 아닌, 전체 graph를 생성합니다.

Recap : Generative Model

Generative Model의 개념을 알아보겠습니다.
앞서 말씀드린 바와 같이 Generative Model의 목표는 기존 data의 확률분포 $P_{data}$와 유사한 $P_{model}$을 만드는 것입니다. 우리는 $P_{data}$에서 온 data $x~P_{data}$만 있을 뿐, $P_{data}$가 무엇인지 모릅니다. 학습 데이터로 모델 분포에 최적으로 근사시키는 변수 $\theta$를 찾게됩니다. 이는 결합확률 함수 형태로 표현 가능하며, 수치해석이 쉽도록 log 공간으로 변형시켜 maximum likliehood문제로 풀게됩니다.

대부분의 생성모델에서는 noise distribution에서 $z$를 sampling해옵니다. $z_i$~N(0,1)
Deep Neural Net으로 decoding하여 원하는 data를 생성합니다. $x_i=f(z_i;\theta)$

생성모델에는 많은 종류가 있는데, 오늘 배울 Graph Generation은 Auto-regressive model을 사용합니다. Tractable Density를 추정합니다. fully visible brief network의 일종으로, density를 명시하고 시작하며 likelihood $p(x)$를 모델링합니다.

chain rule을 통해 graph내의 모든 action(add node, add edge)에 대한 joint likelihood는 모든 action의 likelihood의 곱의 형태가 됩니다.

3. GraphRNN : Generating Realistic Graphs

idea : node와 edge를 sequencial하게 추가하면서 graph를 생성합니다.

• $\pi$ : node ordering(Graph의 node순서). Random으로 결정됩니다.
• $S^{\pi}$ : Graph의 node의 연결 sequence
  graph $G$ with node ordering $\pi$ can be uniquely mapped into a sequence of node and edge additions $S^{\pi}$
  (예. 1~5까지의 숫자를 가진 5개의 node의 sequence)

graph $G$의 node ordering $\pi$가 결정되면, sequence $S$는 unique하게 결정됩니다.
$S^{\pi}$의 원소 $S^{\pi}_n$은 모두 작은 graph입니다. 노드의 순서가 고정되면 전체 그래프를 생성하는 방법은 하나뿐입니다.

sequence $S^{\pi}$은 두 가지 level로 나뉩니다.

• Node-level : 새로운 node를 하나 추가합니다.
  
• Edge-level : 추가된 node와 기존 node를 잇는 edge(link)를 추가합니다.
  
  node-level을 한번 upedate하면, 그 node에 해당하는 edge-level을 update하고, 그 다음 node를 추가하는 node-level을 update하고 다시 edge-level을 update하는 과정을 반복합니다.

node-level squence의 요소마다 edge-level sequence가 있으므로, squence of sequence라고 합니다.

graph generation문제를 sequence generation문제로 볼 수 있습니다. sequence generation은 두 단계로 나뉩니다.

• Generate a state for a new node (Node-level sequence)
• Generate edge for the new node based on its state (Edge-level sequence)

sequence 생성이기 때문에 Recurrent Neural Network로 해결할 수 있습니다.

GraphRNN

GraphRNN은 두단계로 나뉩니다.

• node-level RNN : 새로운 node를 만들고, 만들어진 node는 edge-level RNN의 initial state가 됩니다.
• edge-level RNN : 이전 방법대로 한다면 Node 5를 생성할 때, Node 1~4까지의 모든 연결을 고려해야했습니다. 하지만 이제 새로운 node의 edge를 만듭니다. 만들어진 edge는 node-level RNN의 state를 update합니다.

이제 RNN으로 sequence를 만드는 방법에 대해 자세하게 알아보겠습니다. (RNN,LSTM,GRU...)

• $s_t$ : state for RNN after time $t$
• $x_t$ : input to RNN after time $t$
• $y_t$ : output of RNN after time $t$
• $W,U,V$ : parameter matrices
• $\sigma()$ : non-linearlity
  
  Auto-regressive model이기 때문에 이전 cell의 output이 다음 cell의 input으로 들어가는 구조이므로 $x_{t+1}=y_t$입니다.
  또한 처음 state와 처음 input인 $s_0,x_1$은 SOS(Start Of Sequence) start tocken으로 지정해주고, end tocken인 EOS(End Of Sequence)로 생성을 멈춰줍니다. (SOS,EOS $\rightarrow$ zero vector)
  
  하지만, 이렇게 $x_{t+1}=y_t$이라면 모델이 deterministic하여 같은 graph만 생성될 것입니다. (diversity가 없다.)
  따라서 이전 cell의 output을 다음 cell의 input으로 바로 넣어주는 것이 아닌, $y_t$로 확률을 출력하여, 그 확률 분포에 맞게 $x_{t+1}$을 sampling해줍니다. $x_{t+1}~y_t$
  RNN의 각 step의 output $y$는 확률 vector입니다.

Training

edge에 대한 Ground Truth(Adjacency matrix) $y^*$로 teacher forcing을 합니다.

teacher forcing
techer forcing이란, Ground Truth를 디코더의 다음 입력으로 넣어주는 기법입니다.

Loss

$y^*=\{1,0,1,....\}$ 로 Binary Cross Entropy를 계산합니다.
$L=-[y^*_1log(y_1) + (1-y^*_1)log(1-y_1)]$
BCE를 minimize하는 방향으로 학습합니다.
실제값 $y^*$=1이면 $y^*_1log(y_1)$ term을 최소화하고,
실제값 $y^*$==0이면 $(1-y^*_1)log(1-y_1)$ term을 최소화합니다.

training process

이 graph가 data로 주어졌습니다.

Node 1이 graph에 있다고 가정하고, Node2를 추가해보겠습니다.

Edge RNN은 Node 1과 Node 2사이의 edge를 예측합니다. 첫번째 Edge RNN cell에서 0.5의 확률을 output으로 출력했고, teacher forcing하기 때문에 실제 GT인 1을 다음 Edge RNN cell의 입력으로 넣어줍니다.

Edge RNN에 GT가 supervision으로 오게됩니다.

Edge RNN의 최종 output sequence {1}을 Node RNN의 입력으로 주어 다음 node level(Node 3)로 update합니다.

다음으로 Edge RNN은 새로운 노드 Node 3와 기존 Node들이 연결되어있는지 확인합니다. 역시 Edge RNN에서는 teacher forcing을 해줍니다.

다음으로 GT를 supervision으로 줍니다.

Edge RNN의 output인 결과를 Node RNN의 입력으로 보내줍니다.

동일하게 Edge RNN에서 edge에 대한 확률값을 예측하는데, Node 4는 아무 node와 연결되어있지 않으므로 graph 생성을 중단합니다.

reference graph (GT)를 가지고 BCE loss를 사용하여 전체 RNN layer에 대해 backprob을 진행합니다.

Test

Edge RNN의 output으로 나온 확률이 threshold이상일 경우 1, 반대의 경우에는 0값을 얻을 수 있습니다. GT가 없기 때문에, 이전 Edge RNNcell의 결과인 1 또는 0값이 다음 Edge RNN cell의 input으로 들어갑니다.

GraphRNN을 정리하자면, graph 생성은 node-level sequence과 edge-level sequence 두 단계로 진행되며, RNN을 사용하여 sequnce를 생성합니다.

Issue : Tractability

어느 node든지 모든 node와 연결될 수 있습니다. edge generation을 하기에 많은 단계를 거쳐야 합니다. 우선 전체 adjacency matrix가 필요하고, edge의 종속성이 너무 길어져 복잡해집니다. 이러한 한계를 해결하기 위해 BFS를 사용합니다.

기존 Random node ordering

Node 5 may connect to any/all previous nodes

• Node 1을 놓는다.
• Node 2를 놓는다.
• Node 2와 Node 1의 edge를 확률에 따라 생성한다.
• Node 3를 놓는다
• Node 3와 Node 2, Node 1의 edge를 확률에 따라 생성한다.
• Node 4를 놓는다.
  ......

BFS node ordering

• Node 4와 Node 1은 연결되어있지 않기 때문에, 어쩌라고...

BFS node ordering을 적용한 결과 Node ordering과 Edge generation 모두 시간복잡도가 대폭 줄게됩니다.

Evaluating Generated Graphs

GraphRNN같은 graph generative model로 생성한 graph가 reference와 얼마나 유사한지 어떻게 측정할 수 있을까요??

어느 그래프에나 적용할 수 있는 효율성있는 Graph Isomorphism test가 없습니다.
따라서 Visual similarity와 Graph statistics similarity로 두 그래프의 유사한 정도를 판단합니다.

4. Applications and Open Questions

GraphRNN은 앞서 한번 언급한 Drug Discovery에 사용될 수 있습니다.

• 주어진 목적에 따라 모델을 최적화 시켜야 합니다.(High score)
• 주어진 제약 조건을 지켜야합니다.(Valid)
• 실제 그래프 데이로부터 학습을 해야합니다.(Realisitc)

특정 요구 사항, 주어진 화학적 특성의 높은 점수, 화학적 valency와 realistic을 만족하도록, 세가지 다른 방향으로 접근을 했습니다.

• GCN + 강화학습
• adversarial training
• Policy Network in 강화학습

Drug Discovery에 대표적으로 사용되지만, graph generation은 아직 open problem이 많습니다.

• 3D,point cloud,scene graph같은 다른 domain에서의 graph generation
• 큰 그래프 생성
• Anomaly detection (예. real graph vs fake graph)

이번강의에서는 Graph Generation에 의의와 문제, ML으로 Graph를 생성하는 GraphRNN을 배워보았습니다.

Reference

https://zhuanlan.zhihu.com/p/147675627
https://tobigs.gitbook.io/tobigs-graph-study/chapter10.