관계형 GNN: R-GCN 그리고 그 너머

📍 현재 위치: 4부 · 그래프 신경망과 그 한계 — 13장. 메시지 전달은 2계층 그래프 합성곱 신경망(Graph Convolutional Network, GCN) 청사진을 세웠지만, 우리의 지식 그래프를 무향이고 유형 없는 엣지 덩어리로 납작하게 만들어서야 그렇게 할 수 있었습니다; 이 장은 다섯 개의 관계를 다시 메시지 안에 되돌려 놓습니다.

앞 장은 조용한 희생을 치렀습니다. GCN 청사진을 돌리기 위해 gnn.py는 학계 세계의 18개 트리플 전부를 하나의 대칭 인접 행렬로 뭉갰고, advises(bob, dave)와 about(p1, logic)는 구별할 수 없는 1 항목이 되어 버렸습니다. 그래도 모델은 유보된 네 노드 중 셋을 정확히 분류했지만, 한 손을 등 뒤로 묶은 채 그렇게 했습니다. 왜냐하면 지식 그래프에서 엣지의 유형이야말로 그 엣지가 말하는 것의 대부분이기 때문입니다. 들어오는 authored 엣지는 "당신은 논문입니다"를 뜻하고, 들어오는 advises 엣지는 당신이 학생이라는 강력한 증거입니다(여기 네 명의 지도 대상 중 셋이 실제로 학생입니다); 유형 없는 모델은 오직 "당신에게는 이웃이 있다"만을 듣습니다. 이 장은 그 유형들을 되돌립니다. 관계형 그래프 합성곱 신경망(Relational Graph Convolutional Network, R-GCN)은 모든 관계에 자신만의 가중치 행렬을 부여하고, 그 전부를 이전과 같은 수작업 역전파로 함께 학습하며, 그런 다음 청구서와 마주합니다: 관계의 수에 비례해 선형적으로 늘어나는 파라미터, 그리고 그것을 제어하는 기저 분해입니다 [1]. 아래의 모든 숫자는 examples/neural/rgcn.py의 커밋된 실행에서 나옵니다.

쉽게 말하면

다섯 개 언어로 편지를 받는 회사의 우편실을 상상해 보세요. 값싼 방식은 번역가 한 명을 고용해 모든 것을 하나의 밋밋한 의역으로 옮기는 것입니다: 베를린에서 온 법적 통지문과 리스본에서 온 연애편지가 비슷하게 들리게 되고, 어떤 언어로 도착했는가에 담겨 있던 의미는 사라집니다. R-GCN 방식은 언어마다 전담 번역가 한 명을 고용하고, 발신용으로 언어마다 한 명을 더 고용하며, 당신 자신의 메모를 당신에게 그대로 파일링해 주는 사무원도 둡니다: 도합 열한 명의 전문가입니다. 번역은 충실해지지만, 이제 급여는 언어를 추가할 때마다 늘어납니다. 마지막 묘수는 뛰어난 다국어 구사자 딱 두 명만 고용하고, 각 언어의 번역가를 그 둘의 개인적인 배합("다국어 구사자 1이 70퍼센트, 다국어 구사자 2가 30퍼센트")으로 서술하는 것입니다. 그 배합이 바로 기저 분해입니다: 실력의 거의 전부는 공유되고, 각 언어는 오직 두 개의 배합 숫자만큼만 비용이 듭니다.

이 장에서 다루는 내용

• 엣지 유형을 뭉개는 것이 왜 손실이 되는가: 우리 그래프 위에서 논증됩니다. 네 가지 서로 다른 클래스의 노드 넷이 같은 차수를 공유하고, 열여덟 개 엣지 중 열넷이 서로 다른 클래스의 노드를 잇고 있어서, 오직 관계 레이블만이 기관과 교수를 구분해 줄 수 있습니다.
• R-GCN 전파 규칙, 기호 하나하나: 관계별 이웃 $N_r(i)$, 관계별 정규화 상수 $c_{i,r}$, 별도의 자기 루프 행렬 $W_0$, 그리고 방향 있는 엣지를 따라 양방향으로 정보가 흐르기 전에 역관계가 왜 반드시 추가되어야 하는가.
• 주장이 아니라 계산으로 얻은 파라미터 장부: 전체 모델의 경우 계층당 880개 가중치 곱하기 두 계층으로, 배열로부터 인용되며, 왜 관계 수 $\lvert\mathcal{R}\rvert$에 선형인 증가가 실제 지식 그래프에서는 감당 불가능한가.
• 유도된 기저 분해: $B = 2$개의 공유 원형을 가진 $W_r = \sum_b a_{rb} V_b$, 혼합을 거치는 기울기가 항목별로 풀어져 있고($V_b$에 대해서는 가중합, $a_{rb}$에 대해서는 트레이스), 전체 모델의 1760개 옆에 나란히 놓인 364개 파라미터라는 커밋된 값.
• 경험적 척추로서의 세 갈래 애블레이션: 동일한 코드, 시드, 과제로 훈련된 비유형, 전체, 기저 모델이며, 유보 정확도는 1/4, 4/4, 3/4로 정직하게 읽힙니다.
• 실세계의 교훈으로서의 정칙화: 기저가 단순한 압축 트릭이 아니라, 대규모 지식 그래프를 지배하는 희귀한 관계들을 위한 과적합 방지 장치인 이유.
• R-GCN 너머: 메시지 안에서 관계 임베딩과 개체 임베딩을 합성하는 CompGCN, 링크 예측을 벨만-포드(Bellman–Ford) 방식의 경로 기반 관점으로 보는 NBFNet, 그리고 이들이 열어젖힌 관계-불가지론적 방향.

왜 가중치 행렬 하나로는 충분하지 않은가

앞 장의 모델이 실제로 무엇을 계산하는지에서 시작해 봅시다. 유형 없는 GCN에서 노드 $i$가 이웃 $j$로부터 받는 메시지는 $W \mathbf{h}_j$입니다: 이웃의 현재 특징 벡터 $\mathbf{h}_j$가 그 계층의 공유된 단일 가중치 행렬 $W$를 통과한 것입니다. 이 행렬은 어떤 관계가 그 메시지를 전달했는지 알지 못하고, 알 수도 없습니다. 우리 그래프에서는 이것이 진짜 손실입니다. 다섯 개의 관계가 서로 양립할 수 없는 다섯 가지 변환을 구현하기 때문입니다.

관계	연결 대상	엣지 수	예시 트리플
advises	사람 → 사람	4	(alice, advises, bob)
affiliated	사람 → 기관	5	(carol, affiliated, cmu)
authored	사람 → 논문	4	(bob, authored, p1)
cites	논문 → 논문	2	(p2, cites, p1)
about	논문 → 주제	3	(p1, about, logic)

