메시지 전달: GNN의 청사진

📍 현재 위치: 4부 · 그래프 신경망과 그 한계 — 12장. 쌍곡 임베딩은 기하 계열의 이야기를 마무리했습니다: 지금까지의 모든 모델은 각 개체에 하나의 점, 하나의 상자, 혹은 하나의 공을 배정하고 한 번에 트리플 하나씩을 채점했습니다. 이 장은 계산의 단위 자체를 바꿉니다: 그래프 신경망은 그래프 스스로 뒤섞는 일을 하게 함으로써 모든 노드의 표현을 한꺼번에 계산합니다.

이 권에 등장한 지금까지의 모든 임베딩 모델은 지식 그래프를 독립적인 트리플들의 자루처럼 다뤄 왔습니다: 트리플 하나를 뽑고, 채점하고, 두 개체 벡터와 하나의 관계를 조금 움직이고, 이를 반복하는 식입니다. 그래프의 연결 구조는 오직 어떤 트리플이 존재하느냐를 통해서만 들어왔습니다. 그래프 신경망(graph neural network, GNN)은 이를 뒤집습니다. GNN은 그래프 전체를 여러 계층으로 이루어진 스택 위로 흘려보내는데, 각 계층에서 모든 노드는 반복적으로 이웃들로부터 정보를 모으고 자신의 벡터를 갱신하며, 그 결과 두 계층을 지나고 나면 한 노드의 표현은 자신의 2홉 이웃 전체를 요약하게 됩니다. 놀라운 사실은 GNN 문헌에 등장하는 이름 붙은 아키텍처가 사실상 모두 하나의 추상화에 서로 다른 부품을 끼워 넣은 것에 불과하다는 점이며, 이 장은 그 추상화를 만들고, 정전적인 그래프 합성곱 신경망(Graph Convolutional Network, GCN)으로 구체화하고, 모든 기울기를 손으로 유도한 다음, 앞선 장들이 할 수 없었던 일을 해냅니다: 훈련된 네트워크의 성질을 수치로, 그중 하나는 비트 단위로 정확하게 증명하는 것입니다.

쉽게 말하면

작은 학과가 각 사람이 어떤 사람인지를 판단하려 하는데, 누구도 남의 파일을 들여다볼 수 없다고 상상해 보세요. 대신 한 시간에 한 번, 모든 사람이 자신의 직접적인 지인들에게 "지금 당신은 스스로를 어떻게 믿고 있나요?"라고 묻고, 그 답들을 자기 자신의 현재 믿음과 평균 내어, 그 혼합을 새로운 자기 서술로 삼습니다. 한 라운드가 지나면 당신은 지인들에 대해 알게 됩니다. 두 라운드가 지나면 지인의 지인들에 대해서도 알게 되는데, 왜냐하면 그들의 1라운드 믿음에는 이미 그들의 지인들이 담겨 있었기 때문입니다. 이 의식에는 두 가지 규칙이 박혀 있습니다: 평균에는 언제나 자기 자신을 포함시켜야 하고(그렇지 않으면 자신의 이력이 증발해 버립니다), 아주 인기 있는 사람은 소리치지 않고 속삭여야 합니다(그렇지 않으면 학과장을 아는 사람 때문에 모두가 귀먹게 됩니다). 그래프 신경망은 이 의식을 미분 가능하게 만든 것입니다: 믿음은 벡터가 되고, 혼합은 행렬 곱셈이 되며, 경사 하강법이 각자가 무엇을 전달할지를 조율합니다.

이 장에서 다루는 내용

• THE 추상화로서의 청사진 — 메시지, 집계, 갱신; 집계가 왜 이웃 다중집합에 대해 순열 불변이어야 하는지(어떤 수식보다 먼저 진술됩니다); GCN, GraphSAGE, GAT(Graph Attention Network), GIN(Graph Isomorphism Network)을 하나의 표 안의 칸으로 배치합니다.
• 하나씩 설계 결정을 쌓아 조립한 GCN 계층 — 인접 행렬 $A$와 차수 행렬 $D$를 해독합니다; $A$만으로는 왜 노드 자신의 특징이 지워지는지(그래서 $I$를 더합니다); 왜 정규화되지 않은 합이 차수에 비례해 커지는지(허브의 활성값이 자신의 차수와 함께 커진다는 것을 보입니다); 대칭 정규화 $\hat{A} = D^{-1/2}(A+I)D^{-1/2}$가 왜 스펙트럼을 길들이는지, 고유값 논증을 완전히 풀어냅니다.
• 핵심을 드러내도록 고른 특징 — $X$는 항등 특징이 아니라 원-핫 차수여서, 노드별로 아무것도 암기될 수 없습니다; 9개의 레이블 붙은 노드로 훈련하고 bob, dave, p2, cmu를 유보하는 준지도 분할입니다.
• 완전히 유도한 역전파 — $p - y$ 소프트맥스 기울기를 한 단계씩 다시 유도한 다음, ReLU와 두 가중치 행렬을 거치는 연쇄 법칙을, $\partial L/\partial W = (\hat{A}H)^\top \Delta$의 전치까지 포함해 다룹니다. 각 방정식은 gnn.py의 정확한 줄에 대응되며, 1, 50, 100, 200, 400 에폭에서 커밋된 손실 표가 함께 제시됩니다.
• 두 개의 정리, 두 개의 숫자 — 순열 등변성 $f(PAP^\top, PX) = Pf(A, X)$가 $2.22 \times 10^{-16}$까지 검증되고, 2홉 지역성이 비트 단위로 검증됩니다: 네 홉 떨어진 곳의 거대한 교란이 출력을 정확히 $0.0$만큼만 움직입니다.
• 유보된 노드에 대한 평결 — 레이블이 없는 4개 노드에 대한 실제 예측이며, 네트워크가 틀리는 하나의 사례와 차수만으로 이루어진 특징이 무엇을 구분할 수 있고 무엇을 구분할 수 없는지에 대한 정직한 분석을 담습니다.
• 아직 풀리지 않은 부분 — 연산자 $\hat{A}$는 지도하다(advises)와 인용하다(cites)를 같은 전선으로 취급합니다; 학계 그래프의 엣지들은 서로 다른 것을 의미하며, 다음 장은 각 관계에 자신만의 가중치를 부여합니다.

청사진: 메시지, 집계, 갱신

어떤 수식보다 먼저, 이후 모든 것을 좌우하는 하나의 제약을 테이블 위에 올려놓아야 합니다. 한 노드의 이웃들은 집합(더 정확히는 다중집합(multiset), 같은 원소가 두 번 이상 나타날 수 있는 집합)을 이룹니다. 집합에는 순서가 없습니다. bob의 "첫 번째 이웃"이라는 것은 없습니다; 그래프는 우리에게 alice, carol, dave, mit, p1을 순서 없는 모음으로 줄 뿐이며, 따라서 이들의 정보를 결합하는 어떤 함수든 어떤 순서로 읽든 같은 답을 내놓아야 합니다. 이런 성질을 지닌 함수를 순열 불변(permutation-invariant)이라 부릅니다: 입력을 어떻게 재배열하든 출력이 바뀌지 않는다는 뜻입니다. 합, 평균, 최댓값, 최솟값은 순열 불변이지만, 연쇄(concatenation)나 순차적인 무언가(예컨대 이웃들을 임의의 순서로 순환 신경망에 흘려 넣는 것)는 그렇지 않습니다. 이는 문체상의 취향이 아닙니다. 출력이 엣지 목록의 저장 순서에 좌우되는 모델은 그래프가 아니라 파일 형식에 대한 함수를 계산하고 있는 셈입니다.

이 제약을 못박아 둔 채로, 청사진은 세 부분으로 이루어집니다 [1]. 노드 $i$의 현재 벡터를 $h_i \in \mathbb{R}^d$라고 씁니다. 여기서 $d$는 표현의 폭(각 노드가 지니는 숫자의 개수)이고, $\mathbb{R}^d$는 길이 $d$짜리 실수 목록 전체의 집합입니다. $\mathcal{N}(i)$는 노드 $i$의 이웃 집합을 나타냅니다. 메시지 전달 신경망(message-passing neural network)의 한 계층은 모든 노드 $i$에 대해 동시에 다음을 계산합니다:

