그래프 신경망 - 기본

ganta·2021년 2월 26일
Graph
0

Graph 이론

목록 보기
8/9
post-thumbnail

그래프 신경망 기본

  • 그래프 신경망의 특징
    ✔️ 변환식(Transdctive) 방법(학습의 결과로 정점의 임베딩 자체를 얻음)이 아닌 정점을 임베딩으로 변화시키는 함수, 즉 인코더를 얻는 귀납식(Inductive)방법이다.

    ✔️ 그래프의 신경망은 그래프와 정점의 속성 정보를 입력으로 받음

    ✔️그래프의 인접 행렬을 AA(∣V∣|V| X ∣V∣|V|의 이진행렬), 각 정점 uu의 속성(Attribute)벡터를 XuX_u(mm차원 벡터이고, mm은 속성의 수를 의미)라고 가정
    이때, 정점의 속성은 다음과 같다.
    👉 SNS에서 사용자의 지역, 성별, 연령, 프로필 사진 등
    👉논문 인용 그래프에서 눈문에 사용된 키워드에 대한 원-핫 벡터
    👉 PageRank등의 정점 중심성, 군집 계수(Clustering coefficent)

    ✔️ 그래프 신경망은 이웃 정점들의 정보를 집계하는 과정을 반복하여 임베딩을 얻는다.

    출처
    Naver BoostCamp AI Tech - edwith 강의
    http://snap.stanford.edu/proj/embeddings-www/


    위의 에시에서 대상 정점의 임베딩을 얻기 위해 이웃과 이웃의 이웃들의 정보를 집계한다.


    출처
    Naver BoostCamp AI Tech - edwith 강의
    http://snap.stanford.edu/proj/embeddings-www/


    각 층에서 이웃들의 이전 층 임베딩을 집계하여 새로운 임베딩을 얻고 0번 층(입력 층)의 임베딩으로는 정점의 속성 벡터를 사용

    출처
    Naver BoostCamp AI Tech - edwith 강의
    http://snap.stanford.edu/proj/embeddings-www/



    출처
    Naver BoostCamp AI Tech - edwith 강의
    http://snap.stanford.edu/proj/embeddings-www/


    대상 정점마다 집계되는 정보가 상이하고 대상 정점 별 집계되는 구조를 계산 그래프(Computation Graph)라고 한다.

    ⭐️ 이때, 서로 다른 정점간에도 층 별 집계 함수는 공유한다.
    (이때, 집계함수란 이전층에서 다음층으로 갈 때의 변환을 해 주는 함수이다.)

    출처
    Naver BoostCamp AI Tech - edwith 강의
    http://snap.stanford.edu/proj/embeddings-www/

  • 집계함수
    ✔️ 집계함수의 단계
    1️⃣ 이웃들 정보의 평균을 계산
    2️⃣ 신경망에 적용
    ➡️ hv0=xv  h_v^0= x_v\;(0번 층에서 정점 vv의 임베딩(입력 속성 정보)으로 정점 vv의 속성 벡터로 초기화)
    ➡️ hvk=σ(Wk∑u∈N(u)huk−1∣N(u)∣+Bkhvk−1),∀k>0h_v^k = \sigma(W_k\sum_{u \in N(u)}\frac{h_u^{k-1}}{|N(u)|} + B_kh_v^{k-1}), \forall k > 0
    (hvkh_v^k : 현재 층, 즉 kk번 층에서 정점 vv의 임베딩, σ\sigma : 활성함수, huk−1∣N(u)∣\frac{h_u^{k-1}}{|N(u)|} : 이전 층에서 이웃들의 임베딩에 대한 평균을 계산, hvk−1h_v^{k-1} : 이전 층에서 정점 vv의 임베딩)
    (이때, WkW_k, BkB_k는 학습 변수(Trainable Parameter)로써 층 별 신경망의 가중치이다.)
    ➡️ zv=huKz_v = h_u^K (마지막 층에서 정점 vv의 임베딩(출력 임베딩))

    ✔️ 손실함수
    1️⃣ 정점간 거리를 보존하는 것을 목표로 할 수 있다.
    만약, 인접성을 기반으로 유사도를 정의하면 손실함수는 다음과 같다.
    ➡️ L=∑(u,v)∈V×V∣∣zu⊤zv−Au,v∣∣2L = \sum_{(u,v) \in V\times V}||z_u^{\top}z_v - A_{u,v}||^2
    해당 내용 링크 : https://velog.io/@ganta/%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%98-%EC%A0%95%EC%A0%90-%EB%B2%A1%ED%84%B0%ED%99%94
    2️⃣ 후속 과제(Downstream Task)의 손실함수를 이용한 종단종(End-to-End)학습도 가능
    예시)
    👉 정점 분류가 최종 최종 목표인 경우(그래프 신경망을 이용하여 정점의 임베딩을 얻음 - 이를 분류기(Classifier)의 입력으로 사용 - 각 정점의 유형을 분류)를 가정
    👉 분류기의 손실함수, 예를 들어 교차 엔트로피(Cross Entropy)를 전체 프로세스의 손실함수를 사용하여 종단종(End-to-End)학습을 할 수 있다.(손실함수를 어떻게 사용하느냐에 따라 다양한 Task를 수행 할 수 있다.)
    ➡️ L=∑v∈Vyvlog(σ(zv⊤θ))+(1−yv)log(1−σ(zv⊤θ))L = \sum_{v \in V}y_vlog(\sigma(z_v^{\top}\theta)) + (1-y_v)log(1-\sigma(z_v^{\top}\theta))(yvy_v : 정점의 실제 유형(0 혹은 1), zvTz_v^T : 정점의 임베딩, θ\theta : 분류기의 학습 변수)

    출처
    Naver BoostCamp AI Tech - edwith 강의


    ✔️ 집계 함수의 역전파
    👉 학습 데이터를 구성할 시 선택한 대상 정점들에 대한 계산 그래프를 구성한다.

    출처
    Naver BoostCamp AI Tech - edwith 강의


    👉 오차역전파(Backpropagation)을 통해 손실함수를 최소화 한다.

    출처
    Naver BoostCamp AI Tech - edwith 강의


    ✔️ 학습된 신경망을 적용하여 학습에 사용되지 않은 정점, 학습 이후에 추가된 정점의 임베딩 또한 얻을 수 있다.=> 반면, 변환식(Transdctive) 방법은 새로 추가된 정점에 대하여는 임베딩 결과를 얻을 수 없다.

    출처
    Naver BoostCamp AI Tech - edwith 강의



    출처
    Naver BoostCamp AI Tech - edwith 강의
    http://snap.stanford.edu/proj/embeddings-www/


    실생활에 많이 존재하는 그래프에서는 정점이 새로 추가되는 사례가 대부분이기 때문에(예 - SNS) 이러한 특징은 매우 유용하게 사용된다.

    ✔️ 학습된 그래프 신경망을 새로운 그래프에 적용 또한 가능하다.
    예를 들어, A종의 단백질 상호 작용 그래프에서 학습한 그래프 신경망을 B종의 단백질 상호작용 그래프에 적용 가능(입력 속성 정보를 넣어주면 되기 때문)

    출처
    Naver BoostCamp AI Tech - edwith 강의
    http://snap.stanford.edu/proj/embeddings-www/

  • 그래프 신경망의 성능
    ✔️ 그래프 신경망의 종단종(End-to-End)학습을 통한 분류는 변환적 정점 임베딩 이후에 별도의 분류기를 학습하는 것보다 정확도가 대체로 높다.

    출처
    Naver BoostCamp AI Tech - edwith 강의