advises 엣지는 어떤 사람에 대한 증거를 다른 사람에 대한 증거로 사상하고, about 엣지는 논문에 대한 증거를 주제에 대한 증거로 사상합니다. 하나의 $W$가 둘 다를 섬기도록 강제하는 것은 $W$가 타협안이, 즉 서로 다른 방향을 가리켜야 할 변환들의 평균이 되어야 함을 뜻합니다. 이 실패 양상에는 이름이 있습니다: 이질성(heterophily)입니다. 연결된 노드들이 서로 다른 레이블을 지니는 경향이 있어서, 이웃을 순진하게 평균 내면 노드의 표현이 잘못된 클래스 쪽으로 끌려가는 상황을 가리킵니다 [2]. 연결된 논문들이 대개 주제를 공유하는 인용 네트워크는 동질적(homophilous)이고 관대하지만, 지식 그래프는 구성상 이질적입니다. 우리 그래프에서 세어 보면: 18개 엣지 중 오직 넷만이 같은 클래스의 노드를 잇습니다(교수들 사이의 alice→bob, 학생들 사이의 carol→erin, 그리고 논문들 사이의 두 cites 엣지). 나머지 열넷은 클래스 경계를 가로지르며, 이 열넷에 대해서는 관계 레이블이 곧 신호입니다.

앞 장의 과제가 이 손실을 구체적으로 만들어 줍니다. 우리는 정체성 없는 특징을 가진 5-클래스 개체 유형 분류를 하고 있습니다: 각 노드의 입력은 자신의 차수에 대한 원-핫 인코딩이므로, 모델이 학습하는 모든 것은 구조로부터 나와야 합니다(rgcn.py 67–85번째 줄). 이제 차수-3 노드들을 봅시다: alice는 교수, cmu는 기관, dave는 학생, p3는 논문입니다. 네 노드, 네 클래스, 동일한 입력 특징입니다. 이들을 갈라놓을 수 있는 유일한 것은 이웃 관계이며, 그 이웃 관계는 주로 유형에서 다릅니다: cmu의 세 엣지는 모두 들어오는 affiliated이고, dave의 하나뿐인 들어오는 엣지는 advises이며, p3의 것은 authored입니다. 유형 없는 모델은 각 이웃 관계 속 차수들의 혼합이 우연히 다르기를 바라야 하지만, 유형화된 모델은 그저 메시지가 어떤 채널로 도착하는지를 읽으면 됩니다. 이 장 끝의 애블레이션은 바로 이 격차를 측정합니다.

전파 규칙, 기호 하나하나

노드 $i$에 대한 R-GCN 계층 갱신은 다음과 같습니다 [1]:

$$\mathbf{h}_i' \;=\; \mathrm{ReLU}\!\left( \sum_{r \in \mathcal{R}} \; \sum_{j \in N_r(i)} \frac{1}{c_{i,r}}\, W_r\, \mathbf{h}_j \;+\; W_0\, \mathbf{h}_i \right).$$

한 기호씩, 평범한 말로 먼저 풀어 봅시다. 인덱스 $i$는 $N = 13$개의 노드 위를 움직이고, $\mathbf{h}_i$는 노드 $i$의 현재 특징 벡터입니다(입력 계층에서는, 길이 $d_{\text{in}} = 5$짜리 벡터인 자신의 원-핫 차수입니다). 집합 $\mathcal{R}$은 관계 유형들을 모아 둔 것입니다. 각 관계 $r$에 대해, 관계별 이웃(per-relation neighborhood) $N_r(i) = \lbrace j : (j, r, i) \in E \rbrace$는 $i$로 향하는 $r$-엣지를 가진 노드 $j$들의 집합입니다. 여기서 $E$는 엣지 집합, 즉 우리 그래프의 18개 방향 있는 유형화된 트리플입니다; $j \in N_r(i)$에 대한 합은 그런 각 이웃마다 메시지 하나씩을 모읍니다. 각 관계는 자신만의 가중치 행렬(weight matrix) $W_r$을 가지므로, 메시지 $W_r \mathbf{h}_j$는 어떤 관계가 그것을 전달했는지에 따라 다르게 변환됩니다: 이것이 바로 수선의 전부입니다. 정규화 상수(normalizer) $c_{i,r} = \lvert N_r(i)\rvert$는 관계별 진입 차수, 즉 $i$의 $r$-이웃 개수입니다; 이것으로 나누면 각 관계의 메시지 더미가 평균이 됩니다. 그래서 affiliated 이웃이 다섯인 노드가 하나뿐인 노드보다 단순히 더 시끄러워지지 않습니다. 마지막으로 $W_0$는 별도의 자기 루프 행렬(self-loop matrix)입니다: 노드 $i$ 자신의 벡터가 자신만의 변환을 거쳐 더해지므로, 노드는 결코 이웃들의 목소리 속에서 자기 자신을 잃지 않습니다. ReLU(Rectified Linear Unit, 정류 선형 유닛), 즉 항목별 사상 $\max(0, \cdot)$은 이전과 같은 비선형 함수입니다.

$N_r(i)$의 한 가지 미묘한 점은 신중히 짚고 넘어갈 가치가 있습니다. 이를 잘못 이해하면 그래프의 절반이 침묵하게 되기 때문입니다. 정의는 엣지 방향을 따라 메시지를 읽습니다: 트리플 (alice, advises, bob)에 대해, alice $\in N_{\text{advises}}(\text{bob})$이므로 이 엣지는 자신의 꼬리인 bob에게 메시지를 전달합니다; 머리인 alice는 이로부터 아무것도 받지 못합니다. 우리 그래프에서 이것은 치명적입니다: alice는 어떤 트리플의 꼬리로도 등장하지 않으므로(그녀의 세 엣지 모두 바깥을 향합니다), 기본 관계만으로는 그녀의 갱신이 $\mathrm{ReLU}(W_0 \mathbf{h}_{\text{alice}})$가 되어, 오직 자신의 차수만의 함수가 되어 버립니다. 표준적인 수선은 모든 관계 $r$에 대해, 반대 방향으로 흐르는 엣지를 가진 역관계(inverse relation) $r^{-1}$을 추가하는 것입니다: (alice, advises, bob)은 또한 bob $\in N_{\text{advises}^{-1}}(\text{alice})$를 만들어 내고, 이는 자신만의 가중치 행렬 $W_{r^{-1}}$을 가집니다 [1]. 이제 alice는 advises⁻¹ 채널을 통해 bob으로부터 소식을 듣고, 그것도 유형화된 채로 듣습니다: 지도교수인 것과 지도 대상인 것은 서로 다른 채널에서 서로 다른 행렬로 도착하며, 이는 정확히 "교수 대 학생"의 구분이 필요로 하는 것입니다.