$$m_i \;=\; \operatorname{aggregate}\big(\{\, \operatorname{message}(h_i, h_j) : j \in \mathcal{N}(i) \,\}\big), \qquad h_i' \;=\; \operatorname{update}(h_i, m_i).$$

먼저 이를 평범한 말로 읽어 봅시다. 노드 $i$의 각 이웃 $j$는 두 끝점의 현재 상태로부터 계산된 벡터인 메시지를 만들어 냅니다. $i$에 도착한 메시지들은 순열 불변인 집계에 의해 하나의 벡터 $m_i$로 결합됩니다. 그런 다음 갱신 함수가 $m_i$를 $i$ 자신의 이전 상태와 혼합해 새로운 상태 $h_i'$를 만듭니다. 이런 계층을 $T$개 쌓으면 정보는 $T$홉만큼 걸어갑니다: 한 계층을 지나면 $h_i'$는 $i$의 직접적인 이웃을 반영하고, 두 계층을 지나면 이웃의 이웃을 반영하는 식으로 이어집니다. 이것이 발상의 전부입니다. 유명한 이름이 붙은 것들은 모두 이 세 자리를 채우는 하나의 선택에 불과합니다 [1][2]. 아래 표에서 $d_i$와 $d_j$는 노드 $i$와 $j$의 차수, 즉 이웃의 개수이며(다음 절에서 온전히 정의되고, 표현의 폭 $d$와는 다른 양입니다), GIN 행의 $\varepsilon$은 노드 자신의 상태가 이웃 합에 흡수되지 않도록 지켜 주는, 고정하거나 학습하는 스칼라입니다:

아키텍처	$j$에서 $i$로 가는 메시지	집계	갱신
GCN [3]	$1/\sqrt{d_i\, d_j}$로 스케일된 $h_j$	합(자기 루프가 $h_i$를 포함)	공유된 선형 사상 $W$, 그다음 ReLU
GraphSAGE [4]	$h_j$	표본 추출된 이웃 부분집합에 대한 평균 또는 최댓값 풀링	$h_i$와 연쇄한 뒤, 선형 사상 + 비선형 함수
GAT (어텐션에서 인용)	학습된 어텐션 계수 $\alpha_{ij}$로 가중된 $h_j$	어텐션 가중합	선형 사상 + 비선형 함수
GIN (표현력의 천장에서 인용)	$h_j$	합, 그리고 $(1+\varepsilon)\,h_i$	작은 다층 퍼셉트론

모든 행은 불변 제약을 따릅니다: 각 집계 열은 합, 평균, 최댓값, 혹은 가중합이며, 모두 순서에 무감각합니다. 각 행이 다른 것은 무엇을 맞바꾸느냐입니다. GCN은 엣지 가중치를 그래프의 차수로부터 고정하는데, 이는 값싸면서도, 곧 보게 되겠지만, 스펙트럼상으로 잘 작동합니다. GraphSAGE는 이웃을 표본 추출해 노드당 비용을 너무 커서 모든 엣지를 만질 수 없는 그래프에서도 일정하게 유지하며, 그 가중치가 고정된 노드 명단에 의존하지 않기 때문에 훈련 때 본 적 없는 노드도 임베딩할 수 있습니다(귀납적(inductive) 설정) [4]. GAT는 네트워크가 각 이웃이 얼마나 중요한지를 학습하도록 둡니다. GIN은 이웃 다중집합에 대한 정보를 가장 많이 보존한다는 것이 증명 가능한 유일한 집계를 선택하며, 이 점은 이 부(Part)의 마지막 장인 표현력의 천장의 주역이 됩니다. 이 장은 첫 번째 행을 처음부터 만드는데, 그 모든 상수를 제1원리로부터 정당화할 수 있는 칸이기 때문입니다.

청사진(메시지 → 집계 → 갱신), bob의 실제 이웃 위에서 실제 $\hat{A}$ 가중치로 구체화된 GCN, 그리고 훈련된 네트워크가 수치로 통과하는 두 개의 정리: 부동소수점 반올림 오차 수준의 등변성과 비트 단위의 2홉 지역성. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

두 개의 행렬로 표현한 그래프

kg.py의 학계 지식 그래프에는 13개의 개체와 18개의 트리플이 있습니다. 이 장에서는 의도적으로 관계 레이블을 잊습니다: ('alice', 'advises', 'bob')과 ('p2', 'cites', 'p1')은 둘 다 그냥 무향(undirected) 엣지가 됩니다. 그 결과는 인접 행렬(adjacency matrix) $A$로 인코딩되는데, 이는 노드마다 하나의 행과 하나의 열을 가진 표로, 항목 $A_{ij}$(행 $i$, 열 $j$)는 노드 $i$와 $j$를 잇는 엣지가 있으면 $1$, 없으면 $0$입니다. 무향이라는 것은 $A_{ij} = A_{ji}$를 의미하므로 $A$는 대칭(자기 자신의 전치와 같다는 뜻으로, $A^\top = A$이며, 전치 $\top$는 행렬을 대각선을 기준으로 뒤집습니다)입니다. 짝이 되는 파일은 이를 열 줄로, 그중 다섯 줄만 실행 가능한 코드로 만듭니다(gnn.py 56–65번째 줄):

def build_adjacency() -> np.ndarray:
    """The 18 triples as an undirected, unlabelled adjacency matrix A
    (13 x 13, symmetric, zero diagonal).  Relation types are dropped on
    purpose: this module isolates pure message passing; ``rgcn.py`` adds
    relation-specific weights."""
    a = np.zeros((N, N))
    for h, _r, t in kg.TRIPLES:
        i, j = kg.E_ID[h], kg.E_ID[t]
        a[i, j] = a[j, i] = 1.0
    return a

두 번째 행렬은 차수 행렬(degree matrix) $D$입니다: 노드 $i$의 차수(degree) $d_i$는 그 이웃의 개수, 즉 $A$의 행 $i$의 합이며, $D$는 대각선에 $d_1, \ldots, d_{13}$을 두고 나머지는 0인 대각 행렬입니다. 이 그래프에서 차수는 1부터 5까지 걸쳐 있습니다: 주제 노드 logic, ml, nesy는 각각 논문 하나에만 닿아 있고(차수 1), 두 학생을 지도하고 지도교수가 있고 논문을 썼고 소속을 가진 bob은 차수 5에 있습니다. 이 두 행렬이 GCN이 보게 되는 구조의 전부입니다.

왜 하필 행렬일까요? 행렬 곱셈 하나가 모든 노드에 대한 메시지 전달 라운드 전체를 한 번에 수행하기 때문입니다. 행 $i$가 $h_i^\top$인 행렬 $H$($13 \times d$, 노드당 한 행)로 노드 벡터들을 쌓아 봅시다. 그러면 행렬 곱셈의 정의에 따라 곱 $AH$의 행 $i$는 다음과 같습니다.

$$(AH)_i \;=\; \sum_{j=1}^{13} A_{ij}\, h_j \;=\; \sum_{j \in \mathcal{N}(i)} h_j ,$$

왜냐하면 $A_{ij}$는 이웃에서만 정확히 $1$이고 그 외에는 $0$이기 때문입니다. $A$를 곱하는 것은 곧 "이웃들의 벡터를 합하라"는 것이며, 이것이 13개 노드 전부에 대해 단 한 번에 실행됩니다. 청사진의 집계가 선형대수가 된 것입니다. 그러나 이 있는 그대로의 연산자에는 두 가지 결함이 있으며, 이를 하나씩 고쳐 나가는 과정이 GCN을 만들어 냅니다.

계층 조립하기: 두 가지 결함, 두 가지 수선

결함 하나: $A$는 노드 자신을 지워 버립니다. 합 $\sum_{j \in \mathcal{N}(i)} h_j$는 이웃에 대해서만 돌아갑니다; $A_{ii} = 0$이므로 $h_i$는 자신의 갱신에 아무것도 기여하지 못합니다. 한 계층을 지나면 노드의 표현은 전적으로 다른 노드들의 특징으로부터 만들어지고, 자신의 입력 특징은 사라져 버립니다. 이에 대한 수선은 모든 노드에 자기 루프(self-loop)를 두는 것입니다: $A$를 $\tilde{A} = A + I$로 바꾸는데, 여기서 $I$는 단위 행렬(identity matrix, 대각선은 1이고 나머지는 0)입니다. 이제 $\tilde{A}_{ii} = 1$이고, $\tilde{A}H$의 행 $i$는 $h_i + \sum_{j \in \mathcal{N}(i)} h_j$가 되어, 모든 노드가 자신의 수용 영역 안에 계속 머무릅니다 [3].

