Graph in DGL

Graph

그래프는 노드(V)과 엣지(E)의 관계를 표현하기 위한 자료 구조

Node는 $V$ 집합으로 정의 되고
Edge는 $E$ 집합으로 정의 될때

그래프를 정의하는 수식 (1)과 같다

$V = \{1, 2, 3, 4\}$ … (1)
$E = \{(1,2), (2,3), (3,4)\}$ … (2)
$G = \{V,E\}$ … (3)

이때 노드들간의 대칭적인 관계를 표현하는 것과 같이 방향성이 없거나
비대칭적인 관계를 표현하기 위해서 방향성을 가질 수 있다.

그래프는 엣지의 방향성에 따라서 방향성(directed) 또는 비방향성(undirected) 그래프로 정의된다.

또한 그래프는 가중치(unweight), 가중치를 가지 않는(unweighted) 상태가 있다.

unweight graph : 단순히 연결만을 가지는 그래프
unweighted grpah : 연결의 강도를 가지는 그래프

그래프는 동종(homogeneous), 이종(heterogeneous) 그래프의 특성을 가질 수 도 있다.

homogeneous grpah : Node와 Edge같은 종류의 관계를 나타내는 그래프
heterogeneous graph : Node와 Edge가 다른 종류의 관계를 나타내는 그래프

다중 그래프(MultiGraph)는 자체 루프를 포함한 노드들 사이 방향성이 있는 여러 에지들을 갖는 그래프

DGL Library

Graph 생성

dgl 라이브러리에서 graph 표현법

dgl에서 Edge를 다음과 같이 표현한다.
Edge의 방향성을 U에서 V로의 엣지를 식 (4)로 나타낸다.

$E = \{U, V\}$ … (4)
$U = \{U_1, U_2, U_3, \cdots\, U_n\}$ … (5)
$V = \{U_1, U_2, U_3, \cdots\, U_n\}$ … (6)

dgl에서 다음과 같은 그래프를 만들고 싶을 때 Node의 번호를 이용하여 코드를 작성하면 된다.

import dgl
import torch as th

u, v = th.tensor([0, 0, 0, 1]), th.tensor([1, 2, 3, 3])
g = dgl.graph((u, v))

print(g)를 이용하면 다음과 같이 출력이된다.

Graph(num_nodes=4, num_edges=4,
ndata_schemes={}
edata_schemes={})

Graph 객체에 nodes()함수를 이용하면 Node가 출력이 된다.

tensor([0, 1, 2, 3])

Graph 객체에 edges()함수를 이용하면 Edge가 출력이 된다.

(tensor([0, 0, 0, 1]), tensor([1, 2, 3, 3]))

edges()함수의 파라미터로 form='all'을 주면 다음과 같이 edge의 번호 또한 출력이 가능하다.

(tensor([0, 0, 0, 1]), tensor([1, 2, 3, 3]), tensor([0, 1, 2, 3]))

또는 다음 코드를 통해 가능하다.

import dgl
import torch as th

g = dgl.DGLGraph()
g.add_nodes(4)

u, v = th.tensor([0, 0, 0, 1]), th.tensor([1, 2, 3, 3])
g.add_edges(u, v)

Node, Edge Feature

Node와 Edge의 특징을 저장하기 위해서는 ndata와 edata 인터페이스를 통해 가능하다.

import dgl
import torch as th

g = dgl.graph(([0, 0, 1, 5], [1, 2, 2, 0])) # 6 nodes, 4 edges
g.ndata['x'] = th.ones(g.num_nodes(), 3)               # node feature of length 3
g.edata['x'] = th.ones(g.num_edges(), dtype=th.int32)  # scalar integer feature

g를 출력하면 다음과 같다.

Graph(num_nodes=6, num_edges=4,
ndata_schemes={'x': Scheme(shape=(3,), dtype=torch.float32)}
edata_schemes={'x': Scheme(shape=(), dtype=torch.int32)})

이때 g.ndata['x']를 출력하면 다음과 같다.
tensor([[1., 1., 1.],
[1., 1., 1.],
[1., 1., 1.],
[1., 1., 1.],
[1., 1., 1.],
[1., 1., 1.]])

이떄 g.edata['x']를 출력하면 다음과 같다.
tensor([1, 1, 1, 1], dtype=torch.int32)

각 ndata의 경우 각 행이 노드의 갯수와 같다는 것을 볼 수 있고
edata의 경우 각 index가 Edge의 index인 것을 볼 수 있다.