짝이 되는 코드는 이 모든 것을 채널 하나당 인접 행렬 하나씩의 스택으로 만듭니다: 5개의 기본 관계, 5개의 역관계, 그리고 $\hat{A}_{\text{self}} = I$, 곧 단위 행렬(identity matrix, 대각선은 1이고 나머지는 0이어서 이 채널은 각 노드에게 자기 자신의 벡터를 건네줍니다)인 자기 루프를 자신만의 채널로 두어, 도합 11개 채널이 됩니다(rgcn.py 91–133번째 줄):

    channels: list[tuple[str, np.ndarray]] = []
    if typed:
        for rel in RELATIONS:                     # base: message head → tail
            A = np.zeros((N, N))
            for h, r, t in TRIPLES:
                if r == rel:
                    A[E_ID[t], E_ID[h]] = 1.0
            channels.append((rel, A))
        for rel in RELATIONS:                     # inverse: message tail → head
            A = np.zeros((N, N))
            for h, r, t in TRIPLES:
                if r == rel:
                    A[E_ID[h], E_ID[t]] = 1.0
            channels.append((rel + "⁻¹", A))
    else:
        A = np.zeros((N, N))                      # one untyped, symmetric channel
        for h, _, t in TRIPLES:
            A[E_ID[t], E_ID[h]] = 1.0
            A[E_ID[h], E_ID[t]] = 1.0
        channels.append(("edge", A))
    channels.append(("self", np.eye(N)))          # the self-loop channel

    names = [name for name, _ in channels]
    A_hat = np.stack([A for _, A in channels])
    # Row normalization: divide row i of Â_r by c_{i,r} = |N_r(i)|.
    c = A_hat.sum(axis=2, keepdims=True)
    A_hat = A_hat / np.where(c == 0.0, 1.0, c)

else 분기에 주목하십시오: 같은 함수가 typed=False로 호출되면, 유형 없는 설정을 구성합니다(양방향의 모든 엣지가 하나의 관계로 뭉쳐지고, 자기 루프가 더해져 2개 채널이 됩니다). 그 분기는 우리가 나중에 훈련할 애블레이션이며, 유형화 여부 외에는 아무것도 다르지 않도록 동일한 코드 경로 안에 산다는 점이 중요합니다. 맨 아래의 행 정규화가 $1/c_{i,r}$을 구현합니다: $\hat{A}_r$의 항목 $(i, j)$는 $j \in N_r(i)$이면 $1/c_{i,r}$이 되고 그 외에는 0이 되며, 전부 0인 행은 그대로 둡니다. 이 모듈을 실행하면 채널들을 출력하고 정규화 상수를 구체적인 행 하나로 근거 짓습니다; 이는 실제로 커밋된 출력입니다:

11 relation channels (5 base + 5 inverse + 1 self-loop), edges per channel:
  about:3  advises:4  affiliated:5  authored:4  cites:2  about⁻¹:3  advises⁻¹:4  affiliated⁻¹:5  authored⁻¹:4  cites⁻¹:2  self:13
  e.g. c_(cmu,affiliated) = 3 (carol, dave, erin): each neighbour contributes weight 1/3 = 0.3333

모든 $\hat{A}_r$이 이미 자신의 정규화 상수를 지니고 있고 자기 루프 채널이 $W_0 \mathbf{h}_i$ 항을 제공하므로, 전체 계층은 특징 행렬 $H$(노드당 한 행) 위의 하나의 행렬 방정식으로 뭉개집니다:

$$H' \;=\; \mathrm{ReLU}\!\left( \sum_{r=1}^{R} \hat{A}_r\, H\, W_r \right), \qquad R = 11,$$

여기서 코드는 행-벡터 관례를 따르므로 각 $W_r$은 오른쪽에서 곱해집니다(rgcn.py 195–218번째 줄). 출력 계층에서는 ReLU가 소프트맥스 분류 헤드로 대체되며, 이는 앞 장과 정확히 같습니다(209–217번째 줄). 이것이 아래의 순전파와 역전파가 다루는 형태입니다.

하나의 회색 행렬에서 열한 개의 유형화된 채널로, 다시 두 개의 공유 원형으로: 학계 그래프 위에서의 R-GCN 전파 규칙과 그 파라미터 청구서. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

주장이 아니라 계산으로 얻은 파라미터 장부

유형화된 가중치는 가중치 비용을 치릅니다. $d_{\text{in}}$개의 입력 특징을 $d_{\text{out}}$개의 출력으로 사상하는 계층은 채널당 하나의 $d_{\text{in}} \times d_{\text{out}}$ 행렬을 필요로 하므로, 계층당 개수는 $R \cdot d_{\text{in}} \cdot d_{\text{out}}$입니다. 우리 네트워크는 은닉 폭 16의 두 계층을 가집니다(rgcn.py 42–46번째 줄): 계층 1은 5개 차수 특징을 16개 은닉 유닛으로 사상하고, 계층 2는 16개 은닉 유닛을 $K = 5$개 클래스로 사상합니다. 이 모듈은 공식이 아니라 실제 배열로부터 파라미터를 셉니다(param_counts, 182–190번째 줄), 그리고 다음을 출력합니다:

parameters (counted from the actual arrays)
  layer     full (11 relations)      basis (B=2)
  layer 1   11×(5×16) =   880        2×(5×16) + 11×2 =  182
  layer 2   11×(16×5) =   880        2×(16×5) + 11×2 =  182
  total                 1760                          364   (4.8× fewer)

산술을 한 번 확인해 봅시다: 계층 1에 대해 $11 \times 5 \times 16 = 880$, 계층 2에 대해 순서를 뒤집은 같은 곱, 그리고 $880 + 880 = 1760$개의 훈련 가능한 가중치입니다. 채널이 2개뿐인 비유형 애블레이션은 계층당 $2 \times 80 = 160$개, 도합 320개가 필요합니다. 이 장부의 요점은 그것이 드러내는 확장 법칙입니다: 이 개수는 관계 수에 대해 선형이며, 관계가 하나씩 늘 때마다 전체 $d_{\text{in}} \cdot d_{\text{out}}$ 블록 하나가 통째로 곱해집니다. 우리의 장난감 모델은 다섯 개의 관계 때문에 비유형 모델보다 5.5배의 비용을 치릅니다. 실제 벤치마크 그래프는 이 증가를 구체적으로 만들어 줍니다: 표준적인 Freebase 기반 벤치마크로 관계 어휘가 정확히 237개인 FB15k-237은 $2 \times 237 + 1 = 475$개의 채널을 필요로 할 것이고, 은닉 폭 500에서 하나의 은닉-은닉 계층만 해도 우리 공식으로는 $475 \times 500 \times 500 \approx 1.19 \times 10^8$개의 가중치를 담게 될 것입니다. 관계 유형이 수천 개인 지식 그래프가 실제로 존재하며, 그런 그래프에서는 전체 파라미터화란 그저 적어 낼 수조차 없습니다. 대부분의 관계가 지닌 몇 안 되는 엣지로 훈련하는 것은 말할 것도 없습니다 [1].

기저 분해: 둘로부터 나온 열한 개의 행렬

