CS224W - (9) Machine Learning with Heterogeneous Graphs
이종 그래프(Heterogeneous Graphs)
이종 그래프는 다양한 노드 타입과 엣지 타입을 가지는 그래프를 말합니다.
위 그림처럼 두 개의 노드 타입과 두 개의 엣지 타입을 가진 그래프가 있다고 가정해보겠습니다. 논문, 저자라는 두 개의 노드 타입이 있고, 인용과 선호라는 두 개의 엣지 타입이 있습니다. 그래프에서 모든 연결은 노드와 노드 사이에 이루어지므로 총 여덟 가지의 관계 타입이 생깁니다.
- (논문, 인용, 논문)
- (논문, 선호, 논문)
- (논문, 인용, 저자)
- (논문, 선호, 저자)
- (저자, 인용, 저자)
- (저자, 선호, 저자)
- (저자, 인용, 논문)
- (저자, 선호, 논문)
이처럼 관계 타입은 (시작 노드, 엣지, 도착 노드) 로 정의할 수 있습니다. 관계 타입은 노드와 엣지 사이의 상호 작용을 훨씬 잘 설명합니다.
이종 그래프(heterogeneous graph)는 다음과 같이 정의합니다.
\[G = (V, E, \tau, \phi)\]- 어떤 노드 타입을 가진 노드: $v \in V$
- 노드 $v$의 노드 타입: $\tau(v)$
- 어떤 엣지 타입을 가진 엣지: $(u, v) \in E$
- 엣지 $(u, v)$의 엣지 타입: $\phi(u, v)$
- 엣지 $e$의 관계 타입: $r(u, v) = (\tau(v), \phi(u, v), \tau(v))$
이종 그래프는 많은 곳에서 볼 수 있습니다. 위처럼 이커머스 도메인에서도 볼 수 있습니다. 사용자, 아이템, 쿼리, 위치 등 다양한 노드 타입이 존재하고, 구매, 방문, 검색 등의 다양한 엣지 타입을 갖습니다. 서로 다른 노드 타입에 따라 다른 피처 공간을 갖습니다.
또 다른 예로는 아카데미를 들 수 있습니다. 저자, 논문, 분야 등의 노드 타입을 갖고 출판, 인용 등의 엣지 타입을 갖습니다.
여기서 생각해보면 노드 타입과 엣지 타입은 피처로 사용할 수 있을 것 같습니다. 각 노드 타입과 엣지 타입에 대해서 원 핫 인코딩을 수행하면 간단하게 피처로 만들 수 있는데요. 그러면 이종 그래프는 일반 그래프와 똑같아집니다. 그러면 어떤 상황에서 이종 그래프가 필요할까요?
우선 원 핫 인코딩을 효과적으로 수행할 수 없는 상황에 필요합니다. 노드마다 갖는 노드 타입이 다르거나 엣지마다 갖는 엣지 타입이 다른 경우에 필요한거죠. 예를 들어 저자 노드는 네 개의 피처를, 논문 노드는 다섯 개의 피처를 가지면 원 핫인코딩을 수행할 수 없습니다. 두 번째로 상호작용에서 서로 다른 관계 타입을 갖는 경우입니다. (영어, 번역, 프랑스어)와 (영어, 번역, 중국어)는 다른 모델이 필요하니까요.
결론적으로 이종 그래프는 훨씬 표현력이 높은 그래프 표현 방식입니다. 엔티티 간의 다양한 유형의 상호 작용을 잡아낼 수 있습니다. 하지만 계산이나 저장 공간의 관점에서 훨씬 큰 비용을 가지고 구현도 훨씬 복잡합니다. 이런 문제를 해결하기 위해 이종 그래프를 일반 그래프로 변환하는 많은 방법이 존재합니다.
관계형 GCN (Relational GCN, RGCN)
기본적인 GCN은 다음과 같습니다.
\[h_v^{(l)} = \sigma \left( W^{(l)} \sum_{u \in N(v)} \frac{h_u^{(l-1)}}{|N(v)|} \right)\]이제 GCN을 다양한 엣지/관계 타입을 가진 이종 그래프를 처리할 수 있도록 확장시키려고 합니다. 우선 하나의 관계를 가진 방향이 있는 그래프로 시작하겠습니다.
GCN에서 타겟 노드인 A에 대한 표현은 A 방향으로 메시지를 전달하기만 하면 됐습니다.
그러면 위 그래프처럼 다양한 관계 타입을 갖는 그래프는 어떻게 해야할까요? 다양한 관계 타입마다 서로 다른 뉴럴 네트워크 가중치를 사용하면 됩니다. 아래처럼 말이죠.
그래서 관계형 GCN(RGCN) 은 다음과 같이 수학적으로 쓸 수 있습니다.
\[h_v^{(l+1)} = \sigma \left( \sum_{r \in R} \sum_{u \in N_v^r} \frac{1}{|N_v^r|} W_r^{(l)} h_u^{(l)} + W_0^{(l)} h_v^{(l)} \right)\]메시지 전달은 다음과 같습니다. 우선 주어진 관계에 대해 각 이웃의 메시지 전달은 다음과 같습니다.
\[m_{u, r}^{(l)} = \frac{1}{|N_v^r|} W_r^{(l)} h_u^{(l)}\]자기 자신에 대한 메시지 전달은 다음과 같습니다.
\[m_v^{(l)} = W_0^{(l)} h_v^{(l)}\]그리고 이웃과 자기 자신으로부터의 메시지를 모두 더하고 활성화 함수를 적용합니다.
\[h_v^{(l+1)} = \sigma \left( \text{Sum} \left( \left\{ m_{u, r}^{(l)}, \; u \in N(v) \right\} \cup \left\{ m_v^{(l)} \right\} \right) \right)\]이렇게 설계했을 때 각 관계마다 레이어 개수인 $L$ 개의 행렬 $W_r^{(i)}$을 계산해야 합니다. 그리고 각 $W_r^{(i)}$의 크기는 $d^{(l+1)} \times d^{(l)}$ 입니다. 따라서 관계의 수가 늘어날 수록 계산해야 하는 파라미터의 수가 기하급수적으로 증가합니다. 이런 경우 오버피팅같은 문제가 발생할 수 있는데요. 다음 두 방법을 통해서 가중치 행렬을 규제화(regularize)할 수 있습니다.
- Block diagonal matrix 사용
- Basis learning
RGCN 규제화
Block Diagonal Matrix
Block Diagonal Matrix
Block diagonal matrix를 통해서 가중치 행렬을 보다 희소하게 만드는 것이 목적입니다. 가중치 행렬을 위 그림처럼 B 개의 블록으로 구분 짓게 되면 파라미터의 수는 블록의 개수에 비례하여 줄어듭니다. 각 차원마다 블록의 개수만큼 연산이 줄고 블록의 개수만큼 연산하기 때문입니다. Block diagonal matrix 형태의 $W_r$은 수식으로 아래와 같이 나타낼 수 있습니다.
\[W_r = \begin{bmatrix} W_{r_1} & 0 & \cdots & 0 \\ 0 & W_{r_2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & W_{r_B} \end{bmatrix}\]Basis Learning
Basis learning은 다른 관계에 걸쳐서 가중치를 공유하는 방식입니다. 각 관계의 행렬을 기저 변환(basis transformation)의 선형 결합(linear combination) 으로 표현하는 것인데요. $B$ 개의 기저(basis)에 대해서 가중치 행렬은 다음과 같습니다.
\[W_r = \sum^B_{b=1} a_{rb} \cdot V_b\]- $V_b$: 기저 행렬
- $a_{rb}$: $V_b$에 대한 가중치
이 경우 각 관계는 $a_{rb}$만 학습하면 됩니다.
예시
위와 같이 그래프가 주어졌을 때 노드 분류 태스크는 주어진 노드에 대해 레이블을 예측하는 작업을 수행합니다. RGCN은 마지막 레이어의 표현을 사용하는데요. 만약 $k$ 개의 클래스에 대해서 노드 A의 클래스를 예측한다면 마지막 레이어에서 $h_A^{(L)} \in \mathbb{R}^k$가 각 클래스에 대한 확률을 나타냅니다.
하지만 링크 예측 태스크라면 더 복잡해집니다. 링크 예측 태스크의 경우 모든 엣지를 다음 네 가지 범주로 나눕니다.
- 학습 메시지 엣지(training message edges)
- 학습 감독 엣지(training supervision edges)
- 검증 엣지(validation edge)
- 테스트 엣지(test edge)
위와 같은 그래프에서 $(E, r_3, A)$를 학습 감독 엣지로 가정하고 나머지 엣지는 모두 학습 메시지 엣지로 가정하겠습니다. 이제 RGCN을 이용해 $(E, r_3, A)$에 대한 점수를 매겨야 합니다. 이 과정은 다음의 순서를 따릅니다.
- $E$와 $A$에 대한 최종 임베딩 벡터, $h_E^{(L)}, h_A^{(L)}$를 계산합니다.
- 두 벡터를 이용해 관계에 점수를 매길 함수를 정의합니다. $f_r: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}.$
- 다음 점수를 구합니다. $f_{r_3}(h_E, h_A) = h_E^T W_{r_3} h_A.$
학습 과정은 다음과 같습니다.
- RGCN을 이용해 학습 감독 엣지인 $(E, r_3, A)$의 점수를 구합니다.
- 학습 감독 엣지 $(E, r_3, A)$에서 도착 노드를 변조하여 $(E, r_3, B)$, $(E, r_3, D)$와 같은 네거티브 엣지를 생성합니다.
- 이때 네거티브 엣지는 실제 그래프에 존재하지 않는 엣지만을 생성합니다.
- 네거티브 엣지에 대한 점수를 계산합니다.
- 크로스 엔트로피를 이용해 최적화합니다.
- 이때 학습 감독 엣지에 대한 점수는 최대화하고 네거티브 엣지에 대한 점수는 최소화합니다.
- 예시를 수식으로 쓴다면 다음과 같습니다.
평가할 때는 검증과 테스트를 동시에 하는데요. 학습 메시지 엣지와 학습 감독 엣지를 이용해 검증 엣지를 예측합니다. 위 그림처럼 $(E, r_3, D)$를 예측하는데 이때 $(E, r_3, B)$와 같이 학습 메시지 엣지나 학습 감독 엣지에 없는 엣지보다 항상 높은 스코어가 나오는 것이 좋습니다. 위 그림을 토대로 평가는 다음의 순서를 거칩니다.
- $(E, r_3, D)$의 점수를 계산합니다.
- 모든 네거티브 엣지에 대해 점수를 계산합니다.
- ${ (E, r_3, v) \mid v \in { B, F } }$
- $(E, r_3, D)$의 순위 $RK$ 를 얻습니다.
- 다음의 메트릭을 계산합니다.
- Hits@$k$: 1 [$RK \leq K$]
- Reciprocal Rank: $\frac{1}{RK}$
Heterogeneous Graph Transformer (HGT)
기존에 GNN에 어텐션을 활용했던 Graph Attention Network는 다음과 같습니다.
\[h_v^{(l)} = \sigma \left( \sum_{u \in N(v)} \alpha_{vu} W^{(l)} h_u^{(l-1)} \right)\]어텐션을 활용했기 때문에 노드의 이웃이 모두 똑같이 중요한게 아니게 되죠. 어텐션 가중치인 $a_{vu}$로 인해 입력 데이터에서 더 중요한 부분에 집중하고 되고 나머지에 대해선 크게 집중하지 않습니다. 그러면 GAT를 이종 그래프에 어떻게 적용할 수 있을까요?
아쉽게도 GAT를 그대로 다른 노드 타입과 다른 엣지 타입을 가진 이종 그래프에 적용할 수는 없습니다. 각 관계 타입마다 어텐션을 적용하기에는 계산 비용이 너무 커지기도 합니다.
그래서 HGT는 트랜스포머(Transformer)에서 제안한 Scaled Dot-Product Attention을 활용합니다.
\[\text{Attention}(Q, K, V) = \text{softmax} \left( \frac{QK^T}{\sqrt{d_k}} \right)V\]여기서 $Q$는 쿼리, $K$는 키, $V$는 값을 의미합니다. 각각은 (배치 사이즈, 차원)의 크기를 갖습니다. 또한 각각은 입력 데이터에 대해 선형 레이어를 태워서 얻을 수 있습니다.
- $Q = Q_\text{Linear}(X)$
- $K = K_\text{Linear}(X)$
- $V = V_\text{Linear}(X)$
그리고 $l$번째 레이어를 $H^{(l)}$라고 할 때 다음과 같습니다.
\[H^{(l)}[t] \leftarrow \text{Aggregate}_{\forall s \in N(t), \forall e \in E(s, t)} \left( \text{Attention}(s, t) \cdot \text{Message}(s) \right)\]
그리고 노드 타입과 엣지 유형에 종속적인 어텐션 메커니즘을 사용해 이종 그래프의 어텐션으로 분해합니다. 만약 세 개의 노드 가중치 행렬과 두 개의 엣지 가중치 행렬이 있다면 이와 같은 분해 없이는 모두 $3 \times 2 \times 3 = 18$ 개의 관계 타입에 대한 가중치 행렬이 필요합니다. 각각의 가중치 행렬을 구분하기 위해서 멀티 헤드 어텐션(Multi-head Attention)을 활용해야 할 것 같지만 그러면 같은 피처 분포를 공유하게 되기 때문에 적절하지 않습니다. 이 문제를 해결하기 위해서 HGT에서는 이종 상호 어텐션(Heterogenerous Mutual Attention) 매커니즘을 도입합니다.
\[\begin{aligned} \text{ATT-head}^i(s, e, t) & = \left( K^i(s) W^\text{ATT}_{\phi(e)} Q^i (t)^T \right) \\ K^i(s) & = K\text{-Linear}^i_{\tau(s)} \left(H^{(l-1)}[s] \right) \\ Q^i(t) &= Q\text{-Linear}_\tau(t)^i \left( H^{(l-1)}[t] \right) \end{aligned}\]각 관계 $(\tau(s), \phi(e), \tau(t))$는 고유한 가중치 집합을 갖게 됩니다.
- $\tau(s)$: $s$에 대한 노드 타입
- $\phi(e)$: $e$에 대한 엣지 타입
- $\tau(s)$와 $\tau(t)$는 $K\text{-Linear}_{\tau(s)}$와 $Q\text{-Linear}_{\tau(t)}$를 파라미터화 하는데, 각각은 더 나아가 키와 쿼리 벡터 $K(s)$와 $Q(t)$로 반환됩니다.
- 엣지 타입 $\phi(e)$는 $W_\phi(e)$를 직접 파라미터화 합니다.
최종적으로 전체 HGT 레이어는 다음과 같습니다.
\[\tilde{H}^{(l)}[t] = \bigoplus_{\forall s \in N(t)} \left( \text{Attention}_\text{HGT} (s, e, t) \cdot \text{Message}_\text{HGT} (s, e, t) \right)\]마찬가지로 HGT는 메시지 계산에서 노드 타입과 엣지 타입으로 가중치를 분해합니다.
\[\text{Message}_\text{HGT}(s, e, t) = \|_{i \in [1, h]} \text{MSG-head}^i(s, e, t)\] \[\text{MSG-head}^i(s, e, t) = \text{M-Linear}^i_{\tau(s)} \left( H^{(l-1)}[s] \right) W_{\phi(e)}^\text{MSG}\]- $\text{M-Linear}^i_{\tau(s)}$ : 각 노드 타입에 대한 가중치
- $W_{\phi(e)}^\text{MSG}$: 각 엣지 타입에 대한 가중치
이종 그래프 GNN 설계하기
마지막으로 일반적인 GNN 디자인을 이종 그래프로 어떻게 확장할 수 있을까요?
우선 메시지 계산은 다음과 같이 할 수 있습니다.
\[m_u^{(l)} = \text{MSG}_r^{(l)} \left( h_u^{(l-1)} \right)\]노드는 여러 종류의 메시지를 받을 수 있습니다. 메시지의 종류는 관계 타입의 수와 같습니다. 그래서 각 관계 타입마다 서로 다른 메시지 함수를 만들어줘야 합니다. 그래서 위 식의 경우 $r = (u, e, v)$ 라고 가정하면 노드 $v$가 엣지 타입 $e$로 연결되어 있는 노드 $u$로부터 메시지를 받는게 됩니다.
각 노드는 이웃 노드로부터 여러 종류의 메시지를 수신할 수 있고, 여러 이웃 노드가 각 메시지 종류에 속할 수 있습니다. 그래서 집계의 경우 두 단계의 메시지 전달을 정의하여 집계합니다.
\[h_v^{(l)} = \text{AGG}_\text{all}^{(l)} \left( \text{AGG}_r^{(l)} \left( m_u^{(l)}, \; u \in N_r(v) \right) \right)\]노드로 전송된 모든 메시지가 주어졌을 때 각 메시지 유형 내에서 엣지 타입에 속하는 메시지를 $\text{AGG}_r^{(l)}$ 로 집계합니다. 그리고 모든 엣지 타입에 대해서 $\text{AGG}_\text{all}^{(l)}$ 로 모두 집계합니다.
그리고 이종 그래프에 대해서도 전처리 레이어와 후처리 레이어를 둘 수 있는데요. 각 노드 타입에 대한 MLP 레이어가 됩니다.
\[h_v^{(l)} = \text{MLP}_{\tau(v)} (h_v^{(l)})\]또한 GNN 디자인 시 성능을 향상 시켰던 스킵 커넥션이나 배치 정규화, 레이어 정규화도 성능에 도움을 줄 수 있습니다.
기존 GNN은 그래프 피처나 그래프 구조에 대한 조작을 가하여 성능을 향상시켰었는데요. 이종 그래프에 대해서도 비슷하게 조작이 가능합니다. 우선 피처 관점에서 크게 두 가지 옵션이 있습니다.
- 각 관계 타입마다 node degree와 같은 그래프 통계값을 계산하기
- 관계 타입을 무시하고 전체 그래프에 대해 통계값을 계산하기
그래프 구조에서는 기존과 같이 이웃 샘플링과 서브그래프 샘플링을 여전히 사용할 수 있습니다. 다만 각 관계 타입마다 샘플링을 할지, 아니면 전체 그래프에 대해서 샘플링을 할지 정해야 합니다.
마지막으로 이종 그래프의 예측 헤드입니다. 노드 레벨의 예측 헤드는 다음과 같습니다.
\[\hat{y}_v = \text{Head}_\text{node, $\tau(v)$} \left( h_v^{(L)} \right) = W_{\tau(v)}^{(H)} h_v^{(L)}\]엣지 레벨의 예측 헤드는 다음과 같습니다.
\[\hat{y}_{uv} = \text{Head}_\text{edge, $r$} \left( h_u^{(L)}, h_v^{(L)} \right) = \text{Linear}_r \left(\text{Concat} \left( h_u^{(L)}, h_v^{(L)} \right) \right)\]마지막으로 그래프 레벨의 예측 헤드는 다음과 같습니다.
\[\hat{y}_G = \text{AGG} \left( \text{Head}_\text{graph, $i$} \left( \left\{ h_v^{(L)} \in \mathbb{R}^d, \; \forall \tau(v) = i \right\} \right) \right)\]