결함 둘: 합이 차수에 비례해 커집니다. 모든 노드의 벡터가 대략 같은 길이 $c$를 갖는다고 합시다($\lVert h_j \rVert \approx c$라 쓰며, $\lVert \cdot \rVert$는 유클리드 노름, 즉 성분 제곱의 합의 제곱근입니다). 그러면 노드 $i$에 대한 집계된 행은 그런 벡터 $d_i + 1$개의 합이 되고, 항들이 체계적으로 상쇄되지 않는 한 그 길이는 대략 $(d_i + 1)\,c$ 정도가 됩니다. 구체적으로, 우리 그래프에서 bob(차수 5)은 6개 벡터의 합을 받는 반면 logic(차수 1)은 2개 벡터의 합을 받습니다: 한 계층을 지나면 bob의 활성값은 약 3배 커지고, 두 계층을 지나면 약 9배가 되며, 일반적으로 이 격차는 차수의 거듭제곱처럼 깊이에 대해 기하급수적으로 누적됩니다. 연결이 잘 되어 있다는 것 자체가 어떤 노드를 9배 더 중요하게 만들어야 할 이유는 없습니다; 그 크기는 그저 세는 방식이 낳은 인공물입니다. 더 나쁜 것은 이 폭주가 그래프 전체에 걸친다는 점입니다: $\tilde{A}$를 반복해서 곱하는 것은 행렬의 지배적인 고유벡터 방향을 따라 임의의 벡터를 가장 큰 고유값(eigenvalue, 어떤 0이 아닌 벡터 $v$가 $\tilde{A}v = \lambda v$를 만족시키는 수 $\lambda$; 행렬을 $T$번 적용하면 그 방향은 $\lambda^T$만큼 스케일됩니다)만큼 증폭시키고, 인접 행렬류의 행렬에서 그 최상위 고유값은 그래프의 연결도와 함께 커지므로, 깊은 스택은 밀집된 그래프에서는 폭주하고 희소한 그래프에서는 굶주립니다.

수선은 정규화(normalization)이며, 구체적으로 어떤 것을 고르느냐가 중요합니다. 각 항목을 양쪽 끝점의 차수로, 대칭적으로 나눕니다:

$$\hat{A} \;=\; D^{-1/2}\,\tilde{A}\,D^{-1/2}, \qquad\text{항목별로}\qquad \hat{A}_{ij} \;=\; \frac{\tilde{A}_{ij}}{\sqrt{d_i\, d_j}},$$

여기서 이제부터 $d_i$는 자기 루프를 포함한 차수(즉 $\tilde{A}$의 행 합)를 나타내며, $D^{-1/2}$는 $1/\sqrt{d_i}$를 나르는 대각 행렬입니다. 이제 각 엣지 $i \sim j$는 가중치 $1/\sqrt{d_i d_j}$를 지니게 됩니다: 메시지는 보내는 쪽의 인기도로 한 번, 받는 쪽의 인기도로 한 번, 두 번 할인됩니다. 이를 정당화하는 주장을 완전한 논증과 함께 제시합니다.

주장: $\hat{A}$의 모든 고유값 $\lambda$는 $-1 \lt \lambda \le 1$을 만족합니다. 먼저 $\hat{A}$를 행-정규화 보행 연산자(row-normalized walk operator) $P_{\mathrm{rw}} = D^{-1}\tilde{A}$와 비교합니다. 그 항목 $(P_{\mathrm{rw}})_{ij} = \tilde{A}_{ij}/d_i$는 받는 쪽의 차수로만 나누므로, $P_{\mathrm{rw}}$의 모든 행은 정확히 $1$로 합해집니다. 아래첨자 rw는 무작위 보행(random walk)을 줄인 것이며, 맨글자 $P$를 비워 두기 위해 붙였습니다. 뒤 절에서는 그 글자에 네트워크의 출력 확률 행렬과 정리 1의 순열 행렬이라는 두 가지 표준 역할을 더 맡기기 때문입니다. 이 둘은 닮은 행렬(similar matrices)입니다: $\hat{A} = D^{-1/2}\tilde{A}D^{-1/2} = D^{1/2}\,(D^{-1}\tilde{A})\,D^{-1/2} = D^{1/2} P_{\mathrm{rw}} D^{-1/2}$이며, 닮은 행렬은 동일한 고유값을 갖습니다(만약 $P_{\mathrm{rw}}v = \lambda v$라면 $\hat{A}(D^{1/2}v) = D^{1/2}P_{\mathrm{rw}}v = \lambda\,(D^{1/2}v)$이기 때문입니다). 그러므로 $P_{\mathrm{rw}}$의 고유값을 한정하는 것으로 충분합니다. 고유벡터 $v$를 갖는 $P_{\mathrm{rw}}$의 임의의 고유값 $\lambda$를 잡고, 항목 $v_i$의 절댓값(부호를 뗀 크기)인 $\lvert v_i \rvert$가 가장 큰 지점의 인덱스를 $i$라 합시다. $P_{\mathrm{rw}}v = \lambda v$의 행 $i$를 읽어 내고 대각 항을 분리하면:

$$\lambda\, v_i \;=\; \sum_{j} (P_{\mathrm{rw}})_{ij}\, v_j \;=\; (P_{\mathrm{rw}})_{ii}\, v_i + \sum_{j \ne i} (P_{\mathrm{rw}})_{ij}\, v_j .$$

대각 항을 반대편으로 옮기고, $\lvert v_j \rvert \le \lvert v_i \rvert$와 $P_{ij} \ge 0$을 사용해 나머지를 한정합니다:

$$\lvert \lambda - (P_{\mathrm{rw}})_{ii} \rvert \, \lvert v_i \rvert \;=\; \Big\lvert \sum_{j \ne i} (P_{\mathrm{rw}})_{ij}\, v_j \Big\rvert \;\le\; \sum_{j \ne i} (P_{\mathrm{rw}})_{ij}\, \lvert v_j \rvert \;\le\; \Big( \sum_{j \ne i} (P_{\mathrm{rw}})_{ij} \Big) \lvert v_i \rvert \;=\; \big(1 - (P_{\mathrm{rw}})_{ii}\big)\, \lvert v_i \rvert,$$

여기서 마지막 등식은 행 합 $\sum_j (P_{\mathrm{rw}})_{ij} = 1$을 사용합니다. $\lvert v_i \rvert \gt 0$로 나누면 $\lvert \lambda - (P_{\mathrm{rw}})_{ii} \rvert \le 1 - (P_{\mathrm{rw}})_{ii}$를 얻는데, 이는 $(P_{\mathrm{rw}})_{ii}$를 중심으로 반지름 $1 - (P_{\mathrm{rw}})_{ii}$인 구간, 즉 $2(P_{\mathrm{rw}})_{ii} - 1 \le \lambda \le 1$입니다(지금 다루는 실수 고유값에 대해; $\hat{A}$는 대칭이므로 모든 고유값이 실수입니다). 자기 루프는 대각선을 엄격히 양수로 만들므로 $(P_{\mathrm{rw}})_{ii} = 1/d_i \gt 0$이고, 따라서 왼쪽 끝은 $-1$보다 엄격히 위에 있습니다. 결론: $\lambda \in (-1, 1]$이며, $\lambda = 1$은 달성됩니다(모든 곳에서 $v_i = 1$인 $v$를 취하면, $P_{\mathrm{rw}}v$의 각 행은 $P_{\mathrm{rw}}$의 행을 합한 것인데 이는 $1$입니다). 그러므로 $\hat{A}$를 반복 적용해도 결코 증폭되지 않습니다: 최상위 고유벡터를 따르는 성분은 보존되고($1^T = 1$), 다른 모든 스펙트럼 성분은 줄어듭니다. (구간 하나만으로는 해결되지 않는 한 가지 유의점이 있습니다: 이는 고유값 $1$이 정확히 하나의 방향에서만 달성된다는 것을 필요로 하며, 이는 그래프가 연결되어 있을 때 성립하고, 우리 그래프는 실제로 연결되어 있습니다: 어느 노드에서 시작하든 너비 우선 탐색이 13개 노드 모두에 닿습니다. 연결되지 않은 그래프라면 각 연결 성분이 자기만의 성분 하나를 보존하게 됩니다.) 허브는 폭주할 수 없고, 깊은 스택은 폭발할 수 없으며, 이 연산자는 노드 13개짜리 그래프에서나 1,300만 개짜리 그래프에서나 똑같이 동작합니다.