이 수선은 각 관계에 자유로운 행렬을 주는 것을 멈추고, 대신 각 관계에 레시피를 주는 것입니다. 공유되는 소수 $B$개의 기저 행렬(basis matrices) $V_1, \ldots, V_B$(여기서는 $B = 2$)를 고정합니다. 각각은 전체 $d_{\text{in}} \times d_{\text{out}}$ 크기이며, 모든 관계의 행렬을 이들의 학습된 선형 혼합으로 적습니다 [1]:

$$W_r \;=\; \sum_{b=1}^{B} a_{rb}\, V_b .$$

스칼라 $a_{rb}$는 혼합 계수(mixing coefficients)입니다: 관계 $r$이 $B$개의 공유 원형에 대해 갖는 개인적인 배합으로, 관계마다 $B$개의 숫자입니다. 계층당 파라미터 개수는 $B \cdot d_{\text{in}} \cdot d_{\text{out}} + R \cdot B$가 됩니다: 계층 1의 경우 $2 \times 80 + 11 \times 2 = 182$이고, 도합 364로, 위 장부에서 인용된 숫자이며 전체 모델보다 4.8배 적습니다. 이 공식을 구조적으로 읽어 봅시다: 값비싼 $d_{\text{in}} \cdot d_{\text{out}}$ 블록은 이제 $R$이 아니라 상수 $B$로 곱해지며, 관계 어휘와 함께 늘어나는 항은 오직 값싼 $R \cdot B$개의 계수 표뿐입니다. 관계를 하나 추가하는 비용은 여든 개가 아니라 두 개의 숫자입니다. 순전파는 전파하기 전에 레시피로부터 각 $W_r$을 실체화합니다(rgcn.py 169–179번째 줄):

    if params["kind"] == "full":
        return params["W1"], params["W2"]
    R = params["a1"].shape[0]
    W1 = np.zeros((R, D_IN, HIDDEN))
    W2 = np.zeros((R, HIDDEN, K))
    for r in range(R):
        for b in range(BASES):
            # W_r = Σ_b a_{rb} V_b   (same B bases shared by all R relations)
            W1[r] += params["a1"][r, b] * params["V1"][b]
            W2[r] += params["a2"][r, b] * params["V2"][b]
    return W1, W2

유형화된 네트워크 훈련하기: 모든 기울기를 손으로

두 파라미터화 모두 앞 장과 같은 과제로 훈련됩니다: 9개의 레이블 붙은 노드에 대한 마스크된 교차 엔트로피이며, bob, dave, p2, cmu는 유보되고, 시드 0에서 학습률 $\eta = 0.5$로 400 에폭 동안 완전 배치 경사 하강법을 씁니다(train_model, rgcn.py 223–310번째 줄). 손실은

$$L \;=\; -\frac{1}{\lvert T\rvert} \sum_{i \in T} \ln p_{i,\,y_i}, \qquad \lvert T\rvert = 9,$$

여기서 $T$는 레이블 붙은 훈련 노드들의 집합이고, $y_i$는 노드 $i$의 참 클래스이며, $\ln$은 자연로그(밑이 $e$인 로그)이고, $p_{i,k}$는 네트워크가 노드 $i$에 대해 클래스 $k$에 부여하는 소프트맥스 확률입니다. 로짓에서의 기울기는 메시지 전달을 이끌었던 것과 같은 소프트맥스-더하기-교차 엔트로피 잔차이며, 다시 유도하기에 짧으므로 이 장은 그 자체로 완결됩니다. $z_{i,k}$를 노드 $i$의 클래스 $k$에 대한 로짓(소프트맥스 이전 점수), $c$를 참 클래스라 쓰면, $p_{i,k} = e^{z_{i,k}} / \sum_{k'} e^{z_{i,k'}}$이며, 여기서 합산 인덱스 $k'$는 5개 클래스에 걸쳐 돕니다. 로그는 그 몫을 차이로 바꾸어, 한 노드의 손실을 다음과 같이 줍니다:

$$L_i \;=\; -\ln p_{i,c} \;=\; -z_{i,c} + \ln \sum_{k'} e^{z_{i,k'}} .$$

각 항을 하나의 로짓 $z_{i,k}$에 대해 미분합니다. 첫 번째 항은 선형입니다: $\partial(-z_{i,c})/\partial z_{i,k}$는 $k = c$일 때 $-1$이고 그 외에는 $0$이며, 이는 정확히 원-핫 목표 $y_{i,k}$에 대한 $-y_{i,k}$입니다. 두 번째 항은 연쇄 법칙을 거칩니다. 정규화 합을 $S = \sum_{k'} e^{z_{i,k'}}$로 줄여 쓰면, $\partial(\ln S)/\partial z_{i,k} = (1/S)\,\partial S/\partial z_{i,k}$이고, $S$ 중 $k' = k$ 항만이 $z_{i,k}$를 포함하므로 그 도함수는 $\partial S/\partial z_{i,k} = e^{z_{i,k}}$입니다. 그 결과 나오는 몫 $e^{z_{i,k}}/S$는 소프트맥스 확률 $p_{i,k}$ 그 자체입니다. 두 조각을 더하면:

$$\frac{\partial L_i}{\partial z_{i,k}} \;=\; p_{i,k} - y_{i,k} .$$

9개의 레이블 붙은 행에 대해 평균 내고 마스크로 나머지는 0으로 만들면, 이것이 G2 = (P - Y) * mask / n_tr입니다(rgcn.py 254번째 줄).

새로운 것은 이 기울기가 유형화된 채널을 거쳐 가는 경로입니다. $G$를 $\partial L/\partial Z_2$(노드당 한 행, 클래스당 한 열인 $13 \times 5$ 행렬)라 쓰고, $M_r = \hat{A}_r H_1$을 관계 $r$의 집계되고 정규화된 이웃 특징이라 하면, 계층 2는 $Z_2 = \sum_r M_r W_{2,r}$로 읽힙니다. 하나의 관계 행렬 $W_{2,\rho}$(인덱스 $\rho$는 하나의 채널을 고르고, $m$은 16개의 은닉 좌표를 인덱싱하며, $k$와 $n$은 5개의 클래스를 인덱싱합니다)에 대해 미분하기 위해, 항목별로 전개하면:

$$(Z_2)_{ik} \;=\; \sum_{r=1}^{R} \sum_{m=1}^{16} (M_r)_{im}\, (W_{2,r})_{mk} \quad\Longrightarrow\quad \frac{\partial (Z_2)_{ik}}{\partial (W_{2,\rho})_{mn}} \;=\; (M_\rho)_{im}\,\delta_{kn},$$

여기서 $\delta_{kn}$은 크로네커 델타(Kronecker delta)로, $k = n$일 때 1이고 그 외에는 0입니다: 채널 $\rho$의 행렬 항목 $(m, n)$은 로짓의 오직 $n$번째 열만을, 그것도 오직 채널 $\rho$를 통해서만 건드립니다. 연쇄 법칙은 그런 다음 둘의 곱을 합산합니다:

