> 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

CS224W by 신윤종

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

## Deep Generative Models for Graphs

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

* GCN, GraphSAGE

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

![Deep Graph Encoders](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6y-r9vjc2MvYpflR5G%2F-M6y08llcbea_czt-0SM%2Fimage.png?alt=media\&token=034a3e5f-ae75-48ca-a1a1-bd28c3095748)

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

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

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

![Deep Graph Decoders](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6y-r9vjc2MvYpflR5G%2F-M6y1lHapM9jAGMMS_dK%2Fimage.png?alt=media\&token=5b91028c-26bf-4f30-bed0-a8617182aa14)

## 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](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6y-r9vjc2MvYpflR5G%2F-M6y4_wtsRROUM8HShgB%2Fimage.png?alt=media\&token=41903ae2-1c16-4568-bccb-8cb548a6fefa)

![Complete molecule to optimize property](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6y-r9vjc2MvYpflR5G%2F-M6y4dOSs_WbIHr0xkaS%2Fimage.png?alt=media\&token=e5d6ac3c-1aa3-4395-a5ee-a1934688422e)

![Discovering novel structures](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6y-r9vjc2MvYpflR5G%2F-M6y5LbE2ItOpkMA3PiW%2Fimage.png?alt=media\&token=da36e7d0-5dad-4bb4-bae0-8e261d4a2019)

### why is it Hard?

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

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

![Output space](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6y6pVhH5LUJfLLpEmE%2F-M6y9v7_uSS9Kdkzp2Eo%2Fimage.png?alt=media\&token=518bd20c-e2a9-4057-abd0-4d55ea3efaf2)

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

![Non-unique representations](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6y6pVhH5LUJfLLpEmE%2F-M6y9LtvZA9D12Fe17Q_%2Fimage.png?alt=media\&token=c80ab1c9-375d-4516-9b3e-b15f843e85de)

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

![Complex dependencies](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6y6pVhH5LUJfLLpEmE%2F-M6yAat2F7rUbMCybZb-%2Fimage.png?alt=media\&token=54aa1e9a-a605-4bbd-a2c9-3fb824a4f037)

## Machine Learning for Graph Generation

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6yH0VWFWUviN5TigMQ%2F-M6yI1IMuKGJTtqwt04o%2Fimage.png?alt=media\&token=d8566c10-d3c1-4a6b-9b84-da725337d601)

![Graph Generative Models](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6y6pVhH5LUJfLLpEmE%2F-M6yEN3FdB_DU7qNpHRF%2Fimage.png?alt=media\&token=76895d8c-3a7e-44b4-8b24-b4872c561433)

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

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6yH0VWFWUviN5TigMQ%2F-M6yINO6XWf-pDwsu4JG%2Fimage.png?alt=media\&token=d66d12dc-def8-4cd8-8a76-86bd46d9b661)

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6yymant48XnDs4CTgp%2F-M6z1qvXA_3Fjro7CZ9b%2Fimage.png?alt=media\&token=83f9ee9b-a95e-4b7a-a30e-b159500859ec)

### Graph RNN : Generating Realistic Graphs

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6z2voQjDrd2NM8d04p%2F-M6z3cNwPioCprQmIGMP%2Fimage.png?alt=media\&token=11ec1fb7-077e-4cc3-ba3b-9cc3f1948192)

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6z3t9aGJkAJgsZJo47%2F-M6z4-7nfiIx1BJ44tiU%2Fimage.png?alt=media\&token=a3333aef-b2ad-48d2-9037-c14c036d6329)

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

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6z3t9aGJkAJgsZJo47%2F-M6z6cVPZpraUa7j_J8A%2Fimage.png?alt=media\&token=47215c6e-8e96-4103-a69e-fb4acb5fc5b2)

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6z3t9aGJkAJgsZJo47%2F-M6z6ilzeYqHRxTsb1pv%2Fimage.png?alt=media\&token=73b1699e-32ba-47c8-a0b2-beb1b435a704)

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

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

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6z3t9aGJkAJgsZJo47%2F-M6z8H9Soex-mOsyjxBp%2Fimage.png?alt=media\&token=c13211fe-c272-4573-be2d-ed6602bea11c)

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

#### GraphRNN : Two levels of RNN

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6z3t9aGJkAJgsZJo47%2F-M6z9q0u-o6SBMRsTfBc%2Fimage.png?alt=media\&token=e803bbe8-0268-47d9-9b79-aa9b95cc0597)

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6z3t9aGJkAJgsZJo47%2F-M6zDH3k7A4S9H2hnTjm%2Fimage.png?alt=media\&token=929a2332-373d-4af6-86fd-64facbc642e8)

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M6zNwNvJZR4vGRvkrfn%2F-M6zPoRNVlObS6-tABuO%2Fimage.png?alt=media\&token=6368e8b1-de42-4600-ac69-a90e0ccc2978)

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M73OAqbx8S2cbqndOZc%2F-M73PCiPK1QggUhKbex7%2Fimage.png?alt=media\&token=be8c534a-b75f-4594-9399-054ac73828e1)

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

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M73OAqbx8S2cbqndOZc%2F-M73PsmGQdX0UFJePgdV%2Fimage.png?alt=media\&token=be15a89f-bb4d-40f9-a0c4-57fcd615050f)

* pdf ㄱ

#### Issue : Tractability

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M73TniKflWR5G6xyFxK%2F-M73TqAsDz4NVBYNoNDz%2Fimage.png?alt=media\&token=b6269bc7-c0e6-4ddd-9aaa-0d361cda1c6b)

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

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M775bpvVAmodESBCUvw%2F-M779oS851u8_FRdderL%2Fimage.png?alt=media\&token=5b2aebf5-f5ec-4672-bf96-4108d9c33495)

#### Evaluating Graphs

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

* Visual similarity
* Graph statistics similarity

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M775bpvVAmodESBCUvw%2F-M77AKfhyLfXWyGa4ehD%2Fimage.png?alt=media\&token=87be4b96-5f57-4f42-a233-b2b9bc74cb85)

#### Applications and Open Questions

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M77B8DdKevUrjd_Chup%2F-M77CuTHZzneivC9EHN4%2Fimage.png?alt=media\&token=598879e8-0c14-4ba3-987b-7381ab723cf4)

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

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

#### Graph Convoliutional Policy Network

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

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M77B8DdKevUrjd_Chup%2F-M77Ba2J-k5naFnt23lP%2Fimage.png?alt=media\&token=95cd29ca-20b2-4bfd-ba93-769065626b1e)

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M77B8DdKevUrjd_Chup%2F-M77C0Z7bfraztEh9A74%2Fimage.png?alt=media\&token=1b488660-9145-4f06-b83b-163eb88c6963)

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M77B8DdKevUrjd_Chup%2F-M77Br1BGKy9qKOtErJ6%2Fimage.png?alt=media\&token=39199988-7425-49b6-a778-aaf5057a5e25)

#### Open Problems 

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