Recommender systems, social network,academic graph, knowledge graph 등 다양한 분야에 large-scale의 그래프가 활용되고 있다.일반적으로 ML 모델은 미니배치를 활용한 SGD를 통해 학습을 한다.이웃노드들로부터

완벽한 GNN 모델이란 neighborhood structure와 node embedding 사이에 injective function을 가지는 것을 의미한다.즉 같은 구조라면 같은 노드 임베딩을, 다른 구조라면 다른 노드 임베딩을 가져야 한다.Problem 1: 같은

Graph generation에는 주어진 그래프와 유사하도록 만드는 task와 제약조건 하에서 최적화되는 그래프를 생성하는 task가 있다. 이번 lecture에서는 전자에 대해 다룬다.하지만 다음과 같은 이유로 그래프 생성은 어려움이 있다.$n$개의 노드를 위해 $n

$P(k)$로 나타내며 임의로 선택한 노드가 $k$의 degree를 가질 확률을 의미한다.$N_k$를 degree가 $k$인 노드의 수라 할 때 정규화된 히스토그램은 $P(k)=N_k/N$으로 나타낼 수 있다.$C$로 표기하며 노드 $i$가 이웃들과 어떻게 연결되어 있

1. Community Detection in Networks Granovetter's Answer Social network에서의 관계는 가까운 친구와 지인으로 나뉠 수 있다. 구직을 하는 과정에서 친한 친구보다는 지인으로부터 소개를 받는 경우가 많다. Granov

Subgrpah는 노드와 엣지 중 어느 것을 중심으로 subset을 구성하냐에 따라 node-induced subgraph와 edge-induced subgraph로 나뉜다.도메인에 따라 두 방식 중 하나가 선택되며 예를 들어 chemistry는 노드가 중요하므로 no

Lecture 11.1: https://www.youtube.com/watch?v=X9yl0pTP9fY&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=31Lecture 11.2: https://www.youtube.

Heterogeneous graph는 노드 $V$ 엣지 $E$, 노드의 종류 $T$, 관계성 종류 $R$로 구성된다.GCN은 이전 레이어에서의 이웃 노드와 자기 자신의 임베딩 벡터를 받아 선형변환을 하는 message transformation과 이를 summation

우리는 local network neigborhood에 기반하여 노드 임베딩을 생성하고자 한다.이를 위한 다양한 GNN 모델들이 나왔으며 GCN은 element-wise mean pooling+Linear+ReLU를 이용하고 GraphSAGE는 MLP+element-w

현재까지는 input 그래프가 계산 그래프와 동일하다는 가정이 있었으나 아래와 같은 이유로 부분 그래프를 계산 그래프로 쓸 필요가 있다.Input 그래프는 feature가 부족하여 augmentation 할 필요가 있다.그래프가 sparse 할 경우 가상의 노드나 엣지

하나의 GNN layer는 message와 aggregation으로 구성된다.GNN layer는 여러개 쌓을 수 있다.Raw input graph와 computational graph는 다르다. 즉, 여러개의 그래프가 활용될 수 있다.Supervised/ Unsuper

노드 임베딩이란 그래프 상에서 유사한 노드들이 함수 $f$를 거쳐 $d$차원으로 임베딩 되었을 때에 가까이 위치하도록 만드는 것이다.이 과정에서의 핵심은 low-dimension으로 맵핑을 해주는 인코더와 original network에서의 유사도와 embedding

1.Message Passing and Node Classification References Lecture 5.1: Lecture 5.2: Lecture 5.3:

웹은 각 웹페이지가 노드, 페이지 간의 하이퍼링크가 엣지인 그래프로 표현할 수 있으며 각 웹페이지는 서로 다른 중요도를 가진다.웹에는 방향성이 있어 해당 웹페이지로 연결되는 in-link와 다른 웹페이지로 연결되는 out-link가 있다.In-link가 많을수록 중요도

Encoder를 통해 노드를 low-dimension인 embedding space로 보냈을 때 그 공간에서 비슷한 곳에 위치하는 노드들이 graph 내에서도 유사성을 띄어야 한다.유사성은 두 노드가 연결되어있는가?, 이웃노드를 공유하는가?, 구조적으로 비슷한 역할을

Node의 위치 및 구조를 파악하기 위한 feature로는 Degree, Centrality, Clustering coefficient, Graphlets가 있다.$k_v$는 node $v$의 edge의 수를 의미한다.edge의 수 = 이웃 node의 수Node deg

Objects는 nodes(vertices)에 담기며 $N$으로 표기한다.Interactions는 edges(links)에 담기며 $E$로 표기한다.node와 edge로 이루어진 전체 system을 graph 혹은 network라고 하며 $G(N,E)$로 표기한다.양방