$$\frac{\partial L}{\partial (W_{2,\rho})_{mn}} \;=\; \sum_{i,k} G_{ik}\, (M_\rho)_{im}\,\delta_{kn} \;=\; \sum_{i} (M_\rho^{\top})_{mi}\, G_{in} \;=\; \big( (\hat{A}_\rho H_1)^{\top} G \big)_{mn}.$$

각 채널은 자신만의 집계된 특징으로부터 만들어진 자신만의 기울기를 얻습니다. 은닉 상태는 모든 채널로부터의 기여를 모읍니다; $(Z_2)_{ik} = \sum_r \sum_j \sum_m (\hat{A}_r)_{ij} (H_1)_{jm} (W_{2,r})_{mk}$를 전개하고 $(H_1)_{jm}$에 대해 미분하면 $\sum_r (\hat{A}_r)_{ij}(W_{2,r})_{mk}$를 얻습니다. 연쇄 법칙은 그런 다음 이를 모든 로짓 항목에 걸쳐 $G$와 축약하고, 각 인자를 전치를 통해 다시 쓰면 행렬 곱이 드러납니다:

$$\frac{\partial L}{\partial (H_1)_{jm}} \;=\; \sum_{i,k} G_{ik} \sum_{r=1}^{R} (\hat{A}_r)_{ij}\, (W_{2,r})_{mk} \;=\; \sum_{r=1}^{R} \sum_{i,k} (\hat{A}_r^{\top})_{ji}\, G_{ik}\, (W_{2,r}^{\top})_{km} \;=\; \sum_{r=1}^{R} \big( \hat{A}_r^{\top}\, G\, W_{2,r}^{\top} \big)_{jm},$$

이는 모든 항목 $(j, m)$에서 동시에 성립하는 항등식이므로, 행렬로 쓰면

$$\frac{\partial L}{\partial H_1} \;=\; \sum_{r=1}^{R} \hat{A}_r^{\top}\, G\, W_{2,r}^{\top}.$$

$\hat{A}_r$에 붙은 전치는 앞 장에서와는 다른 방식으로 여기서 중요해집니다: GCN의 연산자는 대칭이었지만, $\hat{A}_r$은 방향성을 가지며, $\hat{A}_r^{\top}$는 모든 화살표를 거꾸로 돌려, 노드 $i$의 오차에 대한 credit을 그것에게 말을 걸었던 이웃 $j$들에게 보냅니다. ReLU 게이트와 계층 1의 가중치 기울기는 그런 다음 같은 패턴을 반복합니다. 이 모든 것은 그대로 구현되어 있습니다(rgcn.py 251–269번째 줄):

        # ---- Backward pass (all gradients hand-derived) -----------------
        # Softmax + cross-entropy cancel to the classic residual:
        #   ∂L/∂Z2[i,:] = (p_i − y_i)/|T| for labelled i, 0 for held-out i.
        G2 = (P - Y) * mask / n_tr
        # Layer-2 weights and hidden state.  From Z2 = Σ_r (Â_r H1) W2_r:
        #   ∂L/∂W2_r = (Â_r H1)ᵀ G2          (each channel's own gradient)
        #   ∂L/∂H1   = Σ_r Â_rᵀ (G2 W2_rᵀ)   (the message, transposed back)
        dW2 = np.zeros_like(W2)
        dH1 = np.zeros_like(H1)
        for r in range(R):
            dW2[r] = (A_hat[r] @ H1).T @ G2
            dH1 += A_hat[r].T @ (G2 @ W2[r].T)
        # ReLU: H1 = max(0, Z1)  ⟹  ∂L/∂Z1 = ∂L/∂H1 ⊙ 1[Z1 > 0]
        G1 = dH1 * (Z1 > 0.0)
        # Layer-1 weights.  From Z1 = Σ_r (Â_r X) W1_r:
        #   ∂L/∂W1_r = (Â_r X)ᵀ G1
        dW1 = np.zeros_like(W1)
        for r in range(R):
            dW1[r] = (A_hat[r] @ X).T @ G1

전체 모델의 경우, 갱신은 각 $W_r$ 스택에 대한 평범한 경사 하강 스텝 $\theta \leftarrow \theta - \eta\, \partial L/\partial \theta$입니다. 기저 모델은 연쇄 법칙을 한 번 더 적용해야 합니다. 왜냐하면 훈련 가능한 대상이 원형 $V_b$와 계수 $a_{rb}$이며, $L$은 실체화된 $W_r = \sum_b a_{rb} V_b$를 통해서만 이들에 도달하기 때문입니다. 두 도함수를 항목별로 구해 봅시다. $\beta$는 미분 대상이 되는 하나의 고정된 원형을 가리키고(계속 도는 합산 인덱스 $b$와는 구별됩니다), $(m', n')$은 그 원형의 하나의 고정된 항목을 가리킵니다. $(W_r)_{mn} = \sum_b a_{rb} (V_b)_{mn}$이므로, $(W_r)_{mn}$을 원형 $V_\beta$의 항목 $(m', n')$에 대해 미분하면 $a_{r\beta}\,\delta_{mm'}\,\delta_{nn'}$입니다: 항목이 일치할 때는 계수, 그 외에는 0입니다. 연쇄 법칙을 모든 관계와 모든 항목에 대해 합산하면, 델타들이 안쪽 합을 무너뜨립니다:

$$\frac{\partial L}{\partial (V_\beta)_{m'n'}} \;=\; \sum_{r=1}^{R} \sum_{m,n} \frac{\partial L}{\partial (W_r)_{mn}}\, a_{r\beta}\,\delta_{mm'}\,\delta_{nn'} \;=\; \sum_{r=1}^{R} a_{r\beta}\, \frac{\partial L}{\partial (W_r)_{m'n'}},$$

이는 모든 항목에서 동시에 성립하므로, 행렬로는 $\partial L/\partial V_\beta = \sum_r a_{r\beta}\, \partial L/\partial W_r$입니다. 원형 $\beta$는 모든 관계의 행렬 안에 앉아 있으므로, 그 기울기는 열한 개 관계별 기울기 전체의 계수 가중합입니다. 하나의 계수 $a_{\rho\beta}$에 대해, $(W_\rho)_{mn}$의 도함수는 단순히 $(V_\beta)_{mn}$이므로,

$$\frac{\partial L}{\partial a_{\rho\beta}} \;=\; \sum_{m,n} \frac{\partial L}{\partial (W_\rho)_{mn}}\, (V_\beta)_{mn} \;=\; \Big\langle V_\beta,\ \frac{\partial L}{\partial W_\rho} \Big\rangle_F \;=\; \operatorname{tr}\!\Big( V_\beta^{\top}\, \frac{\partial L}{\partial W_\rho} \Big),$$

