Chapter10. Deep Generative Models for Graphs

CS224W by 신윤종

^^ 신윤종박진혁바보

Deep Generative Models for Graphs

지난 강의에서는 Graph를 임베딩하는 Encoder를 배웠다.

• GCN, GraphSAGE

핵심은 Node embedding을 Local Neighbors로부터 Representation 정보를 Aggregate하면서 진행된다는 점이다.

Deep Graph Encoders

오늘은 그 반대인 Decoder 모델을 배워보

학습된 모델로부터 Graph를 생성하는 과정을 알아볼 것이다.

• Input은 무엇일까? Output의 정확한 형태는?

• 어떤 모델로 학습하는가? 목적함수는?

• 어따 쓰지?

Deep Graph Decoders

The Problem: Graph Generation

Intuitions : Why is it Important?

1. Generation - gives insight into the graph formation proces

2. Anomaly detection - (이상 그래프가 입력되었을 때 제대로 생성할 수 없기 때문?)

3. Predictions - predicting future from the past

4. Simulations of novel graph structures

5. Graph completion - 그래프의 일부만 주어졌을 때 이어서 그려나갈 수 있다.

6. What if scenarios

Graph Generation Tasks

Task 1) Realistic graph generation : 주어진 그래프와 비슷하게 만들어야 한다.

Task 2) Goal-directed graph generation : 주어진 목적/제약에 맞는 그래프를 생성해야 한다. e.g. Drug molecule generation/optimization

Discover highly drug-like molecules

Complete molecule to optimize property

Discovering novel structures

why is it Hard?

그러나 그래 자체를 다루기는 여간 까다롭지 않다.

첫 째 문제점은 Output space가 크고, 다양하다는 점이다. $n$개의 노로 인접행렬을 만든다면 $n^2$ 개의 Value가 생성된다.

Output space

둘 째는 한 그래의 Representation이 Unique하지 않다는 점이다. $n$개의 Node로 한 그래프$n!$종류로 나타낼 수 있다. 이는 학습 시 목적 함수의 계산과 최적화를 어렵게 만든다.

Non-unique representations

셋 째는 그래프 생성의 복잡한 의존성이다. Edge 정보는 long-range dependecies를 가지고 있어, 우리의 모델은 매 스텝마다 이러한 history를 기억하고 있어야한다.

Complex dependencies

Machine Learning for Graph Generation

• Given : $Pd(G)$로부터 Sampling된 Graphs
• Goal : $Pm(G)$의 distribution을 학습하고 이로부터 Sample을 뽑을 수 있어야 한다.

Graph Generative Models

1. Make P_model(x;θ) close to P_data(x)

• Key Principle : Maximum Likelihood

• 관측치 x의 확률분포를 가장 잘 설명하는 파라미터 $θ^*$를 학습하

2. Sample from P_model(x;θ)

• Goal : Sample from a complex distribution

• How : 정규분포로 샘플링 된 데이터 $z_i$를 함수 $f$를 통하여 변환한다. $x_i = f(z_i; θ)$

함수 $f$는 심층신경망으로 학습하여 구현하는 거고, 이제부터 배울 거임!

Auto-regressive models

• Dependence on what we done.

• $Pm(x;θ)$ 가 앞서 언급한 2가지 Task를 모두 수행한다.
• Apply chain rule : joint distribution은 조건부확률들의 곱이다.

  • $x$가 벡터라면 $x_t$는 t째 차원이다.
  • $x$가 문장이라면 $x_t$는 t째 단이다.
  • 우리 모델의경우 $x_t$는 t째 action이다(add Node, add Edge)

Graph RNN : Generating Realistic Graphs

Idea : RNN과 동일하게, 순차적으로 Node와 Edge를 추가하면서 Graph를 생성한다.

Graph G의 Node 순서를 $π$라고 했을 각 Node 별 Edge 연결정보 Sequence ​$S^π$를 사용한다. 이 벡터에 순차적으로 원소가 들어갔음을 명심하자.

Sequence$S^π$는 2개의 level로 나뉜다.

• Node-level : Node를 하나 추가한다.