스펙트럼을 공유하는데도 왜 $P_{\mathrm{rw}}$ 자신이 아니라 대칭 버전을 쓸까요? 두 가지 실질적인 이유가 있습니다. 첫째, $P_{\mathrm{rw}}$는 메시지를 받는 쪽의 차수로만 가중하므로, 허브가 내보내는 메시지는 허브 자신의 인기도에 대해서는 전혀 할인되지 않습니다; 대칭 가중치 $1/\sqrt{d_i d_j}$는 그 할인을 양쪽 끝점에 나눠, 허브로 들어오는 트래픽과 나가는 트래픽 모두를 감쇠시킵니다. 둘째, 그리고 이 장에서 결정적으로, $\hat{A}$는 대칭입니다($\hat{A}^\top = \hat{A}$), 그리고 바로 이 한 가지 사실이 아래 역전파 유도의 한 줄을 조용히 단순화해 줍니다. 짝이 되는 파일은 이 연산자를 세 줄로 만듭니다(gnn.py 68–81번째 줄, 독스트링 생략):

    a_tilde = a + np.eye(len(a))                 # A + I
    d = a_tilde.sum(axis=1)                      # degrees of A + I
    # Elementwise: Â[i, j] = Ã[i, j] / sqrt(d_i · d_j).
    return a_tilde / np.sqrt(np.outer(d, d))

그리고 계층 자체는, 공유 가중치 행렬과 ReLU 비선형 함수(rectified linear unit의 약자로, 함수 $\operatorname{ReLU}(z) = \max(z, 0)$를 각 항목에 개별적으로 적용합니다)와 함께, 한 줄짜리 청사진 $H' = \operatorname{ReLU}(\hat{A} H W)$입니다(gnn.py 149–152번째 줄):

    z1 = a_hat @ x @ w1
    h1 = np.maximum(z1, 0.0)                     # ReLU, applied elementwise
    z2 = a_hat @ h1 @ w2
    return z1, h1, z2, softmax(z2)

각 조각을 청사진에 맞춰 봅시다: $j$에서 $i$로 가는 메시지는 $\hat{A}_{ij} = 1/\sqrt{d_i d_j}$로 스케일된 $h_j$이고, 집계는 자기 루프를 포함해 행렬 곱이 수행하는 합이며, 갱신은 공유 선형 사상 $W$에 이어지는 ReLU입니다. 계층 2에는 내부 ReLU가 없다는 점에 주목하십시오: 그 출력 $Z_2$는 소프트맥스 분류 헤드로 곧바로 흘러들고, 소프트맥스 자체가 그 비선형 함수입니다(gnn.py 144–148번째 줄의 독스트링은 여기에 굳이 하나를 더한다면 무슨 일이 일어나는지를 기록합니다: 모든 로짓이 음이 아닌 값으로 잘려 나가고, 대부분의 기울기가 0으로 닫히며, 훈련은 9개 중 6개의 훈련 레이블에서 멈춰 버립니다). 실제 숫자로 이 연산자를 살펴봅시다: 커밋된 실행에서 나온, bob의 $\hat{A}$ 행입니다. bob의 승격된 차수는 $5 + 1 = 6$이므로 그의 자기 루프는 $1/6 \approx 0.1667$의 무게를 지니고; mit은 승격된 차수 3을 가지므로 그 엣지는 $1/\sqrt{6 \cdot 3} = 1/\sqrt{18} \approx 0.2357$의 무게를 지니며; carol과 p1(승격된 차수 5)은 각각 $1/\sqrt{30} \approx 0.1826$의 무게를 지닙니다.

  A_hat = D^-1/2 (A+I) D^-1/2; nonzeros of bob's row: alice 0.2041, bob 0.1667, carol 0.1826, dave 0.2041, mit 0.2357, p1 0.1826

네트워크가 구조를 읽게 만드는 특징

GNN에는 노드당 한 행씩인 입력 특징 행렬 $X$가 필요하며, 이 선택은 형식적인 절차가 아니라 과학적인 결정입니다. 뻔한 선택인 원-핫 항등 특징(identity feature, 행 $i$의 위치 $i$에 $1$이 있는 것)은 실험 전체를 망가뜨릴 것입니다: 이는 각 노드에 전용 입력 채널을 쥐여 주므로, 가중치 행렬은 레이블 붙은 노드마다 "채널 3은 학생을 의미한다" 같은 것을 그저 암기해 버릴 수 있고, 학습된 그 무엇도 그래프 구조에 대해서는 아무 말도 하지 못하게 됩니다. 짝이 되는 파일의 독스트링은 이 선택과 그 이유를 명시합니다(gnn.py 84–98번째 줄):

def build_features(a: np.ndarray) -> tuple[np.ndarray, list[int]]:
    """X = one-hot of node DEGREE (13 x 5: the degrees present are 1..5).

    Structural features only, no identity features: a one-hot *node id* would
    hand each labelled node a private input channel, the weights would simply
    memorize the 9 training labels, and nothing learned would transfer to the
    held-out nodes.  Degree forces the model to generalize from structure
    alone (nodes of equal degree start indistinguishable and are separated
    only by their neighbourhoods)."""

그래서 $X$는 $13 \times 5$입니다: 이 그래프에 존재하는 차수는 $1, 2, 3, 4, 5$이며, 각 노드의 특징은 자신의 차수를 나타내는 원-핫 지시자입니다. 차수가 3인 모든 노드(alice, cmu, dave, p3: 교수, 기관, 학생, 논문 하나씩)는 동일한 입력 벡터로 시작합니다. 네트워크가 이들을 조금이라도 구분한다면, 그것은 오직 메시지 전달이 그들의 이웃 구조를 섞어 넣었기 때문일 수밖에 없습니다.

이 과제는 준지도 노드 분류(semi-supervised node classification)입니다 [3]: 모든 노드의 벡터가 계산되지만, 훈련 손실은 13개 중 오직 9개 노드의 레이블만을 읽습니다. 나머지 넷은 모호한 유형마다 하나씩이며(gnn.py 48번째 줄: HELD_OUT = ["bob", "dave", "p2", "cmu"]), 훈련 중에는 결코 레이블이 붙지 않습니다; 그럼에도 네트워크는 순전파를 할 때마다 이들에 대해서도 출력을 계산하는데, 이들이 같은 그래프 안에 앉아 있고 그 특징이 $\hat{A}$를 통해 다른 모든 노드로 흘러들기 때문입니다. 이들을 올바르게 예측하는 것이 곧 일반화의 시험대입니다. 커밋된 설정 줄입니다:

  split     : 9 labelled nodes for training; held out: bob (Professor), dave (Student), p2 (Paper), cmu (Institution)

스택을 통한 역전파, 완전히 유도하기

순전파는 세 개의 방정식입니다. $W_1 \in \mathbb{R}^{5 \times 16}$(입력 폭 5, 은닉 폭 16, gnn.py 50번째 줄에서 설정)와 $W_2 \in \mathbb{R}^{16 \times 5}$(은닉 폭에서 $C = 5$개 클래스로)를 두면:

$$Z_1 = \hat{A} X W_1, \qquad H_1 = \operatorname{ReLU}(Z_1), \qquad Z_2 = \hat{A} H_1 W_2, \qquad P = \operatorname{softmax}(Z_2),$$

여기서 소프트맥스(softmax)는 로짓의 각 행 $z = (z_1, \ldots, z_C)$를 확률 분포로 바꾸는데, $p_k = e^{z_k} / \sum_{j=1}^{C} e^{z_j}$입니다(각 항목은 양수이고, 행의 합은 1입니다). 손실은 마스크된 교차 엔트로피(masked cross-entropy)입니다: 레이블 붙은 노드가 $m = 9$개이고 $y_i$가 노드 $i$의 참 클래스 인덱스일 때,

