25.GNN과 GNN심화

강의 복습 내용

• GNN이란?
  • 귀납식 정점 표현
  • 그래프 신경망 (Graph Neural Network)
  • 그래프 합성곱 신경망 (Graph Convolutional Network)
  • GraphSAGE
• GNN(심화)
  • attention
  • 그래프 임베딩
  • 그래프 풀링
  • over-smoothing
  • data-augmentation

얻은 지식

---

GNN

• 귀납식 정점 표현방식

정점표현방식

• 그래프의 정점들을 벡터의 형태로 표현하는것
• 변환식(transductive)방법
  • 학습의 결과로 정점의 임베딩 자체를 얻는다.
• 귀납식(Inductive)방법
  • 정점을 임베딩으로 변화시키는 함수
  • 
    • 빨간 박스가 귀납식의 결과
    • 파란 박스가 변환식의 결과

변환식의 한계

• 출력으로 임베딩 자체를 얻는 변환식 임베딩의 한계
• 1) 학습이 진행된 이후에 추가된 정점에 대해서는 임베딩 얻을 수 없다
  • 다시 계산을 해야한다.
• 2) 모든 정점에 대한 임베딩을 미리 계산해야한다.
  • 모든 벡터를 저장
• 3) 정점이 속성 정보를 가진 경우활용이 불가
  • 임베딩에서는 그런 정보가 표현못한다고한다.

귀납식 임베딩

• 1) 새로운 정점에도 임베딩 얻을 수 있다.
• 2) 모든정점에 대한 임베딩을 저장하지 않아도 된다
  • 필요할때 함수를 사용
• 3) 속성정보를 가진경우 활용할 수 있다.
• 이런 방식의 대표가 GNN(그래프 신경망)이다.

---

그래프 신경망

• 그래프와 정점의 속성 정보를 입력
• 정점u의 속성벡터 X_u
  • m차원의 벡터이며, m은 속성의 갯수이다.
  • sns에서는 성별, 지역, 연령등이 속성의 예
• 이웃 정점들의 정보를 집계하는 과정을 반복하여 임베딩을 얻는다.
  • 
    • 대상 정점을 기준으로 이웃의 정보를 집계
• 집계 단계를 층(layer)라하고, 층마다 임베딩을 얻는다.
  • 
    • a를 기준으로 점차 확장되는 형태.
    • 층수가 단순히 과정이 아닌, 단계로 중첩된다고 생각해야한다.
    • 2층은 두번 중첩된것, 1층은 1번 중첩이라 생각하면 이해가 쉽다.
    • 
      • 이런 느낌
• 계산 그래프(coumputation graph)
  • 대장 정점마다 집계되는 정보가 상이하다.
  • 
    • 입력 그래프
  • 
    • 대상 정점마다 다른 그래프가 만들어진다.
• 서로다른 대상 정점간 층 별 집계 함수는 공유한다.
  • 
  • 같은 층의 함수는 같은 가중치를 갖는다는 의미
  • 딥러닝의 레이어라고 생각하면된다.
  • 입력의 크기가 달라도 처리가 가능해야한다.
  • 가변적인 입력을 처리하기위한 어떤형태의 짐계함수를 가져야할까
• 집계함수
  • 두가지 기능을 가진다.
  • 
    • 1) 이웃들의 정보의 평균 계산
    • 2) 신경망에 적용
  • 
    • \(h_v^k\)는 k번층의 정점v의 임베딩
    • 초기에는 입력속성정보(x_v)를 가짐
    • k층으로 중첩되면서 반복 계산
    • 출력임베딩(\(z_v\))는 마지막층의 임베딩 \(h_v^K\)가 된다.

신경망의 학습

• 학습변수(trainable parameter)는 층 별 신경망의 가중치
• 
  • W와 B가 가중치
• 손실함수
  • 정점간 거리를 보존하는것
    • 
• 후속과제(downstream task)의 손실함수를 이용한 종단종학습(end-to-end)
  • 정점 분류가 최종
  • 임베딩의 결과가 분류기를 통과하였을때 정확도를 높이는게 최종목표이다.
  • 분류기의 정확도를 높이기 위한 분류기의 손실함수
    • cross entropy를 사용
  • 
  • GNN end-to-end형태
    • 
• GNN vs 변환적 정점 임베딩
  • 분류하는것에 있어 end-to-end로 구현한 GNN과 변환적 임베딩 이후 따로 분류기를 학습한것을 비교
  • 
• 학습시에는 일부의 정점만 선택하여 진행한다.
  • 모든 정점을 사용하지 않는다.