• Edge-level : 기존 Node와 현재 Node를 연결하는 Edge를 그린다.

Node-level의 매 스텝은 Edge-level의 시퀀스에 해당한다.

강의에서는 Graph와 Node Ordering을 합쳐서 Sequence of Sequence라고 했다. Node ordering은 랜덤하게 선택된다고 한다.

Q : 왜 굳이 순서 정보가 필요한가?

A : 중요한 점은 노드의 순서 정보를 지킴으로써 그래프의 구조(Structure)정보가 유지된다.

지금까지 배운 Idea를 RNN에 적용하자!

GraphRNN : Two levels of RNN

• Node-level RNN : 각 Edge-level RNN의 initial state를 생성한다.

• Edge-level RNN : initial state로부터 새로 Node의 Edge를 생성한다.

• 다음 스텝의 인풋은 현재 스텝의 아웃풋 : $x_t+1$ = $y_t$
• SOS, EOS토큰이 사용된다 (Zero init.)

그러나, Model이 너무 잘 학습한다면 똑같은 Graph를 계속 찍어낸다는 문제점이 있다. (deterministic) 그래서 우리의 RNN을 수정하여 Output을 Edge연결 여부 그 자체가 아닌, 확률 정보를 출력하도록 만들자.

이 확률 정보를 다음 스텝에 적용하여 Input x(t+1)은 이전 스텝의 확률분포를 통하여 샘플링 된 벡터가 된다.

$y_t$가 베르누이 분포를 따른다고 할 때, $p$는 1이 될 확률을 나타낸다. 반대로 0이 될 확률은 자연스 $1-p$가 된다.

학습 시에는 Teacher Forcing으로 현재 스텝의 Output값이 틀렸더라도 다음 스텝에서는 정상 라벨을 넣어준다.

Loss는 Binary cross entropy를 최소화하는 방향으로 학습한다.

• 실제값=1이면 왼쪽 항을 최소화한다. 즉 $y_1$을 최대화한다.
• 실제값=0이면 오른쪽 항을 최소화한다. 즉 $y_1$을 최소화한.

• pdf ㄱ

Issue : Tractability

특정 노드는 이전 모든 노드와 연결될 수 있다. 이는 Edge 생성을 위한 계산과정이 엄청 복잡하다는 뜻이다. 이러한 문제점의 해결으로 너비우선탐색을 사용한다.

1. Node 4는 Node 1과 연결되지 않는다.

2. 우리는 Node 1의 모든 이웃이 연결되었음을 이미 알고있다.

3. 그러므로 앞으로도 Node 5, 그리고 이 이후로도 Node 1은 절대로 연결되지 않는다.

4. 우리는 이전 2 step까지의 기억만 가지고도 그래프를 완성할 수 있다. ( 기존에는 n-1 step까지 기억해야 했다)

너비우선탐색 알고리즘을 적용한 결과, Node ordering과 Edge generation 둘 다 획기적으로 시간복잡도가 줄었다.

Evaluating Graphs

생성된 그래프를 평가하기 위한 지표는 다음과 같다.

• Visual similarity

• Graph statistics similarity

교수님은 기존 Kronecker포함 다른 모델보다 GraphRNN의 우수하다는 것을 강조하셨다.

Applications and Open Questions

아까 그래프 생성의 Task중 Goal Directed Generation도 있었다. 예시를 들자면 분자구조를 생성하는 모델이 있다.

주어진 Task를 해결하기 위해선 다음과 같은 요구사항이 존재한다.

• 주어진 목적에 따라 모델을 최적화시켜야 한다. (High score)

• 주어진 제한조도 지켜야 한다.(Valid)

• 실제 그래프 데이로부터 학습을 해야한다.(Realisitc)

Graph Convoliutional Policy Network

GCN에 강화학습을 첨가하였다...

Open Problems

• 특정 도메인의 Graph를 생성하기 : 3D shape, point cloud, etc.

• Graph의 scale을 키우기 : 주어진 작은 Graph로부터 Subgraph를 쌓아가면서 크기를 키워나간다.

• Anomaly detection : 실제 그래프와 가짜 그래프를 비교하기위해 생성모델을 사용