$$L \;=\; -\frac{1}{m} \sum_{i \,\in\, \text{labeled}} \ln p_{i, y_i},$$

즉 네트워크가 정답에 부여하는 음의 로그 확률의 평균입니다(gnn.py 160–163번째 줄). 훈련은 완전 배치 경사 하강법으로, $W \leftarrow W - \eta\, \partial L/\partial W$입니다: 여기서 $\partial L/\partial W$는 가중치 행렬 $W$의 각 항목에 대한 손실의 편미분들로 이루어진 행렬이고(기호 $\partial$는 다른 모든 변수를 고정한 채 취한 미분을 나타냅니다), $\eta$는 학습률(learning rate), 즉 각 갱신의 보폭으로, $0.5$로 설정됩니다(아래 추적의 lr=0.5이며, gnn.py 51번째 줄). 그러므로 모든 것은 두 개의 기울기 행렬을 계산하는 문제로 환원됩니다. 경사 하강법이 단일 뉴런에 대해 그랬던 것과 정확히 똑같이 손실로부터 거꾸로 거슬러 올라가며, 첫 단계는 그 장의 기적을 소프트맥스 형태로 재현합니다.

1단계: $p - y$ 규칙. 레이블 붙은 노드 하나를 고정하고 노드 인덱스를 생략합니다; $c$를 그 참 클래스, $y$를 원-핫 목표($y_c = 1$, 다른 모든 $y_k = 0$), $z$를 그 로짓 행이라 합시다. 소프트맥스를 손실에 대입하고 미분하기 전에 단순화합니다:

$$\ell \;=\; -\ln p_c \;=\; -\ln \frac{e^{z_c}}{\sum_{j} e^{z_j}} \;=\; -z_c + \ln \sum_{j} e^{z_j},$$

여기서 $\ln(a/b) = \ln a - \ln b$와 $\ln e^{z_c} = z_c$를 사용합니다. 이제 임의의 로짓 $z_k$에 대해 미분합니다. 첫째 항은 $k = c$이면 $-1$을, 그 외에는 $0$을 기여하는데, 이는 정확히 $-y_k$입니다. 둘째 항에 대해서는, $\ln(\cdot)$에 대한 연쇄 법칙이 인자의 역수에 그 인자의 도함수를 곱한 것을 주며; $j = k$인 항만이 $z_k$에 의존하고 그 도함수는 $e^{z_k}$입니다:

$$\frac{\partial \ell}{\partial z_k} \;=\; -y_k + \frac{1}{\sum_{j} e^{z_j}} \cdot e^{z_k} \;=\; -y_k + p_k \;=\; p_k - y_k .$$

껄끄러운 정규화 상수가 미분되어 정확히 소프트맥스 자신이 되었고, 오차 신호는 확률 빼기 목표로 무너지는데, 이는 1권에서 유도된 시그모이드 결과의 다중 클래스 버전입니다. 이를 노드들에 대해 쌓고, 레이블 붙은 $m$개에 대해 평균 내고, 마스크로 레이블 없는 행을 0으로 만들면 다음 행렬을 얻습니다.

$$\Delta_2 \;=\; \frac{\partial L}{\partial Z_2} \;=\; \frac{1}{m}\,\operatorname{mask} \odot (P - Y),$$

여기서 $Y$는 원-핫 레이블 행렬이고 $\odot$는 항목별(여기서는 행 단위) 곱셈을 나타냅니다. 이것이 gnn.py 190번째 줄입니다: delta2 = (p - y_onehot) * train_mask[:, None] / m.

2단계: 전치, 유도하기. 로짓은 집계된 은닉 상태의 선형 사상입니다: $Z_2 = M W_2$이고 $M = \hat{A} H_1$입니다. 우리는 $\partial L/\partial W_2$가 필요하며, 깔끔한 방법은 스칼라 항목 하나를 미분하는 것입니다. 곱의 항목 $(i, k)$는 $(Z_2)_{ik} = \sum_{c} M_{ic}\, (W_2)_{ck}$이므로, $(Z_2)_{ik}$를 특정 가중치 $(W_2)_{ab}$에 대해 미분하면 $k = b$일 때(유일한 항 $c = a$가 살아남습니다) $M_{ia}$가 되고, $k \ne b$일 때는(그 가중치를 담은 항이 없으므로) $0$이 됩니다. $(W_2)_{ab}$에서 손실까지 가는 모든 경로에 대해 연쇄 법칙을 합하면:

$$\frac{\partial L}{\partial (W_2)_{ab}} \;=\; \sum_{i, k} \frac{\partial L}{\partial (Z_2)_{ik}} \frac{\partial (Z_2)_{ik}}{\partial (W_2)_{ab}} \;=\; \sum_{i} (\Delta_2)_{ib}\, M_{ia} \;=\; \sum_{i} (M^\top)_{ai}\, (\Delta_2)_{ib} \;=\; \big(M^\top \Delta_2\big)_{ab} .$$

전치는 관례가 아니라 인덱스 회계가 만들어 낸 결과입니다: 합은 $M$과 $\Delta_2$ 둘 다의 행 인덱스인 노드 인덱스 $i$에 대해 돌아가며, 두 행렬을 공유된 행 인덱스를 따라 축약하는 것은 정의상 $M^\top \Delta_2$입니다. 따라서

$$\frac{\partial L}{\partial W_2} \;=\; (\hat{A} H_1)^\top\, \Delta_2 ,$$

이는 gnn.py 194번째 줄입니다: grad_w2 = (a_hat @ h1).T @ delta2.

3단계: 집계를 거슬러 되돌아가기. 이제 $Z_2 = \hat{A} H_1 W_2$를 세 행렬 곱의 가운데 인자인 $H_1$의 함수로 봅시다. 이는 2단계와는 진짜로 다른 장부 문제입니다. 가운데 인자가 양쪽에서 동시에 축약되기 때문입니다. 로짓의 항목 $(i,k)$는 $(Z_2)_{ik} = \sum_v \sum_c \hat{A}_{iv}\,(H_1)_{vc}\,(W_2)_{ck}$이며, 노드 인덱스 $v$와 은닉 인덱스 $c$에 대해 합합니다. 은닉 항목 하나 $(H_1)_{ab}$에 대해 미분하면 $v=a$, $c=b$인 항을 제외한 모든 항이 사라져 $\partial (Z_2)_{ik}/\partial(H_1)_{ab}=\hat{A}_{ia}(W_2)_{bk}$가 남고, 연쇄 법칙은 모든 로짓 항목에 대해 합합니다:

$$\frac{\partial L}{\partial (H_1)_{ab}} \;=\; \sum_{i, k} (\Delta_2)_{ik}\, \hat{A}_{ia}\, (W_2)_{bk} \;=\; \sum_{i} (\hat{A}^\top)_{ai} \sum_{k} (\Delta_2)_{ik}\, (W_2^\top)_{kb} \;=\; \big(\hat{A}^\top \Delta_2 W_2^\top\big)_{ab} .$$

이번에는 한 번이 아니라 두 번 축약됩니다: 노드 인덱스 $i$에 대해서는 $\hat{A}$를 거쳐 왼쪽 전치를 만들고, 클래스 인덱스 $k$에 대해서는 $W_2$를 거쳐 오른쪽 전치를 만듭니다. 따라서 $\partial L/\partial H_1 = \hat{A}^\top \Delta_2 W_2^\top$입니다. 여기서 대칭 정규화가 두 번째 배당을 지불합니다: $\hat{A}^\top = \hat{A}$이므로, 역방향 패스는 순방향 연산자를 그대로 재사용합니다(gnn.py 196–197번째 줄). 활성값과 마찬가지로 기울기도 그래프의 엣지를 따라 흐릅니다: 레이블 붙은 노드의 오차 신호는 같은 차수 가중 배선을 통해 이웃의 은닉 상태로 전파됩니다.