그래프 신경망 변형

  • 일반적인 그래프 신경망 외의 다양한 형태의 집계함수 또한 존재할 수 있다.
    ✔️ 그래프 합성곱 신경망(Graph Convolutional Network, GCN)의 집계 함수
    ➡️ hv0=xvh_v^0 = x_v
    ➡️ hvk=σ(Wk∑u∈N(v)∪vhuk−1∣N(u)∣∣N(v)∣)  ,∀k∈{1,...,K}h_v^k = \sigma(W_k\sum_{u \in N(v) \cup v}\frac{h_u^{k-1}}{\sqrt{|N(u)||N(v)|}})\;, \forall k\in \left \{ 1,...,K \right \}
    ➡️ zv=hvKz_v = h_v^K
    ❗️ 기존의 집계 함수와 비교해 보면 (hvk=σ(Wk∑u∈N(u)huk−1∣N(u)∣+Bkhvk−1)h_v^k = \sigma(W_k\sum_{u \in N(u)}\frac{h_u^{k-1}}{|N(u)|} + B_kh_v^{k-1})) 다음과 같은 차이가 있다.
    1️⃣ 동일 신경망 사용으로 학습 변수 공유
    2️⃣ 정규화 방법 변화(∣N(u)∣∣N(v)∣\sqrt{|N(u)||N(v)|}) => 기하평균의 사용
    ⭐️ 작은 차이지만 큰 성능의 향상이 이뤄졌다.

    ✔️ GraphSAGE의 집계 함수
    ➡️ hvk=σ([Wk⋅AGG({huk−1,∀u∈N(v)}),Bkhvk−1])h_v^k = \sigma([W_k \cdot AGG(\left \{ h_u^{k-1}, \forall u\in N(v) \right \}), B_kh_v^{k-1}])
    이웃들의 임베딩을 AGG 함수를 이용해 합친 후, 자신의 임베딩과 연결(Concatenation)하게 된다.(AGG({huk−1,∀u∈N(v)})AGG(\left \{ h_u^{k-1}, \forall u\in N(v) \right \}) 와 Bkhvk−1B_kh_v^{k-1}을 연결)
    이때, AGG함수로는 평균, 풀링, LSTM등이 사용될 수 있다.
    👉 Mean : AGG = ∑u∈N(v)huk−1∣N(v)∣\sum_{u \in N(v)}\frac{h_u^{k-1}}{|N(v)|}
    👉 Pool : AGG = γ=({Qhuk−1,∀u∈N(v)})\gamma = (\left \{ Qh_u^{k-1}, \forall u \in N(v) \right \}) (이때, γ\gamma는 원소별 최대를 뽑는 것을 뜻한다.)
    👉 LSTM : AGG = LSTM([huk−1,∀u∈π(N(v))])([h_u^{k-1}, \forall u \in \pi(N(v))])

