[Graph 스터디] DAGNN(Directed Acyclic Graph Neural Networks)

작성자 : 채윤병

1. Introduction

 기존의 GNN은 이웃한 노드사이의 반복적인 message passing을 통해서 node의 representation을 update하고 graph representation을 만드는 pooling 방식을 사용했다.

 Neighborhood aggregation 방식은 GNN을 더 발전하게 했고 MPNN(Message passing neural network)으로 형식화하였다. 

 

MPNN architecture

MPNN 특징

1. L번째 representation을 나타내기 표현하기 위해 (L-1)번째 representation을 사용함. 
2. Aggregate, Combine, Readout은 각각 parameterized neural network

DAG(Directed Acyclic Graph)에서는 edge가 node사이의 partial ordering을 결정한다는 특징을 가지고 있으며 이러한 partial order는 neural network에 강력한 inductive bias를 제공할 수 있음!

※ 논문의 key point - DAG의 속성인 node의 partial ordering을 어떻게 network architecture에 활용할 것인가?

 

DAGNN(Directed Acyclic Graph Neural Network)은 이러한 partial order를 사용해 DAG의 representation을 만들어내는 GNN architecture이다.

P(v) - Set of direct predecessor of v, T - Set of nodes without successors(≒leaf node)

G, F, R은 각각 Aggregate, Combine, Readout과 비슷한 역할을 하는 parameterized neural networks

 

MPNN과 DAGNN의 차이

	MPNN	DAGNN
Aggregate	이전 layer의 neighborhood information만을 이용해 현재 layer의 representation을 만든다. Aggregation 범위 : 이웃 노드	Aggregation 과정에서 현재 layer의 information도 이용한다. 따라서 MPNN 보다 recent information을 사용한다고 할 수 있다. Aggregation 범위 : Direct predecessors
Pooling의 범위	V(Set of node of Graph G)	T(Set of node without successors)

이러한 차이를 통해 DAGNN은 graph의 더 적절한 vectorial representation을 얻을 수 있다.

 

DAGNN의 기술적인 details

1. Attention for node aggregation
2. Multiple layers for expressivity
3. Topological batching

2. DAGNN model

 

 

S(Sources) - Set of all nodes without (direct) predecessors

T(Targets) - Set of all nodes without (direct) successors

 

2.1 Model

DAGNN의 main idea - DAG에 의해 정의된 partial order를 다루는 것

노랑 - past representation of node v, 하늘 - representation of direct predecessors, 연두 - updated representation of node v

Aggregate operator G - Attention mechanism

a_uv - u가 v에 미치는 중요도를 softmax로 normalize한 것

Combine operator F - GRU

MPNN은 combine operator에 summation이나 concatenation을 사용했고, GG-NN의 경우 GRU를 사용했으나 GG-NN에서는 message를 input으로 사용하고 node의 representation을 state로 사용한 것에 차이가 있다.

**GRU에서는 state가 update 되는 개념

 

Readout operator R

 Readout operator는 주로 graph representation을 만들기 위해서 사용된다. Readout의 common practice로는 representation을 layer에 따라 concatenate하고 이를 node에 따라 max-pooling을 적용한뒤, FC layer를 사용하는 방법이 있다.

 Common practice와 DAGNN의 차이는 pooling의 범위를 제한(Target node에 제한)한 것과 bidirectional한 성질이 더해진 것이다.

 

2.2 Topological batching

 연산의 효율을 위해서 dependency가 없는 노드들은 같은 그룹으로 묶이고 동일하게 처리된다.(predecessor가 처리되었을 경우)

Topological batching의 규칙

1. Bi(i번째 batch)들은 서로 disjoint하다.
2. Bi에 속해있는 노드 u,v는 서로 연결되어 있지 않아야한다.
3. 모든 i에 대해서(i>0), B(i-1)을 head로 하는 tail이 Bi에 있어야한다.

★ 본문에서의 3번째 규칙에서 "one"이 하나만 존재해야한다는 것인지 잘 모르겠다.

 

 Topological batching은 각 배치안에 있는 모든 노드들이 병렬적으로 처리되도록 하는 sequential batch의 최소 개수를 제공한다. 규칙 1~3을 만족하는 partitioning은 DAG의 longest path의 길이와 같기 때문이다.

 

Remark

1.  3가지의 규칙을 만족하려면 B_0 = S일 필요가 없고 마지막 배치 또한 T와 같을 필요가 없다.
2.  Multiple graph에도 straightforward하게 적용할 수 있다. (다른 graph에도 같은 i로 하나의 Bi로 묶어서 처리할 수 있다.)

 

2.3 Properties

Invariance to node permutation, Different graph → Different representation

3. Results

본 논문에서는 4.Evaluation

Prediction performance

TOK - F1, LP - accuracy

TOK - 함수 이름을 생성하는 토큰을 예측하는 task

LP - DAG의 longest path를 예측하는 task

각각 15%에 해당하는 training set으로도 실험 진행

 

Ablation study

 DAGNN의 여러 methodology를 변화해가면서 Ablation study를 진행

Gated-sum aggr. - Aggregator의 attention방식을 Gated sum으로 대체한 경우 

Single layer - Multiple layer를 single layer로 대체한 경우

FC layer - Combine에서의 GRU를 FC layer로 대체한 경우

Pool all nodes - Readout에서의 pooling을 Target node가 아닌 모든 노드에 대해 진행한 경우

W/o edge attr. - Edge 정보 없이 진행한 경우

 

Ablation study 결과 요약

1. Attention방식을 대체했을 때의 성능 감소가 가장 컸다.
2. Dataset마다 가장 좋은 결과를 냈던 방법론이 달랐다.

 

Sensitivity analysis

Layer의 개수가 2~3개일 때의 결과가 가장 좋았다.

Single layer에서 2 layer로 갈때의 성능 향상이 가장 컸으며, Single layer에서 randomization으로 인한 variance가 가장 컸다.

Additionial ablation study

Bidirectional을 도입한 것의 효과가 좋지 않았다.

 

---

※ 읽어봐야할 논문 - D-VAE