[GNN] 그래프 신경망 입문 pt.1

Chap 4. 기본 그래프 신경망

4.1 서론

그래프에서 노드 $v$는 feature에 대한 노드로 정의됨.

GNN의 목표는 각 노드의 상태 임베딩(State embedding) ${\bf h}_v \in \R^s$ 학습

state embedding ${\bf h}_v$는 해당 노드, 주변 노드의 정보 포함하며, $v$의 출력값 ${\bf o}_v$ 얻을 때 활용

기본 그래프는 무향 동종 그래프, 각 노드는 input feature ${\bf x}_v$를 가지며, edge 또한 feature 가질 수 있음.

$co[v], ne[v]$ 는 각각 노드 $v$와 연결된 edge 집합, 인접한 노드 집합을 의미.

4.2 모델

이웃으로부터 노드 상태를 업데이트 하는 두 가지 종류의 함수:

지역 전환 함수(local transition function) $f$, 지역 출력 함수(local output function) $g$

\[\begin{align} {\bf h}_v = f({\bf h_v}, {\bf x}_{co[v]}, {\bf h}_{ne[v]}, {\bf x}_{ne[v]}) \end{align}\] \[\begin{align} {\bf o}_v = g({\bf h}_v, {\bf x}_v) \end{align}\]

업데이트는 자기 자신의 state + 주변 node, edge의 정보를 통해,

output은 자기 자신의 state embedding, input feature만으로 정의됨.

행렬 연산으로의 정의

행렬로 ${\bf H, O, X, X_N}$을 각각 전체에 대한 state embedding, output embedding, input feature, node input feature라고 하면,

\[\begin{align} {\bf H} = F({\bf H}, {\bf X}) \end{align}\] \[\begin{align} {\bf O} = G({\bf H}, {\bf X_N}) \end{align}\]

식 (3)에서 $\bf H$ 는 고정점이며, 고정점 정리에 의해

\[\begin{align} {\bf H}^{t+1} = F({\bf H}^t, {\bf x}) \end{align}\]

노드의 target information(output과 디멘션이 같음) ${\bf t}_v$가 주어졌을 때 Loss function은

\[\begin{align} \text{Loss function} = \sum_{v\in P}({\bf t}_v - {\bf o}_v) \end{align}\]

여기서 $\bf P$는 ${\bf t}_v$가 정의된 노드 집합

학습은 gradient descent로 이루어지며,

1. state embedding ${\bf h}_v^t$가 반복적으로 시간 $T$까지 업데이트 되며 고정점 근사값 $H$를 얻게 됨
2. Weights $w$의 gradient는 loss function으로부터 획득
3. $w$의 마지막 단계에서 계산된 gradient를 이용해 가중치 업데이트

4.3 한계

• 고정점을 얻기 위해 노드의 은닉상태를 반복적으로 업데이트 하는 것은 비효율적
• 기본 GNN은 업데이트시 동일한 파라미터를 사용하나, 다른 신경망들은 각 층마다 다른 파라미터를 사용함. (계층적 feature 추출의 가능성)
• edge의 학습 상태에 대한 모델링이 불가능.
• T가 아주 클 경우 고정점의 분포가 비슷한 값을 가지게 되어 각 노드의 정보가 구별되지 않음.