> For the complete documentation index, see [llms.txt](https://tobigs.gitbook.io/tobigs-graph-study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tobigs.gitbook.io/tobigs-graph-study/chapter10..md).

# Chapter10. Deep Generative Models for Graphs

^^ ~~신윤종~~박진혁바보

## Deep Generative Models for Graphs

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

* GCN, GraphSAGE

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

![Deep Graph Encoders](/files/-M6y08llcbea_czt-0SM)

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

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

* Input은 무엇일까? Output의 정확한 형태는?
* 어떤 모델로 학습하는가? 목적함수는?
* 어따 쓰지?

![Deep Graph Decoders](/files/-M6y1lHapM9jAGMMS_dK)

## 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](/files/-M6y4_wtsRROUM8HShgB)

![Complete molecule to optimize property](/files/-M6y4dOSs_WbIHr0xkaS)

![Discovering novel structures](/files/-M6y5LbE2ItOpkMA3PiW)

### why is it Hard?

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

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

![Output space](/files/-M6y9v7_uSS9Kdkzp2Eo)

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

![Non-unique representations](/files/-M6y9LtvZA9D12Fe17Q_)

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

![Complex dependencies](/files/-M6yAat2F7rUbMCybZb-)

## Machine Learning for Graph Generation

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

![](/files/-M6yI1IMuKGJTtqwt04o)

![Graph Generative Models](/files/-M6yEN3FdB_DU7qNpHRF)

#### 1. Make P\_model(x;θ) close to P\_data(x)

* Key Principle : Maximum Likelihood
* 관측치 x의 확률분포를 가장 잘 설명하는 파라미터 $$θ^\*$$를 학습하

![](/files/-M6yINO6XWf-pDwsu4JG)

#### 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)

![](/files/-M6z1qvXA_3Fjro7CZ9b)

### Graph RNN : Generating Realistic Graphs

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

![](/files/-M6z3cNwPioCprQmIGMP)

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

![](/files/-M6z4-7nfiIx1BJ44tiU)

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

* Node-level : Node를 하나 추가한다.
* Edge-level : 기존 Node와 현재 Node를 연결하는 Edge를 그린다.

![](/files/-M6z6cVPZpraUa7j_J8A)

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

![](/files/-M6z6ilzeYqHRxTsb1pv)

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

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

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

![](/files/-M6z8H9Soex-mOsyjxBp)

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

#### GraphRNN : Two levels of RNN

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

![](/files/-M6z9q0u-o6SBMRsTfBc)

![](/files/-M6zDH3k7A4S9H2hnTjm)

* 다음 스텝의 인풋은 현재 스텝의 아웃풋 : $$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$$가 된다.

![](/files/-M6zPoRNVlObS6-tABuO)

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

![](/files/-M73PCiPK1QggUhKbex7)

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

* 실제값=1이면  왼쪽 항을 최소화한다. 즉 $$y\_1$$을 최대화한다.
* 실제값=0이면 오른쪽 항을 최소화한다. 즉 $$y\_1$$을 최소화한.

![](/files/-M73PsmGQdX0UFJePgdV)

* pdf ㄱ

#### Issue : Tractability

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

![](/files/-M73TqAsDz4NVBYNoNDz)

1.  Node 4는 Node 1과 연결되지 않는다.
2. 우리는 Node 1의 모든 이웃이 연결되었음을 이미 알고있다.
3. 그러므로 앞으로도 Node 5, 그리고 이 이후로도 Node 1은 절대로 연결되지 않는다.
4. 우리는 이전 2 step까지의 기억만 가지고도 그래프를 완성할 수 있다. ( 기존에는 n-1 step까지 기억해야 했다)

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

![](/files/-M779oS851u8_FRdderL)

#### Evaluating Graphs

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

* Visual similarity
* Graph statistics similarity

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

![](/files/-M77AKfhyLfXWyGa4ehD)

#### Applications and Open Questions

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

![](/files/-M77CuTHZzneivC9EHN4)

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

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

#### Graph Convoliutional Policy Network

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

![](/files/-M77Ba2J-k5naFnt23lP)

![](/files/-M77C0Z7bfraztEh9A74)

![](/files/-M77Br1BGKy9qKOtErJ6)

#### Open Problems 

* 특정 도메인의 Graph를 생성하기 : 3D shape, point cloud, etc.
* Graph의 scale을 키우기 : 주어진 작은 Graph로부터 Subgraph를 쌓아가면서 크기를 키워나간다.
* Anomaly detection : 실제 그래프와 가짜 그래프를 비교하기위해 생성모델을 사용