1. Graph란

참고자료 : Graph Representation Learning, William L. Hamilton (McGill University) (2020)

Graph는 복잡한 시스템을 나타내는 Data structure이다. 가장 일반적으로 생각하면, graph는 node들의 집합이고,
이 node들의 pair 사이 interaction들의 집합으로 이루어져 있다. 예를 들면, graph로 social network를 encoding한다면,
각각 node는 개인을 나타내고 개인 사이의 관계를 edge로 나타낼 수 있다. Graph의 장점은 각각 node들의 특성보다는
node들 사이의 관계에 좀 더 초점을 맞췄다는 것이다.

Graph의 Definition

graph의 formal description은 다음과 같다.
graph $\mathcal{G=(V,E)}$은 node들의 set인 $\mathcal{V}$과 edge들의 set인 $\mathcal{E}$로 이루어져 있다는 의미이다. Edge는 $(u,v)\in \mathcal{E}$ 로 표기한다.
보통 simple graph은 node pair 사이에 대부분 한개의 edge가 존재하고, self-loop(자신과 연결된 edge)는 존재하지 않고, edge들이 undirect(방향성이 없음)함을 의미한다. graph를 가장 간편한 방법은 Adjacency matrix를 활용하는 것으로, (node 개수) * (node 개수) 사이즈의 matrix를 의미한다. Adjacency matrix의 요소는 1 또는 0으로 채워지는데, 두 노드 사이의 edge가 존재할 때 $A[u,v]=1$, 존재하지 않을 때 $A[u,v]=0$ 값을 가지게 된다.

만약 그래프에 undirected edge들만 존재한다면, Adjacency matrix는 symmetric한 matrix가 된다.
하지만 만약 그래프에 방향성이 존재한다면, A는 꼭 symmetric할 필요는 없다. 또 다른 경우는 weighted edge를 가진 경우로, {0,1} 값이 아니라 real-value들로 채워진다. 예를 들면! PPI(Protein-Protein Interaction) graph의 weighted edge는 두 protein 사이의 association의 세기를 의미한다.

Multi-relational Graphs

서로 다른 type의 edge들로 이루어진 graph를 의미한다. edge type은 $(u,\tau,v)\in\mathcal{E}$로 구성되고,
각 edge type마다 adjacency matrix $A_\tau$를 가진다. multi-relational graph은 heterogeneous와 multiplex의 속성을 가진다.

Heterogeneous Graphs

여러 타입의 노드들이 존재하고 노드들의 set은 다음과 같이 나타낼 수 있다.

$\mathcal{V=V_1\cup V_2\cup V_3\cup...\cup V_k \ where V_i \cap V_j=\phi, \forall i \ne j }$

Edge들은 제약 조건을 가지는데, 특정 edge는 특정 type의 node들과 연결된다는 것이다. $(u,\tau_i,v)\in\mathcal{E}\rightarrow u\in\mathcal{V}_i, v\in\mathcal{V}_k$

Multiplex graphs

graph는 k개의 layer들의 집합으로 분해할 수 있다. 모든 노드는 모든 layer에 속해있고, 각 layer는 하나의 relation으로 볼 수 있다. 이는 intra-layer edge type을 의미한다. 같은 노드가 연결된 것은 intra-layer edge type이다. 예를 들면, multiplex transportation network가 있다. 각 노드는 도시를 의미하고, 각 layer는 transportation의 다른 종류(air travel, train travel)를 나타낸다. 여기서 Intra-layer edge들은 다른 종류의 transportation로 연결된 도시들을 나타내고, Inter-layer edge들은 특정한 도시의 transportation의 종류가 달라질 가능성을 나타낸다.

Feature Information

많은 경우, graph에는 graph에 연관된 attribute 또는 feature information이 존재한다. feature information에는 3가지 종류가 있는데,

1. Node-level attribute
2. Edge attribute
3. real-valued features with entire graph

가 있다.