이는 프로베니우스 내적(Frobenius inner product)으로, 원형과 그 관계의 기울기의 (대응하는 항목들의 곱의 합이며, 대각 항목들의 합인 트레이스 $\operatorname{tr}$과 같은) $V_\beta^{\top} \partial L/\partial W_\rho$의 트레이스입니다. 이는 관계 $\rho$의 배합을 원형 $\beta$ 쪽으로 얼마나 밀면 손실이 얼마나 줄어들지를 측정합니다. 두 공식 모두 다음과 같이 그대로 등장합니다(rgcn.py 276–288번째 줄):

            # Chain rule through the decomposition W_r = Σ_b a_{rb} V_b:
            #   ∂L/∂V_b   = Σ_r a_{rb} · ∂L/∂W_r      (V_b sits inside every W_r)
            #   ∂L/∂a_{rb} = ⟨V_b, ∂L/∂W_r⟩_F         (Frobenius inner product)
            for a_key, v_key, dW in (("a1", "V1", dW1), ("a2", "V2", dW2)):
                a, V = params[a_key], params[v_key]
                dV = np.zeros_like(V)
                da = np.zeros_like(a)
                for r in range(R):
                    for b in range(BASES):
                        dV[b] += a[r, b] * dW[r]
                        da[r, b] = float(np.sum(V[b] * dW[r]))
                a -= LR * da
                V -= LR * dV

세 모델 모두 훈련 손실을 사실상 0까지 내려갑니다; 커밋된 손실 추적은 유형화된 모델이 훨씬 빨리 그곳에 도달함을 보여줍니다(비유형 모델의 첫 에폭 손실은 균등 추측 값 $\ln 5 \approx 1.6094$에 가까운 반면, 전체 모델은 열한 개 채널의 합이 초기 로짓에 더 큰 퍼짐을 주기 때문에 더 높게 시작합니다):

에폭	비유형	R-GCN 전체	R-GCN 기저
1	1.6267	2.0372	1.6622
10	0.8565	0.0857	0.2525
50	0.1172	0.0072	0.0028
100	0.0369	0.0030	0.0009
200	0.0127	0.0013	0.0004
400	0.0048	0.0006	0.0002

애블레이션: 유형화된 가중치가 산 것

훈련 손실은 질문이 아닙니다; 세 모델 모두 자신의 9개 레이블에 완벽하게 들어맞습니다. 진짜 질문은 어떤 모델도 레이블을 본 적 없는 네 노드에 대한 것이며, 여기 커밋된 답이 있습니다. 노드별로, 그런 다음 요약해서 봅니다(run, rgcn.py 315–345번째 줄, 세 전시물 전부를 훈련합니다):

held-out predictions (4 nodes never seen with a label)
  node   true          untyped          R-GCN full       R-GCN basis
  bob    Professor     Student      ✗   Professor    ✓   Professor    ✓
  dave   Student       Paper        ✗   Student      ✓   Student      ✓
  p2     Paper         Paper        ✓   Paper        ✓   Paper        ✓
  cmu    Institution   Professor    ✗   Institution  ✓   Professor    ✗

relation ablation — same code, same seed, only the typing differs
  model                        params   train acc     held-out acc
  untyped (1 edge relation)       320   9/9 1.0000    1/4 0.2500
  R-GCN full (11 relations)      1760   9/9 1.0000    4/4 1.0000
  R-GCN basis (B=2)               364   9/9 1.0000    3/4 0.7500

이 행들에서 메커니즘을 읽어 냅시다. 비유형 모델은 p2 하나만을 맞히는데, 이는 정확히 차수 충돌 논증이 예측했던 실패입니다: 관계 레이블이 벗겨진 채로, bob의 뒤섞인 이웃(교수 하나, 학생 둘, 논문 하나, 기관 하나)은 "학생"으로 읽히고, 세 개의 affiliated 엣지의 목표라는 것이 정체성의 전부인 cmu는 "교수"로 읽힙니다. 전체 R-GCN은 넷 모두를 맞힙니다. 채널이 유형 정보를 직접 실어 나르기 때문입니다: cmu의 메시지는 모두 affiliated로 도착하고, dave의 유일한 들어오는 엣지는 advises로 도착하는데, 이 채널의 들어오는 쪽은 훈련 레이블이 학생과 연관 짓는 채널입니다(레이블 붙은 두 명의 지도 대상 carol과 erin은 둘 다 학생입니다); 그리고 bob은 advises로 발신하는 유일한 유보 노드로, 두 번 발신하며, 이는 advises⁻¹ 채널이 그에게 되돌려 전달합니다. 기저 모델은 bob, dave, p2는 지키지만 cmu를 "교수"에게 잃습니다: 두 개의 공유 원형이 열한 개의 채널을 섬기다 보니 affiliated가 완전히 구별되는 변환을 유지할 수 없고, cmu는 정확히 그 증거가 그 하나의 채널 안에 사는 노드이기 때문입니다.

일반화하기 전에 두 가지 정직한 언급이 필요합니다. 첫째, 비유형 행은 앞 장의 GCN을 다시 실행한 것이 아닙니다: gnn.py는 계층당 하나의 행렬을 가진 대칭 연산자 $D^{-1/2}(A+I)D^{-1/2}$(앞 장의 정규화로, 여기서 $A$는 유형 없는 인접 행렬, $I$는 단위 행렬, $D$는 각 노드의 $A+I$ 안 엣지 수를 담은 대각 차수 행렬입니다)를 썼던 반면, 이 애블레이션은 R-GCN 코드 경로 안에서 비유형 설정을 다시 세웁니다(행-정규화 평균 집계, 별도의 자기 루프 행렬; rgcn.py 120–132번째 줄). 그래서 유형화 행과 비유형 행은 유형화 여부만 다르고 다른 것은 다르지 않습니다: 같은 시드, 같은 특징, 같은 최적화기입니다. 이것이 바로 이 비교를 일화가 아니라 애블레이션으로 만들어 주는 것이며, 두 파일의 비유형 숫자가 일치할 필요가 없는 이유이기도 합니다. 둘째, 규모입니다: 네 개의 유보 노드와 하나의 시드는 효과 크기가 아니라 메커니즘을 보여줍니다. 4/4와 3/4 사이의 격차는 노드 하나이며, "여기서 압축이 무언가를 대가로 치렀다"로 읽어야지 "기저 모델은 25퍼센트 더 나쁘다"로 읽어서는 안 됩니다. 이 작은 그래프가 명확하게 보여주는 것은 방향과 원인이며, 이 모듈은 정확히 그만큼을 자신의 역량 단언으로 지킵니다: 유형화는 최소한 비유형과 같아야 하고, 전체 모델은 유보 노드에서 3/4 이상을 유지해야 하며, 기저 모델은 엄격히 더 작아야 합니다(rgcn.py 336–342번째 줄). 이 모델이 만들어진 벤치마크들에서, 유형화된 메시지 전달은 GCN이 다중 관계 데이터에서 애초에 경쟁력을 갖게 만든 것이었습니다 [1].