4단계: ReLU 게이트. $H_1 = \max(Z_1, 0)$이 항목별로 적용되므로, $H_1$의 각 항목은 $Z_1 \gt 0$인 곳에서는 자신의 $Z_1$ 항목에 대해 도함수 $1$을 가지고, $Z_1 \lt 0$인 곳에서는 $0$을 가집니다(그 함수는 0의 왼쪽에서 평평합니다). 정확히 $Z_1 = 0$인 지점에서는 두 기울기가 일치하지 않아 도함수가 존재하지 않습니다; 구현체는 그곳에서 $0$을 취하는 표준 관례를 채택하며, 이는 (z1 > 0.0)의 엄격한 부등호로 인코딩됩니다. 연쇄 법칙은 들어오는 기울기에 이 지시함수를 곱합니다: $\partial L/\partial Z_1 = (\partial L/\partial H_1) \odot \mathbf{1}[Z_1 \gt 0]$, 이는 gnn.py 201번째 줄입니다: d_z1 = d_h1 * (z1 > 0.0). 기울기는 활성화된 유닛은 손대지 않고 통과하고 비활성화된 유닛에서는 죽습니다.

5단계: 첫 번째 가중치. $Z_1 = (\hat{A} X) W_1$는 $M = \hat{A}X$이고 $\Delta_1 = \partial L/\partial Z_1$인 2단계와 정확히 같은 형태를 가지므로, $\partial L/\partial W_1 = (\hat{A} X)^\top \Delta_1$이고(gnn.py 204번째 줄), 갱신 $W \leftarrow W - \eta\, \nabla_W L$이 순환을 닫습니다(gnn.py 207–208번째 줄); 기호 $\nabla_W L$("나블라"라고 읽습니다)은 $W$에 대한 기울기로, 같은 편미분 행렬 $\partial L/\partial W$를 더 간결한 표기법으로 쓴 것입니다. 다섯 단계, 두 개의 기울기 행렬, 자동 미분 없음. 파일을 실행하면(시드 0, 400 에폭) 커밋된 추적이 출력됩니다:

training: full-batch GD, lr=0.5, hidden width 16, 400 epochs, seed 0
  untrained loss = 1.5950  (uniform guessing over 5 classes would give ln 5 = 1.6094)
  epoch    loss   train-acc
      1  1.5690   0.3333
     50  0.8099   0.7778
    100  0.4853   1.0000
    200  0.2211   1.0000
    400  0.0845   1.0000

첫 줄은 정합성 확인용 기준점으로 읽으십시오: 훈련되지 않은 네트워크는 아무것도 몰라야 하며, $C = 5$개 클래스에 대한 균등한 추측은 정답에 확률 $1/5$를 부여해 손실 $-\ln(1/5) = \ln 5 \approx 1.6094$가 되는데, 무작위 초기화는 $1.5950$에 도달해 사실상 그 지점에 있습니다. 이 추적은 이후 단조롭게 떨어지고, 100 에폭 무렵 완전한 훈련 정확도를 넘어서며, $0.0845$에 안착합니다:

에폭	손실 $L$	훈련 정확도
0 (훈련 전)	1.5950	—
1	1.5690	3/9 = 0.3333
50	0.8099	7/9 = 0.7778
100	0.4853	9/9 = 1.0000
200	0.2211	9/9 = 1.0000
400	0.0845	9/9 = 1.0000

9개의 레이블을 맞추는 것은 그 자체로는 대단한 성취가 아닙니다; 충분히 큰 네트워크는 무엇이든 맞출 수 있습니다. 진짜 성취는, 그리고 이 장치를 신뢰할 이유는, 같은 훈련된 네트워크가 다음에 무엇을 하느냐입니다: 두 개의 구조적 정리를 통과한 다음, 레이블 붙은 것을 한 번도 본 적 없는 노드들로 일반화합니다.

정리 1: 순열 등변성, 반올림 오차까지 정확하게

노드 인덱스는 회계 처리에 불과합니다. alice가 행렬의 행 0이든 행 11이든은 저장 방식의 결정일 뿐이며, 그래프에 대한 함수는 이를 신경 써서는 안 됩니다. 형식적인 진술은 순열 행렬(permutation matrix) $P$를 사용합니다: 13개 인덱스의 재배열 $\pi$를 하나 고르고, $P$가 위치 $(i, \pi(i))$에 $1$을 두고 나머지는 0이 되게 하면, $PX$의 행 $i$는 $X$의 행 $\pi(i)$가 되고($\pi$에 의해 뒤섞인 행들), $PAP^\top$는 $A$의 행과 열을 모두 뒤섞어 같은 그래프를 다시 레이블링합니다. (문자 표기에 주의하십시오. 이 절 전체에서 $P$는 동반 코드의 실험 출력과 맞춘 이 순열 행렬입니다. 훈련 절의 확률 행렬 $P = \operatorname{softmax}(Z_2)$나 고유값 논증의 보행 연산자 $P_{\mathrm{rw}}$와는 관계가 없습니다.) 훈련된 네트워크 전체의 출력 행렬을 $f(A, X)$라 쓰면, 이 성질은 등변성(equivariance)입니다(불변성이 아닙니다: 출력은 노드별 행렬이므로, 고정되어 있기보다는 입력을 따라 뒤섞여야 합니다):

$$f(P A P^\top,\, P X) \;=\; P\, f(A, X).$$

증명은 각각 한 줄짜리인 세 관찰의 연쇄입니다. 첫째, 정규화는 재레이블링과 교환됩니다: 승격된 행렬은 $PAP^\top + I = P(A + I)P^\top$입니다($PIP^\top = PP^\top = I$이기 때문입니다; 순열 행렬의 역은 그 전치입니다). 그 차수 벡터는 옛것을 뒤섞은 것이므로(행 합은 열 치환 아래에서 보존됩니다) $D' = PDP^\top$입니다; 그리고 대각 행렬을 순열로 켤레 변환하는 것은 단지 그 대각 항목들을 재배열할 뿐이므로, 항목별 역제곱근을 취하는 것은 그 재배열과 교환됩니다, $(PDP^\top)^{-1/2} = P D^{-1/2} P^\top$. 따라서

$$\hat{A}' \;=\; (PDP^\top)^{-1/2}\, P(A+I)P^\top\, (PDP^\top)^{-1/2} \;=\; P D^{-1/2} \underbrace{P^\top P}_{I} (A+I) \underbrace{P^\top P}_{I} D^{-1/2} P^\top \;=\; P \hat{A} P^\top .$$

둘째, 선형 계층이 교환됩니다: $\hat{A}'\,(PX)\,W_1 = P\hat{A}P^\top P X W_1 = P\,(\hat{A}XW_1) = PZ_1$이며, 다시 $P^\top P = I$를 사용합니다; 결정적인 구조적 사실은 $W_1$이 노드들에 걸쳐 공유되어 특징 쪽에서 곱해지므로 노드 인덱스에는 결코 손대지 않는다는 것입니다. 셋째, ReLU는 항목별로 작동하고 소프트맥스는 행 단위로 작동하므로, 둘 다 어떤 행 뒤섞기와도 교환됩니다. 계층 2를 거쳐 이를 합성하면, 치환된 실행의 모든 중간값은 원래 실행을 $P$로 뒤섞은 것이 되고, 주장이 따라 나옵니다. 노드를 개별적으로 인덱싱하는 어떤 아키텍처도(노드별 편향, 항등 특징) 이 논증에서 살아남지 못할 것이며, 이것이 바로 청사진이 그런 것들을 금지하는 이유입니다.

짝이 되는 파일은 논증에서 멈추지 않고, 이를 훈련된 네트워크 위에서 실행합니다(gnn.py 282–292번째 줄): 시드가 고정된 순열을 뽑고, 재레이블된 그래프로부터 $\hat{A}$를 다시 세우고, 같은 훈련된 가중치를 $(PAP^\top, PX)$ 위에서 다시 돌려, $P\,f(A, X)$와 비교합니다:

exhibit 1 — permutation equivariance: f(P A P^T, P X) = P f(A, X)
  seeded permutation P: [11, 9, 5, 6, 2, 7, 8, 1, 12, 4, 3, 10, 0]
  max |f(P A P^T, P X) - P f(A, X)| = 2.22e-16  (pure float round-off)

$13 \times 5$개 출력 확률 전체에 걸친 가장 큰 절대 불일치는 $2.22 \times 10^{-16}$인데, 이는 1에 가까운 배정도(double-precision) 수의 마지막 자릿수 하나에 해당하며, 이것이 부동소수점에서 "같은 덧셈들을 순서만 바꿔 더한 것과 같다"가 어떻게 보이는지입니다. 하니스는 이를 $10^{-9}$ 아래로 단언하며(gnn.py 319번째 줄), 여섯 자릿수 이상의 여유를 두고 통과합니다.

