0 min read
Graph Embedding 은 node, edge, subgraph, 전체 graph 를 vector 로 표현하는 방법이다.
기존 그래프 알고리즘과의 비교 전통적인 그래프 관련 알고리즘들의 limitation 이 존재 기존 알고리즘들: BFS, DFS, Dijkstra algorithm, Prim algorithm etc.
핵심 요약 Graphical Model (확률 그래프 모델): 확률 분포를 그래프 구조로 표현하는 방법. 노드는 랜덤 변수, 엣지는 변수 간 의존 관계를 나타낸다.
graph/Graph Neural Network PBG 가 학습하는 모델들 RESCAL DistMult TransE ComplEx References Links paper: arxiv.org/pdf/1903.12287.pdf github: github.com/facebookresearch/PyTorch-BigGraph .
Random walk는 graph 위에서 현재 node의 이웃 중 하나를 확률적으로 선택해 이동하는 과정이다. graph의 node를 state로 보고, edge를 이동 경로로 보면 Markov Chain의 한 형태로 이해할 수 있다.
graph/Graph Neural Network에서 자주 발생하는 문제 중 하나로, 네트워크의 layer 수가 깊어질수록 각 정점의 임베딩이 점차 비슷해지는 현상을 말한다.
Related Link 정의 dynamic graphs represented as sequences of timed events 를 학습하기 위한 general encoder 구조 소개 real-world 그래프들은 dynamic 하고 시간에 따라 진화한다.
adjacency matrix 는 정방 행렬로, 유한한 그래프를 표현하기 위한 행렬이다. 이 행렬의 원소는 두 vertices 가 그래프 상에서 서로 인접 (adjacent) 한지 여부를 나타낸다.
Depth-First Search. 그래프나 트리에서 한 갈래를 끝까지 따라 내려간 뒤, 더 갈 곳이 없으면 한 칸 되돌아와 아직 안 가본 갈래로 다시 내려가는 탐색 방식이다. “깊이 우선” 이라는 이름은 이웃을 폭넓게 훑기 전에 한 방향으로 먼저 파고든다는 뜻이다.
Personalized PageRank Personalized PageRank(PPR)는 PageRank에서 “다시 시작할 위치”를 특정 seed node 또는 seed set에 집중시키는 방법이다.