기저 분해는 압축이 아니라 정칙화입니다

이 트릭을 "메모리 절약"으로 분류하고 싶은 유혹이 있지만, 그 더 깊은 역할은 통계적입니다. 우리의 채널 집계를 다시 봅시다: cites는 2개 엣지, about은 3개, advises와 authored는 4개, affiliated는 5개입니다. 전체 모델에서 각 관계는 계층당 80개의 가중치를 얻으므로, cites 행렬은 2개의 엣지에 맞춰지는 160개의 숫자입니다. 우리 그래프는 실제 상황의 축소판입니다: 대규모 지식 그래프에서 관계 빈도는 심하게 롱테일이며, 대부분의 관계는 희귀합니다. 그래서 관계당 엣지 몇 개는 예외가 아니라 표준입니다. 희귀한 관계마다 전용 행렬을 두는 것은 과적합에 대한 초대장입니다: 그것은 자신이 본 몇 안 되는 엣지를 암기하고 아무것에도 일반화하지 못할 수 있습니다.

기저 분해는 그 해독제이며, 우리가 유도한 기울기가 그 이유를 보여줍니다. 원형 $V_b$에 대한 갱신은 모든 관계로부터 온 $a_{rb}$-가중 기울기를 합산하므로, 5개의 affiliated 엣지, 4개의 advises 엣지, 2개의 cites 엣지가 모두 같은 두 개의 공유 행렬을 빚어냅니다: 희귀한 관계는 흔한 관계로부터 통계적 힘을 빌리고, 각 희귀한 관계의 개인 용량은 $B$개의 혼합 계수로 상한이 정해져 있어 아무리 애써도 많은 것을 암기할 수 없습니다. 이는 합성곱 신경망이 이미지 위치들에 걸쳐 필터를 공유하는 것과 정확히 같은 의미에서의 파라미터 공유입니다. 원래 설계는 같은 목적을 지닌 두 번째 방식, 즉 블록-대각 분해도 제공하는데, 이는 각 $W_r$을 혼합이 아니라 블록 구조로 제약합니다; 둘 다 관계 수에 따른 파라미터의 급격한 증가와 그에 따른 희귀 관계에서의 과적합을 막기 위해 존재합니다 [1].

R-GCN 너머: 합성, 경로, 그리고 전이

R-GCN은 관계를 행렬로 다루는데, 이는 강력하지만 비용이 크고, 우리가 보았듯 희귀한 관계와 긴장 관계에 있습니다. CompGCN은 관계를 대신 벡터로 만들어, 1부의 통화를 되살립니다: 관계도 개체와 마찬가지로 임베딩 $\mathbf{e}_r$을 얻고, 관계 $r$을 따라 이웃 $j$로부터 오는 메시지는 두 임베딩의 합성(composition) $\phi(\mathbf{e}_j, \mathbf{e}_r)$이며, 관계가 아니라 오직 엣지 방향(들어오는, 역방향, 자기 자신)에만 의존하는 가중치 행렬을 통과합니다 [3]. 합성 연산자들은 오랜 친구들입니다: 뺄셈($\mathbf{e}_j - \mathbf{e}_r$, TransE의 병진적 관점), 항목별 곱셈($\mathbf{e}_j \odot \mathbf{e}_r$, DistMult의 쌍선형 관점), 그리고 순환 상관(holographic embedding의 압축된 상호작용)입니다. 이 설계는 이 권의 두 절반을 통합합니다: 지식 그래프 임베딩의 채점 함수가 GNN의 메시지 함수가 되고, 관계 임베딩은 개체 임베딩과 나란히 계층마다 갱신되며, 관계당 파라미터 개수는 행렬에서 벡터로 떨어집니다.

NBFNet은 표현되는 대상 자체를 바꿉니다. 노드 분류는 노드당 벡터 하나를 원하지만, 링크 예측은 쌍에 대한 질문입니다. NBFNet은 일반화된 벨만-포드(Bellman–Ford) 재귀를 통해 쌍 표현 $\mathbf{h}_q(u, v)$를 직접 계산합니다: 출발점 $u$에서 지시자를 초기화하고(경계 조건), 엣지를 따라 관계 표현을 합성하는 메시지를 반복적으로 집계하여, $k$번의 반복 후에는 $(u, v)$의 표현이 $u$에서 $v$까지 길이 $k$ 이하의 모든 경로를 요약하게 됩니다 [4]. 카츠 지수(Katz index)와 개인화된 페이지랭크(personalized PageRank) 같은 고전적인 경로 휴리스틱은 고정된 연산자를 가진 같은 재귀의 특수한 경우로 도출되며, 표현이 저장된 개체별 벡터가 아니라 경로로부터 만들어지기 때문에 이 모델은 귀납적입니다: 훈련 중에는 본 적 없는 개체들 사이의 쌍도 채점할 수 있습니다. 그 논리를 끝까지 밀어붙여, ULTRA는 심지어 관계 자체도 본 적 없는 일급 객체로 만듭니다. 관계-대-관계 상호작용의 작은 그래프로부터 관계 표현을 계산하여, 하나의 사전 훈련된 모델이 새로운 관계 어휘를 가진 완전히 새로운 지식 그래프로 제로샷 전이될 수 있게 합니다 [5]. 그 궤적은 분명합니다: 관계당 행렬 하나에서, 관계당 벡터 하나로, 그리고 관계별 파라미터가 전혀 없는 곳으로.

아직 풀리지 않은 부분

이 장은 메시지를 유형화함으로써 용량을 끌어올렸고, 애블레이션은 그 용량이 실재함을 보여줍니다. 관계, 폭, 깊이, 데이터가 충분하다면 메시지 전달이 무엇이든 구별할 수 있으리라고 가정하기 쉽습니다. 그럴 수 없으며, 그 장벽은 통계적인 것이 아니라 구조적인 것입니다. 여섯 노드 위의 두 그래프를 생각해 봅시다. 모든 노드가 같은 초기 특징을 지니고 있습니다: 하나의 육각 순환 그래프, 그리고 서로 떨어진 두 개의 삼각형입니다. 이들은 증명 가능하게 동형이 아닙니다(하나는 연결되어 있고 다른 하나는 그렇지 않으며, 하나는 삼각형을 포함하고 다른 하나는 그렇지 않습니다). 그러나 두 그래프 모두에서 모든 노드는 정확히 두 개의 이웃을 가지고, 그 이웃들도 두 개의 이웃을 가지며, 이는 영원히 계속됩니다: 메시지 전달의 매 라운드마다, 두 그래프의 모든 노드는 동일한 메시지 다중집합을 받으므로, 이 장과 앞 장이 만든 이 계열의 모든 모델(GCN, 임의 개수의 관계를 가진 R-GCN, CompGCN)은 두 그래프의 모든 노드에 같은 벡터를 부여합니다. 노드에서 그래프 전체로의 도약은 그 자체로 닫힙니다: 두 그래프 모두 동일한 벡터를 지닌 여섯 노드를 가지므로, 순열 불변 그래프 판독(합, 평균, 혹은 노드 벡터들의 다중집합으로, 이는 메시지 전달 모델이 그래프 전체를 요약하는 유일한 방법입니다)이라면 무엇이든 두 그래프에 동일한 표현을 부여해야 합니다. 어떤 훈련 실행도, 어떤 학습률도, 어떤 기저 크기도 이것을 바꾸지 못합니다; 실패는 계산의 형태, 즉 순열 등변성과 지역성을 우리에게 주었던 바로 그 이웃 집계 루프 안에 있습니다. 이 계열은 정확히 무엇을 구별할 수 있고, 무엇이 증명 가능하게 그 너머에 있을까요? 이 질문에는 정확한 답이 있습니다. 고전적인 조합론적 검사, 그리고 놀랍게도 하나의 논리이며, 이것이 다음 장의 주제입니다.

