그래프 머신러닝: (5-3) GNN: 다양한 그래프

(GRL) GNN: Graphs

Hamilton,W.L. Graph Representation Learning. 2020

지금까지는 심플 그래프에서의 GNN을 가정했으나, 그래프가 다중관계이거나 hetrogenous(예: 지식 그래프)할 때를 다루지 못했다. 이러한 그래프를 다루는 몇 가지 전략을 알아보자.

Edge features and Multi-relational GNNs

Relational Graph Neural Networks

Relational GNN 중 Relational Graph Convolutional Network(RGCN)[Schlichtkrull et al., 2017] 방법이 대표적이다.

이 방법은 관계 유형별로 별도의 변환 행렬을 지정하여 여러 관계 유형을 수용하도록 집계(aggregation) 함수를 보강한다.

\[\mathbf{m}_{\mathcal{N}(u)} = \sum_{\tau \in \mathcal{R}} \sum_{v \in \mathcal{N}_{\tau}(u)} \frac{\mathbf{W}_{\tau} \mathbf{h}_v}{f_n(\mathcal{N}(u), \mathcal{N}(v))},\]

여기서, \(f_n\)은 노드 \(u\)의 이웃과 집계되는 이웃 \(v\)에 모두 의존하는 정규화 함수이다.

전반적으로 RGCN의 다중 관계형 집계는 정규화를 사용하는 기본 GNN 접근 방식과 유사하지만 서로 다른 엣지 유형에 따라 정보를 별도로 집계한다.

Parameter Sharing

Naive한 RGCN의 단점으로는 관계 유형당 trainable matrix가 있기 때문에 파라미터 수가 매우 크다는 것이다. Schlichtkrull et al.[2017]은 따라서 basis 행렬들을 이용한 parameter sharing을 제안하였다:

\[\mathbf{W}_{\tau} = \sum_{i=1}^{b} \alpha_{i,\tau} \mathbf{B}_i\]

이러한 방식에서 모든 관계 행렬은 basis 행렬 \(\mathbf{B}_1, \dots, \mathbf{B}_b\)의 선형 조합이 되고, 관계와 관련된 파라미터는 각 관계 \(\tau\)에 대한 \(b\)개의 조합 가중 \(\alpha_{1,\tau}, \dots, \alpha_{b,\tau}\)이다.

Basis sharing 방식에서 집계 함수를 다음과 같이 정의한다:

\[\mathbf{m}_{\mathcal{N}(u)} = \sum_{\tau \in \mathcal{R}} \sum_{v \in \mathcal{N}_{\tau}(u)} \frac{\alpha_{\tau} \times_1 \mathbf{B} \times_2 \mathbf{h}_v}{f_n(\mathcal{N}(u), \mathcal{N}(v))}\]

Attention and Feature Concatenation

관계별로 별도의 집계 파라미터를 정의하는 관계형 GNN 접근 방식은 다중 관계형 그래프 및 개별 edge feature가 있는 경우에 적용할 수 있다. 일반적인 형태의 edge feature가 있는 경우를 수용하기 위해 이러한 feature을 활용하거나 메시지 패싱 중에 이 정보를 인접 임베딩과 연결(concatenate)하여 활용할 수 있다.

예를 들어 기본 집계가 주어지면 edge feature를 leverage해 다음과 같은 새로운 집계 함수를 정의할 수 있다:

\[\mathbf{m}_{\mathcal{N}(u)} = \text{AGGREGATE}_{\text{base}}(\{\mathbf{h}_v \oplus \mathbf{e}_{(u,\tau,v)}, \forall v \in \mathcal{N}(u)\}) \]

\(\mathbf{e}_{(u,\tau,v)}\)는 엣지 \((u,\tau,v)\)에 대한 임의의 vector-valued feature이다.

Graph Pooling

신경망 메시지 전달로 그래프 수준에서 예측하는 방법을 알아보자.

노드 임베딩 집합 \(\{\mathbf{z}_1, \dots , \mathbf{z}_{|V|} \}\)를 전체 그래프를 나타내는 임베딩 \(\mathbf{z}_\mathcal{G}\)에 매핑하는 풀링 함수 \(f_p\)를 설계한다. 이웃 임베딩 세트를 학습하기 위해 논의된 모든 방법은 그래프 수준 풀링에 사용할 수 있다.

실제로 집합 풀링을 통해 그래프 수준 임베딩을 학습하는 데 가장 일반적으로 적용되는 두 가지 방법이 있다. 첫 번째는 단순히 노드 임베딩의 합계(또는 평균)를 취하는 것이다:

\[\mathbf{z}_G = \frac{\sum_{v \in \mathcal{V}} \mathbf{z}_c}{f_n(|\mathcal{V}|)} \]

두 번째는 LSTM과 attention을 조합하여 노드 임베딩을 풀링하는 방법이다. \(t=1,...,T\) 단계에 대해 반복되는 방정식의 집합으로 정의된 일련의 attention 기반 집계를 반복한다:

