Introduction to Graph Neural Networks [그래프 신경망 입문]

저자: 즈위안 리우, 지에 저우 지음
출판사: 에이콘

http://www.acornpub.co.kr/book/graph-neural-networks#toc

GNN에 관련된 첫 책이라 이해가 잘 되지는 않았다.
관련 논문을 찾아보고 여러 번 봐야 하는 책이라고 생각한다.
🔎 2022.08.28 Chapter 12까지 - 목차 및 용어 기록
🔎 2022.09.01 완독. 논문은 어떻게 정리할까?

1장. 서론

1.1 GNN이 탄생한 동기

1) 합성곱 신경망(CNN)

📌 GNN으로 사용할 수 있는 CNN 기술
1. 지역 연결: 그래프는 일반적으로 가까운 것들이 연결되어 있는 구조
2. 가중치 공유
3. 다중 계층 사용: 다양한 크기의 특징을 갖는 패턴을 다루는 핵심 기술

2) 네트워크 임베딩(graph embedding)
ex. DeepWalk, node2vec, LINE, TADW
3) 관련 연구

2장. 수학 및 그래프 기초

2.1 선형대수학

1) 기본 개념

• scalar: 수
• vector: 순서가 있는 수의 나열
  - norm: 백터의 길이를 측정한 값
  

N1 norm	N2 norm
L1 Norm은 맨허튼 노름(Manhattan norm)이라고도 한다. 벡터의 요소에 대한 절댓값의 합	n차원 좌표 평면(유클리드 공간)에서의 벡터의 크기를 계산하기 때문에 유클리드 노름(Euclidean norm)이라고도 한다. 피타고라스 정리를 활용한 것
활용: L1 Regularization, Computer Vision	활용: L2 Regularization, KNN 알고리즘, kmean 알고리즘

(출처: https://hwanii-with.tistory.com/58)

• metrix(행렬): 이차원 배열
• tensor: 임의의 차원을 같는 행렬

2) 고유분해
3) 특잇값 분해(singular value)

2.2 확률

1) 기본 개념과 공식
2) 확률분포

• 가우시안 분포(정규 분포)
• 베르누이 분포
• 이항 분포
• 라플라스 분포

2.3 그래프 이론

1) 기본 개념

$G=(V,E)$

유향 그래프(directed graph): 그래프에 속한 모든 엣지의 방향이 있는 경우
무향 그래프(undirected graph): 없는 경우

2) 그래프의 대수적 표현

• 인접 행렬
• 차수 행렬
• 라플라시안 행렬
• 대칭 정규화 라플라시안
• 랜덤 워크 정규화 라플라시안
• 근접 행렬

3장. 신경망 기초

3.1 뉴런

신경망의 기본 단위

• 활성화 함수:

시그모이드	하이퍼볼릭 탄젠트	ReLu

(출처: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=handuelly&logNo=221824080339)

3.2 역전파

• back propagation algorithm: 모델의 파라미터를 최적화 하기 위한 경사하강 기반 알고리즘
• 과정 반복
  • 정방향 개선(foward calculation): 주어진 파라미터와 입력값에 대한 신경망은 정방향으로 각 뉴런에서의 값을 개산한다.
  • 역전파(backward propagation): 최적화될 각 변수의 에러값을 계산하고 편도함수를 통해 파라미터를 업데이트한다.

3.3 신경망

• 순방향 신경망(FNN, Feedforward Neural Network): 입력층, 몇 개의 은닉 층, 출력 층으로 이뤄져 있음.
• 합성곱 신경망(CNN, Convolutional Neural Network): FNN의 특별한 버전, 근처의 연결성을 보존한다. 주로, 합성곱 층, 풀링 층, 몇 개의 완전연결 층으로 이뤄져 있음.
• 순환 신경망(RNN, Recurrent Neural Network): 시계열 데이터 처리하하는 데 효과적. 주로 음성 데이터나 자연어 데이터를 다룰 때 사용.
• 그래프 신경망(GNN, Graph Neural Network): 소셜 네트워크, 분자 구조, 지식 그래프 등 그래프 구조로 된 데이터를 다룰 때 주로 사용

4장. 기본 그래프 신경망

(scarselli et al. 2009)

4.1 서론

4.2 모델

4.3 한계

5장. 그래프 합성곱 네트워크

차근차근 찾아보기

