퀠로맨 블로그

이 챕터에서는 GNN이 그래프 안의 노드들을 얼마나 잘 구별하여 노드 임베딩을 만들어줄 수 있는지 이론적으로 알아보는 시간이다.

이 챕터를 다 배우게 되면 어떤 GNN 구조가 가장 expressive power가 좋은지 알게 될 것이다.

GNN은 어떻게 노드를 구별할까?

node들에 따로 id 같은 feature가 없다고 할 때 graph structure만 가지고 노드들을 얼마나 잘 구별할 수 있을까?

위와 같은 구조를 보면 1,2,3,4,5는 노드 피쳐가 없다. 즉, 구별할 수 없는 노드이기 때문에 노드가 그래프 내에 어디에 달려있는지 그 위치 만으로 구별해야 한다.

직관적으로 봤을 때, 1번 노드와 2번 노드는 같게 취급이 될 것이라는 걸 알 수 있다.

노드가 구별하기 위해서는 각 노드별로 만들어지는 computational graph의 구조가 달라야 한다.
1번, 2번 노드의 computational graph를 아래와 같이 그렸을 때 둘의 구조가 정확히 일치하는 것을 알 수 있다.

(노드 번호가 다른 것은 ID가 노드 피쳐로 들어가지 않았으므로 실제로는 구별할 수 없다.)

아래와 같이 모든 노드들에 대해 computational graph(rooted subgraph structure)를 그려봤을 때 서로 다른 computational graph를 가진 노드들만이 서로 다른 임베딩을 갖게 된다.

결국 GNN의 역할은 computational graph를 임베딩으로 매핑하게 되는데,

다른 computational graph는 다른 embedding이 나오기 위해서는 매핑이 "injective" 해야 한다.

그리고 매핑이 injective하기 위해서는 computational graph의 내부 과정인 neighbor aggregation 또한 injective 해야 한다.

GNN이 expressive하지 못할 때

위에서 GNN이 expressive하기 위해서는 neighbor aggregation이 injective해야 한다고 했다.

그렇다면 과연 어떤 neighbor aggregation이 좋을까?

(우리가 하는 neightbor aggregation의 대상은 multi-set이라고 할 수 있다. 여기서 multi-set은 같은 item이 반복될 수 있는 set을 말한다)

Mean pooling failure case (GCN)

Max pooling failure case (GraphSAGE)

The most expressive GNN - Graph Isomorphism Network (GIN)

GIN을 설명하기에 앞서 다음과 같은 두 개념을 알아두자.

Injective multi-set function

Universal Approximation Theorem

1개의 hidden layer를 가진 MLP가 충분히 크면 어떤 continuous function이던 임의의 정확도로 근사할 수 있다.

위 두개의 theorem에 따라 Injective한 aggregation function을 만들면 다음과 같다.

즉, injective한 동시에 MLP 파트들을 잘 학습시켜서 뒤이어 나오는 downstream task 또한 잘 수행될 수 있도록 학습시킬 수 있다.

GIN과 WL Graph Kernel의 유사성

우리는 챕터2에서 그래프를 구별할 수 있는 WL Graph Kernel에 대해 배웠다.

WL Graph Kernel도 주변 노드에서 정보를 합친 뒤 (sum) Hash를 통해 새로운 ID로 매핑한다.

이는 GIN이 하는 일과 굉장히 유사한데 K-step의 GIN operation을 반복하면 K-hop neighborhood 구조를 summarize하는 것과 같은 효과이다.

Pooling의 expressive power 순위

1. Sum (GIN) - multiset 구별 가능

2. Mean (GCN) - distribution 구별 가능

3. Max (GraphSAGE) - set 구별 가능

Level 별 prediction task 방법

Question: GNN을 통해 Node Embedding을 얻고 나서 실제 Task는 어떻게 수행할 것인가?

--> 각 레벨 별로 어떤 식으로 task를 수행할 수 있는지 알아보자.

(아래에서는 prediction head를 가지고 어떻게 활용할 수 있는지 알아보는 것이라 할 수 있다.)

Level	방법
Node-level	- 노드 임베딩에 웨이트를 곱해서 바로 prediction!
Edge-level	- 두 노드 임베딩을 concat한 뒤 MLP 적용! - 두 노드 임베딩을 dot-product  1- way: 바로 product k-way: 가운데 여러개의 Weight를 시도한 뒤 Concat해서 만든다.
Graph-level	노드 임베딩을 aggregation처럼 모아주는 operator를 활용해서 예측에 사용한다. NOTE: 위의 global pooling method들 같은 경우 서로 다른 노드 임베딩이 같은 결과를 나타낼 때도 있기 때문에 다른 방법이 필요하다. 아래 예제에서도 sum pooling을 하게 되면 node feature들의 절대값들이 달라도 결과가 같아지게 되는 문제가 생긴다.