합성곱 신경망과의 비교

✔️ 합성곱 신경망과 그래프 신경망은 모두 이웃의 정보를 집계하는 과정을 반복한다.
이때, 합성곱 신경망은 이웃 픽셀의 정보를 집걔하는 과정을 반복한다.

출처
Naver BoostCamp AI Tech - edwith 강의
http://snap.stanford.edu/proj/embeddings-www/


이때, 합성곱 신경망에서는 이웃의 수가 균일하나 그래프 신경망에서는 아니다.(즉, 그래프 신경망에서는 정점별로 집계하는 이웃의 수가 다르다.)

출처
Naver BoostCamp AI Tech - edwith 강의
http://snap.stanford.edu/proj/embeddings-www/


⭐️ 그래프에서는 합성곱 신경망이 아닌 그래츠 신경망을 적용해야 한다!
(많은 경우에서 실수를 하는 부분)
👉 합성곱 신경망이 주로 쓰이는 이미지에서는 인접 픽셀이 유용한 정보를 담고 있을 가능성이 높으나 그래프의 인접 행렬에서의 인접 원소는 제한된 정보를 가지고 있는 경우가 많다. 특히, 인접 행렬의 행과 열의 순서는 임의로 결정되는 경우가 많음(좀 더 많은 원소들(영역)을 고려 해 주워야 한다.)

Reference

Naver BoostCamp AI Tech - edwith 강의

profile
ganta
한걸음씩 꾸준히
이전 포스트

추천시스템 - 심화

다음 포스트

그래프 신경망 - 심화

0개의 댓글