• backpropagation
  • 손실함수를 최소화 하는 과정
  • 신경망의 학습 변수들(W,B)을 학습

활용

• 학습에 사용되지 않은 정점에 대해 정점 임베딩 얻을 수 있다.
• 학습이후 추가된 정점의 임베딩 얻을 수 있다.
• 새로운 그래프에 적용 할 수 있다.

---

그래프 신경망의 변형

• 그래프 합성곱 신경망(GCN)
• GraphSAGE

Graph Convolutional Network(GCN)의 집계함수

• 
  • 기존(그래프 신경망)은 이전층에서 v에 대한 정점임베딩을 별도의 B를 사용
    • B역시 함께 평균하는것으로 변경됨
  • 기존과 다른 정규화 방식 사용

GraphSAGE의 집계함수

• 이웃들을 AGG함수를 이용해 합치기
• 자신의 임베딩과 연결(concatenation)한다.
• 
• AGG함수
  • mean(평균)
  • pool(최대값)
  • LSTM

---

합성곱 신경망(CNN)과 비교

• 그래프 신경망과 같이 이웃의 정보를 집계하는 과정을 반복한다.
• 차이점
  • CNN은 이웃이 균일하지만, 그래프 신경망은 균일하지 않는다.
  • 그래프는 다양한 입력을 처리하도록 해야한다.

    차이

  • 그래프 인접 행렬에 CNN적용은?
    • CNN을 적용하면 안된다.
    • CNN은 인접픽셀이 유용한 정보를 가진다.
    • 하지만 인접행렬은 제한된 정보를 가진다.
      • 인접행렬은 행과 열의 순서도 임의로 정해진다.

---

GNN망(심화)

그래프 신경망이란?

• 귀납식 정점 표현 학습의 한가지
  • 정점을 임베딩하는 함수(인코더)를 학습
• 이웃 정점들의 정보를 집계하는 과정을 반복
  • 집계함수의 형태에 따라 그래프 신경망, 그래프 합성곱 신경망, graphSAGE로 구분됨
• 비지도, 지도학습 모두 가능
  • 비지도 학습은 정점간 거리를 보존
  • 지도학습은 후속 과제(downstream task)의 손실함수를 이용해 종단종학습 수행
• 활용
  • 학습하지 않은 정점도 정점 임베딩을 얻을수 있다.
  • 새로운 그래프에서도 정점 임베딩을 얻을 수 있다.

그래프 신경망의 어텐션은?

• 기존방식들
  • 기본 그래프 신경망
    • 이웃들의 정보를 동일한 가중치로 평균
  • 그래프 합성곱 신경망
    • 단순히 연결성을 고려한 가중치로 평균
• 이웃간의 강한연결과 약한 연결이 표현이 없었다.

그래프 어텐션 신경망(Graph Attention Network GAT)

• 
  • 이웃간의 가중치를 다르게 적용
• 가중치 자체도 학습
  • 이를 위해 self-attention을 사용
• \[a_{ij}\]
  • 각 층에서 정점 i부터 j로의 가중치
• 가중치a 계산
  • \[\hat{h_i} = h_iW\]
    • 정점 i의 임베딩 h_i에 신경망 W를 곱해 새로운 임베딩 \(\hat{h_i}\) 얻기
  • \[e_{ij} = a^T[CONCAT(\hat{h_i},\hat{h_j})]\]
    • 정점 i와 정점 j의 새로운 임베딩을 연결한 후, 어텐션 계수 a를 내적
  • \[a_{ij} = softmax_j(e_{ij})\]
    • 위 결과를 softmax적용
  • 학습은 a와 W 벡터를 역전파를 통해 학습이 된다.
• 여러개의 어텐션을 동시에 학습
  • 
    • 3개의 어텐션이 적용된 그림
  • MHA(멀티 헤드 어텐션)을 사용한다.

어텐션의 정확성

• 
  • 어텐션 적용후 성능이 오른것을 볼 수 있다.

---

그래프 표현학습(그래프 임베딩)

• 정점표현학습
  • 그래프의 정점 -> 벡터
• 그래프 표현학습(그래프 임베딩)
  • 그래프 전체 -> 벡터
  • 벡터의 형태로 표현된 그래프 자체를 의미
• 사용하는법
  • 그래프 분류에 활용
  • 예) 그래프로 표현된 화학분자구조로 특성을 예측하기

그래프 풀링(Graph pooling)

• 정점임베딩으로 그래프 임베딩 얻기
• 평균같은 단순한 방법보다 그래프의 구조를 고려한 방법을 사용하여 성능을 높인다.
• 미분 가능한 풀링(Differentiable Pooling, DiffPool)
  • 
  • 군집구조를 활용하여 임베딩을 계층적으로 집계