DiffPool (Hierarchical Pooling)

위의 그림처럼 원본 그래프를 점점 더 작은 그래프로 바꾼 다음 graph embedding을 구하게 된다.

각 단계별로

1. 노드 임베딩을 구하고

2. 주어진 노드 임베딩을 가지고 클러스터링을 한뒤

3. 클러스터링 별로 pooling을 적용하여 다음 스테이지를 위한 single node를 만든다.

Supervised Vs Unsupervised Tasks

그래프를 가지고 할 수 있는 task 중에 supervised와 unsupervised가 있다.

아래 표를 보면 알겠지만 unsupervised 같은 경우는 그래프의 구조 자체를 활용한다.

Loss function for supervised learning

- Classification task: Cross entropy loss를 활용한다. (아래 cross entropy는 K개의 data가 있을 때를 의미한다.)

- Regression task: L2 error (Mean Square error)를 활용한다.)

Evaluation Metric

- Classification task

Multi-class classification의 경우

 --> accuracy를 측정 전체 중 정확하게 예측한 것은 몇개인가?

Binary classification의 경우

--> Confusion matrix를 활용

Accuracy: 전체 중 맞춘 것은 무엇인가? (TP + TN) / (TP + TF + FP + FN)

Precision: True라고 예측한 것 중에 진짜 True의 비율(얼마나 오진을 했냐) (TP) / (TP + FP)

Recall: 모든 True들 중 True라고 예측한 것의 비율(얼마나 진짜 True를 빼먹지 않았냐) (TP) / (TP + FN)

어떤걸 예측한다고 했을 때, False의 비율이 굉장히 낫다고 하자.

그러면 무지성으로 True로 예측하면 왠만하면 Accuracy, Precision, Recall이 모두 높게 나올 것이다.

그래서 다음과 같은 개념이 등장한다.

ROC (Receiver operating characteristic) curve and AUC (Area under Curve)

Binary classification에서 threshold를 바꾸면 TPR과 FPR이 바뀌게 된다.

우리의 목표는 FPR이 0이 되고, TPR이 1이 되게 만드는 것이다. (최대한 왼쪽 위)

threshold가 1이면 아무것도 positive가 안될 것이므로 TP=0, FP=0이어서 (FPR,TPR)=(0,0)에 있을 것이고

threshold가 0이면 모든 것이 positive가 될 것이므로 (FPR,TPR)~(1,1)에 있을 것이다.

우리는 최대한 curve 자체도 왼쪽 위로 넓어지기를 원하고 (AUC)

그 중 가장 왼쪽 위에 있는 point를 통해 threshold를 고를 것이다.

- Regression:

Root Mean Square Error(RMSE)

 Mean Absolute Error(MAE)

Split data (train, validation, test set)

일단 random하게 split하고 여러번의 학습 결과를 평균을 내야 한다.

그렇다면 어떻게 random하게 split해야 할까?

Link Prediction example

Link prediction에서는 edge를 감춰서 학습에 쓰일 edge는 message passing edge, 실제 존재하는지 맞춰야하는 edge를 supervision edge로 나눈다.

Inductive setting에서는 단순히 그래프를 나눠서 하면 되지만 아래와 같은 Transductive setting은 약간 tricky하다.

(1) Transductive setting에서는 그래프를 세 개로 세트로 나눈 뒤 그 안에서 message passing edge, supervision edge로 나눈다.

(2) Training 단계에서는 Training message passing edge와 Training supervision edge로 학습한다.

(3) Validation 단계에서는 Training message passing edge + training supervision edge로 validation supervision edge를 예측한다.

(4) Test 단계에서는 Training message passing edge + training supervision edge + Validation supervision edge로 test supervision edge를 예측한다.

참고: 원래 Transductive setting이라면 모든 단계에서 전체 graph structure를 이용해야 하기 때문에 모든 edge를 이용해야 하지만 edge 자체가 각 단계에서 prediction의 대상이 되기 때문에 점진적으로 더 넣어주게 되는 것이다.

* feature augmentation

(사실 이 부분은 정작 중요한 부분이 아닌데 8단원 강의의 첫부분에 나온게 이상하긴 하다)

때로는 feature가 부족하거나 아무것도 없을 때는 임의로 feature를 넣기도 한다.