\[\begin{align*} \mathbf{q}_t &= \text{LSTM}(\mathbf{o}_{t-1}, \mathbf{q}_{t-1}), \\ e_{v,t} &= f_a(\mathbf{z}_v, \mathbf{q}_t), \quad \forall v \in \mathcal{V}, \\ a_{v,t} &= \frac{\exp(e_{v,i})}{\sum_{u \in \mathcal{V}} \exp(e_{u,t})}, \quad \forall v \in \mathcal{V}, \\ \mathbf{o}_t &= \sum_{v \in \mathcal{V}} a_{v,t} \mathbf{z}_v. \end{align*}\]

여기서, \(\mathbf{q}_t\)는 각 반복에서 attention에 대한 쿼리 벡터이다. 이 쿼리 벡터는 각 노드에 대해 attention score를 계산하기 위해 사용된다(\(f_a\)는 어텐션 함수).

정규화된 attention score \(a_{v,t}\)는 노드 임베딩에 대한 가중치 역할을 하여 가중합을 계산한다.

마지막으로 \(T\)번의 반복을 통해 전체 그래프에 대한 임베딩을 계산한다:

\[\mathbf{z}_G = \mathbf{o}_1 \oplus \mathbf{o}_2 \oplus \ldots \oplus \mathbf{o}_T\]

이 방법은 집합에 대한 어텐션 기반 풀링을 위한 정교한 아키텍처를 나타내며 많은 그래프 수준 분류 작업에서 널리 사용되는 풀링 방법이 되었다.

Graph Coarsening Approaches

집합 풀링 방법의 한계점은 그래프의 구조를 이용하지 않는다는 것이다. 이에 따라 노드 표현을 풀링하는 수단으로 그래프 clustering 혹은 coarsening을 수행한다.

\[f_c \rightarrow \mathcal{G} \times \mathbb{R}^{|\mathcal{V}| \times d} \rightarrow \mathbb{R}^{+|\mathcal{V}| \times c}\]

이 클러스터링 함수는 그래프의 모든 노드를 \(c\)개 클러스터에 할당한다.

이러한 매핑의 결과물을 \(\mathbf{S} = f_c(\mathcal{G},\mathbf{Z})\)라고 하고, 이를 사용해 그래프를 coarsen한다. 구체적으로는 인접행렬과 노드 피쳐 집합을 새로 만든다.

\[\mathbf{A}^{\text{new}} = \mathbf{S}^{\top} \mathbf{A} \mathbf{S} \in \mathbb{R}^{+c \times c}\]

\[\mathbf{X}^{\text{new}} = \mathbf{S}^{\top} \mathbf{X} \in \mathbb{R}^{c \times d}\]

이 coarsening 방식은 CNN에서 사용되는 풀링 접근 방식에서 영감을 받았으며 입력 그래프의 다양한 granularity에서 작동하는 hierarchical GNN을 구축할 수 있다는 직관에 의존한다. 실제로 이러한 방식은 강력한 성능으로 이어질 수 있지만 불안정하고 훈련하기 어려울 수도 있다.

Generalized Message Passing

GNN 메시지 패싱 방법을 일반화하여 메시지 패싱의 각 단계에서 엣지 및 그래프 수준 정보를 활용할 수도 있다.

\[\begin{align*} \mathbf{h}^{(k)}_{(u,v)} &= \text{UPDATE}_{\text{edge}} \left( \mathbf{h}^{(k-1)}_{(u,v)}, \mathbf{h}^{(k-1)}_u, \mathbf{h}^{(k-1)}_v, \mathbf{h}^{(k-1)}_\mathcal{G} \right) \\ \mathbf{m}_{\mathcal{N}(u)} &= \text{AGGREGATE}_{\text{node}} \left( \left\{ \mathbf{h}^{(k)}_{(u,v)} \forall v \in \mathcal{N}(u) \right\} \right) \\ \mathbf{h}^{(k)}_u &= \text{UPDATE}_{\text{node}} \left( \mathbf{h}^{(k-1)}_u, \mathbf{m}_{\mathcal{N}(u)}, \mathbf{h}^{(k-1)}_\mathcal{G} \right) \\ \mathbf{h}^{(k)}_\mathcal{G} &= \text{UPDATE}_{\text{graph}} \left( \mathbf{h}^{(k-1)}_\mathcal{G}, \left\{ \mathbf{h}^{(k)}_u \forall u \in \mathcal{V} \right\}, \left\{ \mathbf{h}^{(k)}_{(u,v)} \forall (u,v) \in \mathcal{E} \right\} \right) \end{align*}\]

• 이 일반화된 메시지 패싱 프레임워크의 메시지 전달 작업과 관련하여 먼저 인시던트 노드의 임베딩을 기반으로 엣지 임베딩을 업데이트한다.

• 다음으로, 모든 인시던트 엣지에 대한 엣지 임베딩을 집계하여 노드 임베딩을 업데이트한다.

• 그래프 임베딩은 노드 및 엣지 표현 모두에 대한 업데이트 방정식에 사용되며, 그래프 수준 임베딩 자체는 각 반복이 끝날 때 모든 노드 및 엣지 임베딩을 집계하여 업데이트된다).

참고자료

[1] Hamilton, W. L. (2020). Graph Representation Learning. Morgan & Claypool Publishers.