지나친 획일화 문제(Over-smoothing)

• 그래프 신경망의 층의 수가 증가하면서 정점의 임베딩이 서로 유사해지는 현상
  • 작은 세상 효과와 관련이있다.
• 
  • 5단계의 층을 넘어가도, 정점들이 비슷한 위치로 모여든다.
  • 왜냐면 이웃을 확인하는데 자기자신도 포함되면서 점차 전역을 바라보게 된다.
• over-smoothing의 결과
  • 
  • 그래프 신경망의 층이 증가하니, downstream-task(후속과제)의 정확도가 감소
  • 잔차항(Residual)을 넣기도한다.
    • 이전층의 임베딩을 한번더 더해주는것
    • 큰 효과가 없다

대응

• JK네트워크(Jumping Knowledge Network)
  • 
  • 마지막 층의 임베딩 뿐만 아니라, 모든 층 임베딩을 사용
• APPNP
  • 
  • 0번째 층을 제외하고 신경망 없이 집계함수를 단순화
  • W를 0번째에만 넣었다.
  • 층의 수증가에 따른 정확도 감소효과가 없다.

---

그래프 데이터 증강(Data Augmentation)

• 데이터증강(Data Augmentation)
  • 다양한 기계학습에서 효과적
    • 일부 데이터를 변형해서 학습하는것
  • 그래프의 누락되거나 부정확한 간선을 보완하기위해 사용
  • 임의 보행으로 정점간 유사도를 계산
    • 유사도가 높은 정점간의 간선을 추가하는 방법이 제안
  • 
    • 정점간 유사도를 계산하여 간선을 추가하는 과정
• 정점 분류의 정확도가 개선됨
  • 
  • HEAT,PPR은 증강기법

---

실습

GraphSAGE이용하기

• from dgl.nn.pytorch.conv import SAGEConv

  GraphSAGE구현

• SAGEConv 클래스 구현

---

전체 복습!

그래프란?

• 복잡계를 효과적으로 표현하고 분석하기 위한 언어

  실제 그래프는?

• 랜덤 그래프와 구분되는 실제 그래프의 구조적 특성
• 작은세상효과
• 군집계수

  검색엔진의 그래프

• Pagerank
• 스파이더트램
• dead-end
• 순간이동

  바이럴 마케팅

• 전파
• 의사결정기반모형
  • 선형임계치 모형
• 확률기반모형
  • 독립전파
• 시드집합
  • 전파되는 기준
• 전파최대화문제
  • 시드찾기

    그래프 구조 분석

• 군집을 찾는방법
• Girvan Newman
  • 하향식
• Louvin
  • 상향식
• 군집성
• 중첩군집
  • 완화된 중첩 군집 모형

    추천시스템

• 내용기반 추천시스템
  • 상품
• 협업필터링 추천시스템
  • 유사한사람

    그래프 정점을 벡터로

• 변환식 정점 임베딩
  • 그래프의 유사한것을 임베딩공간에서도 유사하게
• DeepWalk,Node2Vec

  추천시스템 (심화)

• 넷플릭스 챌린지
• 잠재인수모형
  • 시간
  • 사용자편향
  • 상품편향

    그래프 신경망

• 신경망의 구조, 학습,활용
• 정점임베딩
  • 귀납식 정점 임베딩
  • 정점을 벡터로 변환하는 함수를 출력

    그래프 신경망(심화)

• attention
• data augmentation
• over smoothing

---

좀더 찾아보기

• 집계함수

---

피어세션 정리

• h_v^k-1의 의미는?
  • 층을 밑에서 올라가는게 아닌 a부터 시작해서 감싸는 느낌으로 생각하자.
  • 실제 코드를 보고 해보자
    • num layer가 이웃 층
    • hidden layer
• 층은 실제 레이어
• 같은 층이 공유한나든게?

조교님

• 질문받기
• 모두의 딥러닝, coursera 엔드류강의 들음
  • 면접관련으로 핵심적인게 많음

마스터님

• 그래프 연습
  • kaggle연습
  • OGB(open graph banchmark)
• 추천이 고립을 강화
  • 데이터는 회사의 재산이라서 공개가 안됨
  • bias같은것으로 추천을 약화시키는 방식으로 진행한다고 함
• 그래프 자체를 공부하는것도 좋다.
  • networks, crowds, and markets
  • linked(링크)
• 역량
  • 그냥 조합과 툴을 쓰기보다는,
  • 머신러닝 지식, 구현하는것, 자료구조, 알고리즘, 프로그래밍 경험