정리 2: 2홉 지역성, 비트 단위로 검증

두 번째 정리는 한 노드가 볼 수 있는 것을 한정합니다. 두 계층을 하나의 식으로 풀어 봅시다:

$$Z_2 \;=\; \hat{A}\, \operatorname{ReLU}\!\big(\hat{A} X W_1\big)\, W_2 .$$

노드 $u$의 출력 행을 바깥에서 안으로 읽어 봅시다. 바깥쪽 곱셈은 $(Z_2)_u = \sum_{v} \hat{A}_{uv} (H_1)_v W_2$를 주고, $\hat{A}_{uv} \ne 0$인 것은 오직 $v$가 $u$ 자신이거나 직접적인 이웃일 때뿐입니다: 한 홉입니다. 기여하는 각 은닉 행은 $(H_1)_v = \operatorname{ReLU}\big(\sum_{w} \hat{A}_{vw}\, X_w W_1\big)$이고, $\hat{A}_{vw} \ne 0$인 것은 오직 $w$가 $v$의 닫힌 이웃 안에 있을 때뿐입니다: 두 번째 홉입니다. ReLU와 소프트맥스는 한 행 안에서 작동하며 결코 행들을 섞지 않습니다. 그러므로 $u$에서의 출력은 정확히 $u$로부터 홉 거리가 최대 2인 입력 행 $X_w$들만의 함수이며, 그 외에는 아무것도 아닙니다. $T$개 계층짜리 GCN은 $T$홉 공을 봅니다; 이것이 그 수용 영역(receptive field)이며, 이는 경향이 아니라 정리입니다.

"그 외에는 아무것도 의존하지 않는다"라는 형태의 정리는 가장 강력한 시험을 요구합니다: "거의 변하지 않는다"가 아니라 "조금이라도 변하는가"입니다. 짝이 되는 파일은 logic과 erin 쌍을 골라, 너비 우선 탐색으로 이 둘이 4홉 떨어져 있음을 확인하고(logic의 유일한 이웃은 p1이고, 최단 경로는 logic–p1–p2–carol–erin로 이어집니다), erin의 모든 특징에 $10^6$을 더한 다음 훈련된 순전파를 다시 실행합니다(gnn.py 298–316번째 줄):

exhibit 2 — locality: a 2-layer GCN sees exactly 2 hops
  BFS distance logic <-> erin = 4 hops (more than 2)
  perturb X[erin] by +1e6 in every feature, rerun the trained forward pass:
  max |change in output(logic)|  = 0.0000000000   (bit-identical)
  max |change in output| over erin's neighbours ['carol', 'cmu'] = 0.9871

먼 노드의 출력은 정확히 $0.0$만큼만 움직이며, 하니스는 근사적인 가까움이 아니라 등식 diff_far == 0.0을 단언합니다(gnn.py 321번째 줄). 이 정확함은 잠시 곱씹어 볼 가치가 있습니다. 조밀한 행렬 곱은 logic의 출력을 계산하는 와중에도 erin의 교란된 행을 실제로 소비하지만, 오직 정확히 0인 $\hat{A}$ 계수로만 곱해집니다: logic의 닫힌 2홉 공 바깥에 있는 행은 가중치 $0.0$으로 그 내적에 들어가며, 부동소수점에서 $0.0$ 곱하기 유한한 값은 무엇이든 정확히 $0.0$입니다. 따라서 그 과정의 모든 부분합은 두 실행 모두에서 동일한 순서로 더해진 비트 단위로 동일한 항들로 이루어지며, 결정론적인 부동소수점 산술은 그 결과로 비트 단위로 동일한 출력을 만들어 냅니다. 한편 교란은 정리가 허용하는 곳에서는 실제로 영향을 미칩니다: erin의 직접 이웃인 carol과 cmu는 출력 확률이 최대 $0.9871$까지, 거의 완전히 뒤집힐 만큼 변하는 것을 봅니다. 수용 영역이라는 주장은 비트 단위로 만들어집니다: 공 안에서는 거의 모든 것이, 공 밖에서는 아무것도 변하지 않습니다.

유보된 노드에 대한 평결, 정직하게 읽기

이제 일반화 시험입니다. 훈련 중 레이블을 한 번도 본 적 없는 네 노드에 대한 훈련된 네트워크의 예측을, 커밋된 실행에서 가져오면 다음과 같습니다:

held-out predictions (never labelled during training):
  node   true          predicted     correct?
  bob    Professor     Professor     yes
  dave   Student       Student       yes
  p2     Paper         Paper         yes
  cmu    Institution   Student       NO
  held-out accuracy: 3/4 = 0.7500   (train accuracy 1.0000)

노드	참 유형	예측	정답 여부
bob	교수	교수	yes
dave	학생	학생	yes
p2	논문	논문	yes
cmu	기관	학생	no

4개 중 3개이며, 차수 개수 말고는 아무것도 인코딩하지 않는 특징으로부터 나온 결과입니다. 네트워크가 극복해야 했던 것을 되새겨 봅시다: dave는 alice(교수), cmu(기관), p3(논문)와 동일한 입력 벡터로 시작하는데, 모두 차수 3이기 때문입니다; 이들을 갈라놓은 무언가는 전적으로 두 라운드의 $\hat{A}$에 의해, 즉 그들 이웃과 이웃의 이웃의 차수 프로필로부터 조립된 것입니다. 이것이 바로 구조만으로 예측을 실어 나른다는 것이며, 이는 정확히 이 특징 선택이 만들어 내려던 요점입니다.

오류는 성공만큼이나 시사하는 바가 큽니다. 레이블 붙은 유일한 기관은 mit입니다: 두 이웃(alice, bob)이 각각 차수 3과 5를 갖는 차수 2짜리 노드입니다. 이것이 훈련 시점에 이용 가능한 "기관"에 대한 구조적 정의의 전부입니다. 하지만 cmu는 다른 프로필을 보입니다: 차수 3에, 차수 4, 3, 2를 갖는 이웃 carol, dave, erin을 두고 있어, 잘 연결된 학생 군집의 구성원과 정확히 같은 프로필입니다; 실제로 이는 구조적으로 dave(차수 3, 차수 5, 3, 3의 이웃들)와 가깝습니다. 차수만으로 이루어진 특징은 네트워크에게 mit과 cmu를 하나로 묶어 주는 것이 ~에 소속되어 있음이라는 사실을 알 방법을 주지 않는데, 훈련이 시작되기도 전에 연산자 $\hat{A}$가 엣지 레이블 affiliated를 지워 버렸기 때문입니다. 예시가 하나뿐이고 관계 유형도 없는 상태에서, 네트워크는 cmu를 자신이 배선상 연결된 학생들과 함께 분류했으며, 이는 자신이 볼 수 있도록 허락된 증거로부터 나온 합리적인 추론입니다. 이 그래프에서 차수만으로 이루어진 특징은 이웃의 차수 프로필이 2홉 안에서 서로 다른 클래스는 분리할 수 있지만(논문은 저자와 주제에 매달려 있고, 교수는 지도 부채꼴의 꼭대기에 앉아 있습니다), 소속이 어떤 종류의 엣지가 도착하느냐로 정의되는 클래스는 분리할 수 없으며, 기관이 바로 그런 클래스입니다. 하니스는 4개 중 3개라는 결과를 그대로 받아들이며(gnn.py 324번째 줄), 이 실패를 조정해서 없애 버리는 대신 기록해 둡니다.

아직 풀리지 않은 부분

cmu의 실패는 이 작은 그래프의 우연이 아닙니다; 이는 바로 첫 번째 코드 블록에서 내려진 결정이 눈에 보이는 형태로 드러난 증상입니다. build_adjacency는 모든 트리플에 대해 a[i, j] = a[j, i] = 1.0을 쓰며, 바로 그 순간 지도하다(advises), 저술하다(authored), 인용하다(cites), 소속되다(affiliated), 에 관하다(about)는 모두 같은 전선이 됩니다. 그러면 연산자 $\hat{A}$는 오직 차수에만 의존하고 엣지가 무엇을 의미하는지에는 결코 의존하지 않는 가중치로 모든 메시지를 전파합니다. 하지만 학계 그래프가 지식 그래프인 이유는 정확히 그 엣지들이 서로 다른 것을 의미하기 때문입니다: advises 엣지는 사람과 지위에 대한 증거이고, cites 엣지는 논문과 계보에 대한 증거이며, affiliated 엣지는 기관에 대한 정의적인 증거입니다. 이들을 뭉개 버리는 것은 학습이 시작되기도 전에 그 의미를 내던지는 일이며, 아무리 훈련을 해도 입력 표현이 파괴한 정보를 되찾을 수는 없습니다.

