Graph Neural Network - newlife-js/Wiki GitHub Wiki

by 연세대학교 여진영 교수님

Classical ML tasks in Networks

Node Classification: node의 타입 예측
Link Prediction: 두 node가 연결되어있는지
Community Detection: node들의 cluster identification
Network Similarity: 두 network가 얼마나 비슷한지

Feature Learning

Goal: Efficient task-independent feature learning for ML in networks
Symbolic network를 공간 vector로 변환

Inputs

Homogeneous graph: node들이 같은 type의 object로 이루어진 경우
Heterogeneous graph: node들이 다른 type의 object로 이루어진 경우(예: actor-movie-director)
Graph with auxiliary information
Graph constructed from non-relational data

Embedding Nodes

Node를 공간 vector로 변환

Shallow Encoding

encoder is just an embedding-lookup
node에 embedding matrix Z를 곱하는 방식

Node Similarity

Adjacency-based similarity
node u와 v의 embedding의 내적으로 edge existence(adjacency matrix의 u,v element)를 근사

단점: O(V^2) runtime, direct/local connection만 고려
Multi-hop similarity

기본적으로 S_u,v를 Adjacency matrix의 k곱(A^k_u,v)으로 씀
Jaccard similarity(k-hop 내에서 u,v가 공유하는 node의 수)를 사용하기도 함
Random-walk Embeddings
참고
node u에서 v로 가는 random walk(node sequence)의 확률을 추정하고, random walk statistics를 encoding하는 embedding을 optimize함
node u, v가 전체 random walk(모든 node에 대한 random walk)에서 u와 v가 같이 등장하는 확률이 높다면, 두 node는 가까움
장점: local/high-order neighborhood information을 통합(expressivity), random walk에 함께 나타나는 pair에 대해서만 고려하면 됨(efficiency)

Deepwalk

참고
Random walk를 word2vec의 문장이라고 생각을 하고, input이 one-hot node vector, output이 인접한 node vector로 해서 hidden layer를 embedding으로 사용하는 방법(shallow encoding)

Metapath2vec

참고
Heterogeneous network의 node embedding방법
미리 정의된 meta-path(APA, APVPA 등)로만 transition하는 random walk를 구성하고,
skip-gram 알고리즘으로 hidden layer를 학습

※ metapath2vec++: node type별로 multinomial distribution(output)을 구성

GCN(Graph Convolutional Network)

참고
※ Neighbor aggregation: 주변 neighbor들로부터 NN을 사용하여 정보를 aggregation
Neighbors로부터의 message를 average하여 NN 적용

GCN: neighbor embeddings과 self-embedding을 통일된 수식으로 합침