Feature augmentation 방법	Constant 1을 집어넣기	Node ID를 One-hot으로 집어넣기
특징	- expressive power는 낮다. (graph의 구조에 대해서만 배운다.) - computation cost가 적다. - 그래프가 더 커져도 적용이 가능하다. (단순히 1만 추가하면 되므로)	- expressive power는 높다 (각각의 node에 대해서 배울 수 있다.) - Computation cost가 크다. (one-hot vector 크기가 크므로) - 새로운 노드에는 적용이 불가능하다. (one-hot vector의 크기가 정해져 있으므로 노드가 늘어나면 새로 vector 크기를 정의해야 한다.
설명

때로는 computation graph로는 배울 수 없는 feature들도 있다.

--> 예: 특정 길이의 cycle의 수

이러한 구조적인 정보는 넣어주면 더 좋다. (degree, clustering coefficient, pagerank, centraility)

* Structure augmentation

Too Sparse할 경우	Too Dense할 경우
- biparate graph에서는 edge를 augment해서 한 논문을 같이 쓴 저자들을 묶어줄 수 있다. - 또는 모든 노드를 잇는 임의의 노드를 만들어서 아주 먼 노드를 이어줄 수 있다.	- Neightbor Node를 샘플링 해야 한다. --> computation cost와 missing node로부터의 important message 간의 trade-off

7.1. General GNN Framework

GNN에서 신경써야 할 것들은 다음과 같다.

1. Message: Node embedding에서 Message를 어떻게 만들 것인가

2. Aggregration: neighbor들의 Node embedding을 어떻게 모을 것인가

3. Layer connectivity: 1, 2를 가지고 만든 single layer들을 어떻게 연결할 것인가(예: skip connection을 쓸 것인가?)

4. Graph manipulation: node를 augmentation할 것인가?

5. Training objectives: supervised learning Vs. Unsupervised Learning, Node, Edge, Graph level...

7.2 Single Layer of GNN

GNN에서 하나의 layer는 다음과 같은 기능을 수행한다.

(1) Message transformation: 이전 node embedding을 변환하는 단계

(2) Message aggregation: neighbor들의 node embedding을 모으는 단계

(3) Activation: aggregation 이후에 nonlinearity를 추가하여 expressiveness를 늘린다.

여러가지 GNN을 Message + Aggregation 틀에 맞추어 설명해보자.

Graph Convolution Network (GCN)

node embedding에 linear transformation을 취하고, average를 취한다.

원래의 식은 위와 같으나 Message + Aggregation으로 나누어 표현하여 보자.

GraphSAGE

GCN과 GraphSAGE의 가장 큰 차이점은 GCN은 Node 자체의 embedding은 사용하지 않으나 GraphSAGE는 Node 자체의 embedding을 따로 transformation하고, Concat해서 사용한다는 점이다.

전체 식은 위와 같고, aggregation function은 다양하게 정할 수 있다. (Average, Pooling (Mean, Max), 심지어 LSTM으로 할 수도 있다.)

Message + Aggregation 형식으로 표현하면 다음과 같다.

(옵션) embedding의 크기를 맞춰주기 위해 l2 Normalization을 하면 성능이 좋아지기도 한다.

Graph Attention Network (GAT)

Graph Attention Network는 GraphSAGE보다는 GCN에 가깝다고 볼 수 있다.

GCN은 Average를 사용하므로 Sum을 할 때 각 Neighbor들의 중요도(weight)는 똑같이 1/degree라고 할 수 있다.

GAT에서는 각 node들의 중요도(weight)를 attention mechanism을 이용해 구한다.(Attention Weight)

Attention Mechanism은 자유롭게 정할 수 있는데 보통 두 노드의 임베딩을 Linear + Non-linear layer를 통해서 만들어낸다.

그런 뒤에 weight들의 크기를 맞춰주기 위해 softmax를 취한다.

Attention Mechanism과 Graph Neural Network는 동시에 학습된다.

하나의 attention mechanism이 잘 통하지 않는 경우도 있으니 여러개의 attention mechanism을 동시에 사용하고 aggregation하기도 한다.

다음과 같은 장점들이 있다고 한다.(아직 와닿지 않는다.)

- Computationally efficient

- Storage efficient

- Localized

- Inductive capability

Modern Deep learning Techniques

이 외에도 딥러닝에 쓰이는 테크닉들을 쓸 수 있다.

- Batch Norm: 노드들의 크기를 Normalize한다. (여기서 말하는 Batch는 무엇일까?)

- Dropout: Message Transformation의 Linear layer에 적용 가능

- Activation: 다양한 activation function 사용 가능

7.3 Stacking Layers of a GNN

이전 시간에 GNN layer 하나를 어떻게 구성하는지 배웠으니 이러한 layer들을 연결하는 법을 알아보자.

CNN과는 다르게 GNN에서는 layer의 개수가 반드시 더 많은 expressiveness를 의미하지 않는다.

다만, information을 얼마나 많은 hop에서 얻느냐를 말한다.

# of GNN layers = # of hops != expressiveness

over-smoothing problem

GNN layer를 너무 많이 사용하면 node embedding이 전부 비슷해지는 현상이 생기는데 이를 over-smoothing problem이라고 부른다.

이는 hop이 커지면 reception field가 커져서 결국에는 비슷한 노드를 사용하기 때문에 만들어지는 일이다.

아래 그림을 보면 3-hop만 지나도 그래프의 대부분의 node를 커버하게 된다.

따라서 다른 Deep learning과는 달리 GNN은 Layer를 늘리는 것이 반드시 좋은 것(expressiveness를 늘리는 것)은 아니다.

GNN Layer를 적게 쓰면서 expressiveness를 늘리는 방법은 다음과 같다.

(1) GNN layer 내의 linear layer를 늘리기 (예: message transformation에 쓰이는 MLP layer)

(2) GNN layer 들을 쓰기 전이나 후에 쓰는 MLP layer를 늘이기

혹은 GNN layer들에 skip connection을 사용하면 된다.

Skip connection은 node 자체의 정보를 보존하는데 큰 도움을 주기 때문에 receptive field가 커져도 node embedding이 비슷해지지 않도록 해준다. (Shallow network와 Deep network를 같이 쓰는 효과)

Skip connection은 activation function 전에 node embedding 자체를 더해줘서 만들 수 있다.

들어가면서

다양한 자료 구조 (특히 회로)들은 그래프로 표현하는 것이 직관적으로 더 좋고 성능도 더 잘 나온 것으로 알려져서 스탠포드에서 graph representation leraning 강의가 올라와 있어서 이를 공부하며서 정리하고자 한다.

https://web.stanford.edu/class/cs224w/index.html

왜 그래프를 사용해야 하는가?

기존의 Machine learning 및 Deep learning의 경우 grid(image), sequence(text나 audio) 형태의 input만 주로 활용했지만 세상에는 grid, sequence로 표현되지 않는 것도 많다.

그래프는 relation, interaction을 표현하기 좋은 수단으로 더 나은 prediction 결과를 낼 수 있다.

그래프 표현의 예

그래프를 활용한 Neural Network의 모습

그래프를 가지고 할 수 있는 task들

• Node classification: 특정 노드가 어떤 특징(feature)를 가지고 있는지 예측 (online user/item categorization)
• Link prediction: 두 노드간 link가 있을 것인지 없을 건인지 관계를 에측 (Knowledge graph completion, recommendation system, drug side effect prediction)
• graph classification: 그래프가 어떤 property를 가질 것인지 구분 (molecule/drug property prediction)
• clustering: 특정 sub-graph를 찾아낸다. (social circle prediction, traffic prediction)
• graph generation: 특정 조건을 만족하도록 새로운 그래프를 생성 (Drug discovery)
• graph evolution: 그래프가 어떻게 변화해 갈 것인지 예측 (physical simulation)

그래프의 구성 요소

Node, Edge, Graph

그래프를 표현하는 방법들

(1) Adjacency matrix

각 노드에 index를 부여하고 index의 개수만큼 row와 column을 가지는 매트릭스를 만든다.

- undirected graph일 경우 adjacency matrix는 symmetric하다.

- 만약 edge에 가중치를 준다면 1이 아닌 다른 숫자를 넣으면 된다.

성질

1. row (혹은  column) 값을 다 더하면 해당 노드의 degree가 된다.

$$ k_i = \sum_{j}^{N}A_{ij} $$

보통 node의 개수에 비해 edge의 개수가 훨씬 적으므로 "sparse matrix"가 된다 => memory, computation에서 손해

(2) Edge list

(따로 떨어져 있는 노드 없이 노드들이 모두 연결되어 있다는 가정 하에) edge들의 list만으로 그래프를 표현할 수 있다.

ex: [(1,2), (2,3), (1,3), (3,4)]

(3) Adjacency list

각 노드들의 neighbor들을 표기해준다.

1: 2,3

2: 1,3

3:, 1,2,4

4: 3

다양한 그래프들

• Directed Vs. Undirected: edge에 방향성이 있나 없나
• Heterogenous graph G = (V, E, R, T)
• Bipartite graph: 노드가 두 그룹 (U, V)로 나뉘어져 edge가 같은 그룹내에서는 없고, 서로 다른 두 그룹 사이에만 존재 (user와 iterm, actors & movies
• weighted vs unweighted
• self-edge를 허용할 것인가? multiple edge를 허용할 것인가?