왜 중요한가

관계는 이 시리즈의 기호적 절반과 신경망적 절반이 그래프 위에서 만나는 지점입니다. 2권의 추론기(reasoner)는 그 핵심까지 역할을 인식하고 있습니다: 완결 규칙 CR3과 CR4는 역할별로 발동하며, Professor ⊑ ∃advises.Student 같은 EL++ 공리는 advises가 about과 구별되지 않는다면 무의미합니다. 관계 유형을 지워 버리는 신경망 인코더는 온톨로지가 묻는 질문조차 표현할 수 없으므로, 유형화된 메시지 전달은 추론기와 나란히 작동한다고 주장하는 어떤 GNN에게도 최소한의 입장권입니다. 그리고 R-GCN은 지식 베이스와 학습된 모델을 짝짓는 시스템에서 기본 그래프 인코더로 남아 있습니다. 이는 바로 이 학계 세계 위에서 4권이 쌓아 올리는 설정입니다. 기저 분해의 교훈은 훨씬 더 멀리까지 이어집니다: "값비싼 구조는 공유하고, 소수의 계수로 개인화하라"는 되풀이되는 설계 패턴이며, 그 기울기, 즉 공유되는 부분으로는 가중합이, 개인적인 부분으로는 프로베니우스 내적이 되는 그 형태는, 모델이 공유 요소와 특정 요소로 인수분해되는 곳이라면 어디에서든 다시 등장합니다.

핵심 용어

• 다중 그래프(multigraph, 다중 관계 그래프) — 엣지가 유형을 지니고 두 노드가 서로 다른 유형의 여러 엣지로 이어질 수 있는 그래프; 지식 그래프의 자연스러운 형태입니다.
• 이질성(heterophily) — 연결된 노드가 서로 다른 레이블을 지니는 경향으로, 순진한 이웃 평균을 무너뜨립니다; 우리의 18개 엣지 중 열넷이 서로 다른 클래스의 노드를 잇습니다.
• 관계별 이웃(per-relation neighborhood) $N_r(i)$ — $i$로 향하는 $r$-엣지를 가진 노드들의 집합; R-GCN은 구성원마다 유형화된 메시지 하나씩을 합산합니다.
• 정규화 상수(normalizer) $c_{i,r}$ — 관계별 진입 차수 $\lvert N_r(i)\rvert$; 이것으로 나누면 각 채널이 합이 아니라 평균을 전달하게 됩니다.
• 역관계 채널(inverse relation channel) — 각 관계 $r$에 대해, 꼬리에서 머리로 메시지를 나르는 채널 $r^{-1}$을 추가하여, 방향 있는 엣지가 두 끝점 모두에게, 각각 유형화된 방식으로 정보를 알려 줍니다.
• 자기 루프 행렬(self-loop matrix) $W_0$ — 노드 자신의 벡터에 대한 별도의 변환으로, 항등 인접 채널로 구현됩니다.
• 기저 분해(basis decomposition) — 모든 관계 행렬을 $B$개의 공유 원형의 혼합 $W_r = \sum_b a_{rb} V_b$로 적어, 계층당 파라미터를 $B \cdot d_{\text{in}} \cdot d_{\text{out}} + R \cdot B$로 상한 짓는 것입니다.
• 혼합 계수(mixing coefficients) $a_{rb}$ — 관계 $r$이 원형들에 대해 갖는 배합 가중치; 그 기울기는 프로베니우스 내적 $\langle V_b, \partial L/\partial W_r\rangle_F$입니다.
• 프로베니우스 내적(Frobenius inner product) — 대응하는 행렬 항목들의 곱의 합 $\operatorname{tr}(A^{\top}B)$; 행렬들 사이의 자연스러운 내적입니다.
• 애블레이션(ablation) — 코드, 시드, 과제, 예산을 고정한 채로 정확히 하나의 재료(여기서는 관계 유형화)만을 제거하는 실험으로, 그 결과의 격차를 그 재료에 귀속시킬 수 있게 합니다.

이 장 다음에는

유형화된 가중치는 실재하는 용량을 사 왔습니다: 같은 그래프, 같은 특징, 같은 최적화기가, 메시지가 어떤 관계에 실려 왔는지를 아는 순간 유보 노드에서 4분의 1에서 4분의 4로 올라갔습니다. 그러나 육각 순환 그래프와 두 개의 삼각형이 기다리고 있으며, 메시지 전달 계열의 어떤 구성원도 이 둘을 구별할 수 없습니다. 다음 장 표현력의 천장은 그 장벽을 정확히 짚어 냅니다: 메시지 전달이 결코 넘어설 수 없는 색 정제(color-refinement) 알고리즘인 바이스파일러-레만(Weisfeiler–Leman) 검사(1-WL), 두 변수 계수 논리 C²에서의 그것의 정확한 논리적 쌍둥이, 그리고 그 천장이 실제 그래프 위에서 나타나는 것을 지켜보는 wl.py의 커밋된 실행입니다. 천장이 어디에 있고 무엇으로 이루어져 있는지 아는 것이야말로, 그 주위를 설계하는 것과 그것에 부딪히는 것을 갈라놓습니다.

---

짝이 되는 코드: examples/neural/rgcn.py는 11개의 유형화된 채널을 만들고, 공유된 시드로부터 손으로 유도한 역전파를 통해 비유형, 전체, 기저 모델을 훈련하며, 이 장에 인용된 모든 표를 출력합니다; examples/neural/gnn.py는 이 코드가 확장하는 앞 장의 비유형 청사진입니다. examples/neural/에서 python3 rgcn.py를 실행해 모든 숫자를 재현하고, python3 validate.py를 실행해 이 장의 주장들을 역량 단언으로 재확인하십시오.