[Study]Chapter 15. Deep Generative Models for Graphs
해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.
해당 챕터에서는 신경망을 이용해 그래프 생성 모델을 구축하는 것에 대해 배웁니다.
I. ML for Graph Generation
그래프를 생성하는 Task에는 아래와 같이 두 가지가 존재합니다.
현실적인 그래프 생성목표 지향 그래프 생성
이 중 첫번째 Task에 대해서 이야기 합니다.
1. Graph Generative models
그래프 생성 모델은 $p_{data}(G)$가 주어졌을떄 $p_{model}(G)$의 분포를 학습하고 샘플을 추출하는 것입니다.
밀도추정: $p_{model}(x; \theta)$을 $p_{data}(x)$에 근접시킨다.Figure 1 : Maximum Likelihood
샘플링: $p_{model}(x; \theta)$흔한 접근법 두가지
단순한 noise 분포에서 샘플링하는 방법
\[z_i = N(0,1)\]특정 함수를 통해 noise z를 변환하는 방법
\[x_i = f(z_i; \theta)\]
2. Auto-regressive models
Figure 17 : Autoregressive(AR) 모델은 주어진 데이터의 확률 분포를 모델링하는데 사용되는 모델중 하나
$p_{model}(x;\theta)$는 밀도 추정과 샘플링을 사용합니다. 이외의 다른모델인 VAEs, GANs 들은 2개 이상의 모델을 가지고 각자 다른 역할을 가지고 있습니다.
아래와 같이 Chain rule을 이용한 결합 분포로 조건부 분포들의 곱입니다.
\[p_{model}(x;\theta) = \Pi_{t=1}^np_{model}(x_t|x_1,...,x_{t-1};\theta)\]II. Generating Realistic Graphs
현실적인 그래프 데이터를 생성하는 모델 중 하나인 GraphRNN1에 대해 설명합니다.
Figure 2 : 정리된 노드 \(\pi\)를 가지는 그래프 G는 노드와 edge의 addition인 \(S_{\pi}\)로 그려진다.
연속된 $S_{\pi}$는 2개의 level을 가집니다.
- Node-level : 노드를 추가하는것 각 단계에서 새로운 노드가 추가
- Edge-level : 존재하는 노드들 사이의 edge를 추가, 각 노드 레벨 단계는 edge-level이다.
예시로
- Node-level : \(S^\pi=(S^\pi_1,S^\pi_2,S^\pi_3,...)\)
- Edge-level : \(S^\pi_1 = (S^\pi_{1,2},S^\pi_{1,3},S^\pi_{1,4}) = (1,1,0)\)
Figure 3 : 각 level은 인접행렬을 통해 확인할 수 있다
그래프 생성 문제를 시퀀스 생성 문제로 변환할 수있다.
- 새로운 노드의 상태를 생성하는 것(Node-level sequence)
- 해당 상태를 가지고 새로운 노드의 edge를 생성하는 것(edge-level sequence)
시퀀스 생성 문제에 RNN을 모델에 적용하여 사용합니다.
1. Background RNN
Graph RNN은 두가지의 nodel-level RNN과 edge-level RNN을 가집니다. node-level RNN은 edge-level RNN의 초기 입력 상태를 생성하고 edge-level RNN은 새 노드가 이전 노드와 연결되었는지를 순차적으로 예측합니다.
Figure 4 : 노드 레벨은 이전 노드 상태와 엣지 상태를 가지고 다음 노드를 생성하고, 엣지 레벨은 현재 노드의 상태를 가지고 순차적으로 연결 상태를 예측합니다.
우리 확률모델 \(\Pi_{t=1}^np_{model}(x_t\|x_1,...,x_{t-1};\theta)\)를 얻는 것이기에 결정적인 방법인\(x_{t+1}=y_t\) 보다 \(y_t=p_{model}(x_t\|x_1,...,x_{t-1};\theta)\)로 설정합니다.
그러면 $y_t:x_{t+1}\sim y_t$로 부터 나온 sample $x_{t+1}$가 필요합니다. 따라서 RNN 각 단계의 결과물은 single edge의 확률로 분포에서 샘플을 뽑아 다음 스텝으로 넣어줍니다.
Figure 6 : 이전 RNN cell 결과를 다음 RNN cell의 입력으로 조건부확률분포를 넣는다.
2. Training
교사 강요\(_{Teacher-Forcing}\)2로 관측된 edge들의 시퀀스 y*의 학습을 진행합니다.
\[L = -[y_1^*log(y_1)+(1-y_1^*)log(1-y_1)]\]\(y_1^*\)가 1이면 \(-log(y_1)\)을 최소화하기위해 $y_1$을 높게 만들어야한다. 0이면 $-log(1-y_1)$를 최소화하기 위해 $y_1$을 작게 만들어야 합니다. 이러한 방법으로 $y_1$을 샘플 데이터$ y_1^*$로 적합시킵니다. 그러면 $y_1$은 RNN으로 인해 계산되고 해당 loss는 역전파를 사용해 RNN 파라미터를 조절하게 됩니다.
Figure 7 : 실제 데이터를 가지고 학습을 진행하고, test시 학습된 분포를 가지고 RNN cell의 예측을 진행함
3. Tractability via BFS
노드는 어느 사전 노드와도 연결될 수 있기에 edge의 생성단계가 많아져 전체 인접행렬을 생성해야하고, edge 종속성이 복잡해 집니다. 이러한 복잡성을 해결하기 위해 BFS를 사용할 수 있습니다.
Figure 8 : BFS node ordering
Figure 8에서 노드 4가 노드 1과 연결이 안되어있을때, 이전에 노드 1의 모든 이웃들을 방문한 상태이므로 노드 5와 노드 1은 이웃이 아니었기에 연결되지 않습니다.
Figure 9 : BFS를 통해 edge 생성의 단계를 줄일 수 있습니다.
4. evaluation
이렇게 Graph RNN을 통해 만들어진 그래프를 평가하기 위해 실제 그래프와 생성된 그래프가 얼마나 유사한지 비교과정이 필요합니다.
이러한 방법은 그래프의 유사도 metrics를 정의해야 합니다.
visual similarityFigure 10 : (좌) 격자형태 기반의 시각화 (우) 커뮤니티 기반의 시각화
Graph statistic similarity위의 시각화 방법의 유사도보다 조금 더 엄격한\(_{rigorous}\) 비교가 필요합니다. 두 그래프의 직접적인 비교는 isomorphic 문제로 NP-hard입니다. 따라서, 확률 분포인 그래프 통계량들을 활용하여 비교합니다.
각 그래프의 통계량을 구한 후 비교하는 방법은 아래와 같습니다.
EMD : Earth Mover Distance
Figure 11 : 두 그래프의 통계량을 어떻게 비교, 한 분포에서 다른 분포로 이동하는 최소의 노력을 측정.
EMD에 기반한 MMD3
Figure 12 : 각 그래프의 EMD를 구한 후 L2 거리를 활용해 그래프 통계량의 집합을 비교
III. Application of Deep Graph Generative Models
이러한 딥러닝 기반의 그래프 생성 모델의 활용으로 최적화된 속성 점수를 가지는 유효하고 현실적인 분자 생성하기 위해 활용될 수 있습니다.
이를 알기위해 먼저 목표 지향적\(_{Goal-Directed}\)으로 그래프를 생성하는 것을 알아야합니다.
목표 지향적으로 그래프 생성하는 것은 아래와 같습니다.
- 목적함수를 최적화(높은 점수)
- 도메인의 기본 규칙을 준수(유효)
- 예제에서 학습(현실적)
이러한 그래프 생성이 ML에서 어려운 이유는 블랙 박스가 포함되어있기 때문입니다.
Figure 13
따라서, 강화학습을 통해 ML 에이전트는 환경, 작업, 환경과의 상호작용, 행동, 보상 등을 파악하여 Figure 13의 루프에서 학습을 진행해 ML 에이전트가 직접적으로 환경에서 블랙박스를 학습하게 합니다.
1. GCNP
GCPN4은 Graph Convoluitinal Policty Network로 그래프 생성과 강화학습을 함께 사용하는 방법입니다.
이러한 방법은 GNN을 통해 그래프의 구조적인 정보를 수집하고, 강화학습으로 목표 지향적인 그래프 생성을 이끌어 냅니다. 그리고 지도 학습으로 데이터셋의 예제를 사용해 학습됩니다.
GraphRNN과 비교하여 GCPN의 주된 공통점으로는 그래프를 순차적으로 생성하고 데이터셋을 모방하는 방식입니다. 이와 반대로 GCPN은 GNN을 사용하여 generation action(RNN보다 잘 되지만 시간이 걸림)을 예측합니다. 또한, RL을 사용해 그래프 생성을 목표 지향적으로 접근이 가능합니다. 즉, GraphRNN은 RNN 은닉 상태에 기반하여 행동을 예측하고, GCPN은 GNN 노드 임베딩에 기반하여 행동을 예측합니다.
Figure 14 : GraphRNN vs GCPN
2.Overview of GCPN
Figure 15 : (a) 노드 입력,(b, c) GNN을 사용하여 어느노드가 연결되었는지 예측,(d) action을 취함,(e, f) 보상 계산(reward = final reword + step reward), step reward - 유효한 액션을 학습, 각 단계에서 유효한 액션을 위해 작은 양의 리워드를 배정,Final reward - 원하는 속성을 최적화, 마지막에 많이 원하는 속성에 긍정적인 reward를 배정
따라서 GCPN은 아래와 같이 두 가지 파트로 구성됩니다.
- 지도 학습 : 실제 관측된 그래프에서의 action을 모방하여 정책을 학습
- 강화 학습 : reward를 최적화하여 정책을 학습한다. 표준적인 정책 gradient 알고리즘을 사용
Figure 16 : GCPN의 지도 학습과 강화학습 파트
GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models. J. You, (ICML), 2018. ↩
(입력과 출력을 실제 시퀀스로 교체) ↩
Maximum Mean Discrepancy, https://jrc-park.tistory.com/281 ↩
Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation. J. You. (NeurIPS), 2018. ↩