5.1 스펙트럼 방법

1) 스펙트럼 네트워크
2) ChebNet
3) GCN
4) AGCN(Adaptive Graph Convolution Network)

5.2 공간 방법

1) 뉴럴 FPS
2) PATCHY-SAN: 각 노드에서 k개의 이웃을 고르고 정규화

• 노드 선택
• 그래프 정규화
• 합성곱 구조

3) DCNN(Diffusion-Convolutional Neural Network)
4) DGCN(Dual Graph Convolutional Network)
5) LGCN(Learnable Graph Convolutional Network)
6) MoNet
7) GraphSAGE

6장. 그래프 순환 네트워크(GRN, Graph Recurrent Neural Network)

6.1 게이트 그래프 신경망

6.2 Tree-LSTM

6.3 그래프 LSTM

6.4 S-LSTM

7장. 그래프 어텐션 네트워크

GCN류 방법이라고 볼 수 있음

7.1 GAT(Graph Attention Network)

7.2 GaAN(Gated Attention Network)

8장. 그래프 잔차 네트워크

컴퓨터 비전

8.1 하이웨이 GCN(highway network)

8.2 지식 점프 네트워크(jump knowledge network)

8.3 DeepGCNs

9장. 다양한 그래프 종류

9.1 유향 그래프

• 무향 그래프보다 유향 그래프가 더 많은 정보를 표현할 수 있다.

9.2 이종 그래프(heterogeneous graph)

9.3 에지 정보가 있는 그래프

1) 이분 그래프(bipartite graph)
2) 전파 단계에서 다른 종류의 에지에 다른 가중치 행렬을 적용

9.4 동적 그래프

교통 예측, 인간 행동 인식, 기후 예측 등에 적용

9.5 다차원 그래프

10장. 고급 학습 방법

학습과 최적화 면에서 단점이 있어 이를 해결하기 위한 몇 가지 변형 소개

10.1 샘플링

GraphSAGE: GCN은 전체 그래프 라플라시안이 필요한데, 그래프가 크면 계산 비용이 많이 든다. 또한 새로운 데이터를 처리하는 능력이 떨어진다. 이를 개선하는 것이 GraphSAGE이다.
PinSage: GraphSAGE의 확장

10.2 계층적 풀링

10.3 데이터 증강

10.4 비지도 학습

최근 오토 인코더(AE, auto-encoder)를 그래프에 적용하는 방법

11장. 일반적인 프레임워크

11.1 메시지 전달 신경망

11.2 비지역 신경망

DNN(Deep Neural Network)를 사용해 장거리 의존성을 포착하기 위한 비지역 신경망(NLNN, Non-Local Neural Network) 제안

11.3 그래프 네트워크

12장. 응용: 구조 시나리오

12.1 물리

12.2 화학과 생물

1) 분자 핑거프린트
2) 화학 반응 예측
3) 약물 추천
4) 단백질과 분자 상호작용 예측

12.3 지식 그래프

지식 정보를 노드가 개체(entity)이고, 에지가 관계(relation)인 유향 그래프로 표현된 것. 관계는 head, relation, tail 세 쌍으로 구성. 추천, 웹 검색, 질문 답변 등에 사용된다.

1) 지식 그래프 채우기
2) 귀납 지식 그래프 임베딩
3) 지식 그래프 정렬

12.4 추천 시스템

1) 행렬 채우기
sRMGCNN(seperable Recurrent Multi-Graph CNN) = 멀티 그래프 CNN과 RNN을 결합한 모델.
2) 소셜 추천

13장. 응용: 비구조 시나리오

13.1 이미지
1) 이미지 분류
2) 시각적 추론
3) 의미 구분

13.2 문자
1) 문자 분류
2) 시퀀스 레이블링
3) 신경 기계 번역
4) 관계 추출
5) 사건 추출: 글에서 나오는 특정 종류의 사건을 인식
6) 사실 확인(FV, Fact Verification): 문서에서 관련된 증거를 찾고, 그 증거로 주어진 주장을 확인. '뒷받침', '반박', '불충분' 판별
7) 그 밖의 응용

14장. 응용: 기타 시나리오

14.1 생성 모델
14.2 조합적 최적화

15장. 오픈소스

15.1 데이터셋
15.2 구현


저자 github : https://github.com/thunlp/gnnpapers