이 부(Part)가 계속 맴돌게 될 이 질문에는 더 깊은 버전이 있습니다. 메시지 전달은 국소적인 구조적 요약으로 계산을 수행하며, 표현력의 천장에서 우리는 그 판별력이 정확히 바이스파일러-레만(Weisfeiler-Leman) 색 정제 검사에 의해 한정된다는 것을 보게 될 것입니다: 이웃-차수 전개가 일치하는 두 노드는, 구조적 특징을 지닌 GCN에게는 같은 노드입니다. 진짜로 열려 있는 물음은 그 천장이 존재하느냐가 아니라(그것은 정리입니다) 추론(reasoning)이 그 아래에 얼마나 들어맞느냐입니다: 2권의 EL++ 완성과 같은 기호 시스템의 어떤 함의들이 유계 깊이의, 순열 불변인 메시지 전달자로 계산될 수 있고, 어떤 것들이 국소적으로는 영원히 닿을 수 없는가 하는 것입니다. 다음 장은 그 첫 번째 구체적인 걸음을 내딛습니다: 전선을 뭉개는 일을 멈추는 것입니다.

왜 중요한가

이 권에게 있어 이 청사진은 두 번째의 위대한 표현 방식의 이동입니다. 이 장 이전의 모든 모델은 그래프를 기하 공간에 임베딩하고 트리플을 점별로 채점했습니다; 이 장은 그래프 자체를 계산으로 만들었고, 그 계산이 그래프에 대한 함수라면 반드시 지녀야 하는 두 성질, 즉 노드 순서에 대한 무관심과 실제 연결 구조에 대한 의존을 존중한다는 것을 증명했습니다. 그 증명들, 하나는 대수적으로 $2.22 \times 10^{-16}$까지 확인되었고 다른 하나는 구조적으로 비트 단위로 확인된 이 증명들은, 이 시리즈가 신경 계열의 주장에 대해 견지하는 기준의 작은 모형입니다: 성질이란 구호가 아니라 검증할 수 있는 방정식이라는 기준입니다.

앞으로 나아갈 신경-기호적 여정을 위해, 하나의 GCN 계층이 하는 일을 다시 보십시오: 그것은 노드별 단언들의 표를 쥐고 있다가, 그래프 이웃들의 항목들을 결합함으로써 각 항목을 반복적으로, 계층을 거듭하며 확장합니다. 2권의 완성 알고리즘도 똑같은 일을 했습니다: 원장 $S(A)$와 $R(r)$을 쥐고 있다가, 고정점에 도달할 때까지 역할 엣지를 따라 국소 규칙을 발동시켜 이들을 키워 나갔습니다. 메시지 전달은, 정확한 의미에서, 규칙 적용의 부드럽고 미분 가능한 사촌입니다: 포화 대신 유계 라운드, 집합 합집합 대신 가중합, 도출 대신 기울기입니다. 이 친연성이 바로 GNN이 기호 시스템에 가장 자주 접합되는 신경 쪽 반쪽인 이유이며, 그 표현력의 천장이 그토록 중요한 이유입니다: 그것이 이 부드러운 사촌이 흉내라도 낼 수 있는 규칙 같은 추론이 어디까지인지를 경계 짓기 때문입니다. 4권은 바로 그 간극 안에서 살아갑니다.

핵심 용어

• 메시지 전달(Message passing) — 계층 규칙 $h_i' = \operatorname{update}(h_i, \operatorname{aggregate}(\{\operatorname{message}(h_i, h_j) : j \in \mathcal{N}(i)\}))$이며, 이 부에 나오는 모든 GNN은 그 세 자리를 구체화한 것입니다.
• 순열 불변성 / 등변성(Permutation invariance / equivariance) — 불변성: 출력이 입력 순서를 무시함(이웃 다중집합에 대한 집계에 요구됨); 등변성: 출력이 입력과 함께 재배열됨, $f(PAP^\top, PX) = Pf(A, X)$(네트워크 전체가 이를 만족합니다).
• 인접 행렬 $A$ / 차수 행렬 $D$(Adjacency matrix / degree matrix) — 그래프를 0-1 표의 엣지로, 그리고 이웃 개수의 대각 행렬로 나타낸 것; $A$를 곱하는 것은 각 노드의 이웃 벡터들을 합하는 것입니다.
• 자기 루프(Self-loop, $+I$) — 노드 자신의 상태를 그 갱신 안에 붙들어 두는 더해진 대각선; 이것이 없으면 한 계층이 모든 노드의 자기 특징을 지워 버립니다.
• 대칭 정규화(Symmetric normalization) $\hat{A} = D^{-1/2}(A+I)D^{-1/2}$ — 각 엣지가 $1/\sqrt{d_i d_j}$로 가중됨; 모든 고유값은 $-1$보다 위, $1$ 이하의 구간에 놓이므로 반복 적용이 결코 증폭되지 않으며, $\hat{A}^\top = \hat{A}$가 역전파를 단순화합니다.
• 준지도 노드 분류(Semi-supervised node classification) — 같은 그래프 안에서 모든 노드의 표현이 계산되는 가운데 일부 노드의 레이블로만 훈련하는 것; 유보된 노드가 구조적 일반화를 시험합니다.
• $p - y$ 규칙(The $p - y$ rule) — 소프트맥스를 거친 교차 엔트로피의 기울기가 확률 빼기 원-핫 목표로 무너지는 것, $\partial \ell/\partial z_k = p_k - y_k$.
• 수용 영역(Receptive field) — $T$계층짜리 GNN의 출력이 증명 가능하게 의존하는, 그리고 그 외에는 아무것도 의존하지 않는 $T$홉 공; 여기서는 비트 단위로 검증되었습니다.

이 장이 이끄는 곳

이 장의 하나뿐인 실패는 이 장의 하나뿐인 단순화를 가리키고 있었습니다: 그래프에는 다섯 종류의 엣지가 있는데 $\hat{A}$에는 전선이 하나뿐입니다. 그 수선은 진단만큼이나 곧바릅니다. 각 관계 $r$에 자신만의 가중치 행렬 $W_r$을 부여하고, 메시지를 관계별로 합한 다음 관계들에 걸쳐 다시 합하면, 갱신은 $h_i' = \sigma\big(W_0 h_i + \sum_r \sum_{j \in \mathcal{N}_r(i)} \frac{1}{c_{i,r}} W_r h_j\big)$가 되는데, 여기서 $\sigma$는 항목별로 적용되는 비선형 함수(다음 장의 구현에서는 ReLU입니다)이고, $\mathcal{N}_r(i)$는 관계 $r$만을 따르는 $i$의 이웃이며, $c_{i,r}$은 관계별 정규화 개수입니다: 이것이 관계형 GCN이며, 여기서는 마침내 지도하다와 인용하다가 서로 다른 전선을 타고, affiliated 엣지가 어떤 인용도 의미할 수 없는 무언가를 의미할 수 있게 됩니다. 그 수선이 cmu를 구해 내는지, 파라미터 면에서 무엇을 대가로 치르는지, 그리고 어떤 새로운 실패를 드러내는지는 다음 장 관계형 GNN의 몫입니다.

---

짝이 되는 코드: examples/neural/gnn.py는 이 장의 모든 내용을 NumPy만으로 구현합니다: 인접 행렬과 연산자 $\hat{A}$(56–81번째 줄), 차수 특징(84–98번째 줄), 2계층 순전파(136–152번째 줄), 손으로 유도한 역전파(184–208번째 줄), 그리고 역량 단언을 포함한 두 개의 전시물(279–324번째 줄). 위에서 인용한 모든 숫자를 재현하려면 examples/neural/에서 python3 gnn.py를 실행하십시오; 스위트 하니스 examples/neural/validate.py는 이 권의 인수 판정의 일부로 같은 검사를 실행합니다.