표현력의 천장: 1-WL, C², 등급 양상 논리

📍 현재 위치: 4부 · 그래프 신경망과 그 한계 — 14장. 관계형 GNN은 관계마다 고유한 가중치 행렬을 부여해 애블레이션에서 4분의 4승리를 거뒀습니다; 이 장은 유형화되었든 아니든, 얕든 깊든, 어떤 메시지 전달 신경망이라도 도대체 무엇을 구별할 수 있는지를 묻고, 정확히 답합니다.

앞의 두 장은 하나의 골격 위에서 점점 더 유능한 기계를 지었습니다: 노드는 자신의 현재 상태와 이웃들의 상태로부터, 층을 거듭하며 자신의 상태를 갱신합니다. 이 장은 그 골격을 조율하는 일을 멈추고 그 경계를 증명합니다. 고전적인 조합론적 절차인 1차원 바이스파일러-레만 색 정제(1-WL, 색 정제라고도 불립니다)는 그래프의 노드들을 반복적으로 색칠하며, 4부의 핵심에 놓인 정리는 이것입니다: 아무리 넓고 깊고 영리하게 매개변수화되었더라도 어떤 메시지 전달 신경망도 1-WL이 동일하게 색칠하는 두 노드나 두 그래프를 구별할 수 없습니다 [1][2]. 이 경계는 전설이 아닙니다. 여섯 개 노드짜리 그래프로도 부딪힐 만큼 낮으며, 동반 파일 examples/neural/wl.py가 실제로 그 경계에 부딪힙니다. 더 좋은 것은, 이 경계가 하나의 논리라는 사실입니다: 1-WL이 분리하지 못하는 노드들은 정확히 2변수 계수 논리 C²의 모든 논리식에 동의하는 노드들이고 [3], 평범한 메시지 전달 신경망이 표현할 수 있는 논리적(1차 논리로 표현 가능한) 노드 분류기는 정확히 등급 양상 논리의 것들입니다 [4]. 2권에서 온 독자에게는 그 마지막 사실이 이 장의 보상입니다: "GNN이 이 온톨로지 조건을 검사할 수 있는가?"라는 질문을 견해의 문제에서 조견표 조회로 바꿔 놓기 때문입니다.

쉽게 말하면

아무도 이름을 갖지 않은 두 마을의 인구조사를 상상해 보세요. 모든 사람이 같은 빈 명찰로 시작합니다. 매 라운드마다 각 사람은 카드 한 장을 작성합니다: "내 현재 명찰, 그리고 내 이웃들의 현재 명찰 집계"이고, 인구조사청은 동일한 카드가 동일한 명찰을 받고 다른 카드는 다른 명찰을 받도록 새 명찰을 인쇄합니다. 명찰이 더 이상 바뀌지 않을 때까지 라운드가 반복됩니다. 이제 핵심입니다: 한 마을의 우정은 세 사람짜리 삼각형 두 개로 나뉘어 있고, 다른 마을의 우정은 여섯 사람짜리 고리 하나로 이루어져 있습니다. 이 두 마을은 분명히 다르지만, 두 마을 모두에서 모든 사람이 정확히 두 명의 친구를 가지고 있으므로, 모든 카드는 영원히 "빈 명찰, 빈 명찰을 가진 친구 둘"이라고 적히고, 인구조사는 양쪽 마을 모두에서 모두가 동일한 채로 끝납니다. 명찰을 읽어서 답하는 어떤 질문이든 두 마을에서 같은 답이 나옵니다. 메시지 전달 신경망은 명찰 판독기입니다: 노드는 이웃의 현재 요약이 무엇을 말하는지만 배울 뿐, 이웃이 실제로 누구인지는 결코 배우지 못합니다. 그래서 인구조사가 볼 수 없는 것은 어떤 GNN도 볼 수 없습니다.

이 장에서 다루는 내용

• 정제 알고리즘, 해독한 다음 인용: 색은 균일하게 시작하고, 각 라운드는 (자신의 색, 이웃 색들의 정렬된 다중집합)을 해시하며, 아무것도 나누지 않는 라운드가 고정점을 증명합니다. wl.py의 실제 루프입니다.
• 학계 그래프, 완전히 풀린 모습: 커밋된 라운드별 색 개수 1 → 5 → 12 → 13, 각 라운드에서 어떤 개체가 계속 묶여 있는지와 그 이유, 그리고 모든 개체가 구조적으로 이름 붙는 결말.
• 고전적 실패, 서술이 아니라 실행: 서로 떨어진 삼각형 두 개 대 육각형 하나: 증명 가능하게 비동형(삼각형 2개 대 0개)이지만 커밋된 히스토그램은 동일하므로, 어떤 메시지 전달 함수도 이들을 분리하지 못합니다.
• 천장이 성립하는 이유: 층에 대한 귀납법: 한 층은 정확히 1-WL 라운드가 해시하는 것을 보며, 집계의 단사성이 어디에 들어오고 무엇을 사 오는지.
• 천장 안의 단사성 경계: 합은 이웃 다중집합을 단사적으로 나타낼 수 있지만 평균과 최댓값은 그럴 수 없습니다. 네 개의 증거 다중집합에 대한 커밋된 합/평균/최댓값 표, 진법 전개 구성, 그리고 GIN 정리.
• 천장의 논리: 1-WL 구별 불가능성은 모든 C²에 대한 동의와 일치하며, 평범한 집계-결합 GNN의 1차 논리로 표현 가능한 분류기는 정확히 등급 양상 논리이고, 커밋된 클래스-불변성 검사.
• 천장을 통해 다시 읽는 2권: ∃r.C와 ≥n r.C는 천장 아래에 살고, 역할 합성은 세 번째 변수를 필요로 하며 천장 위에 살고, 부호화-후-점수화 모델을 위한 grandAdvisor 연쇄를 가라앉히는 구체적인 증거 쌍이 함께합니다.
• 천장을 넘는 방법들, 정직하게 값이 매겨진: k-WL 신경망, 고유 식별자, 그리고 부분그래프 또는 위치 인코딩, 각각의 비용과 함께.

정제 알고리즘: 아무것도 나뉘지 않을 때까지 이웃을 해시하라

먼저 대상들을 쉬운 말로 짚어 봅니다. 그래프의 색칠(coloring)은 각 노드에 유한 집합에서 뽑은 레이블 하나를 부여합니다. 여기서는 작은 정수를 사용하고, 라운드 $k$ 이후 노드 $v$가 지니는 색을 $c_k(v)$로 씁니다. 그래서 아래 첨자 $k$는 정제 라운드를 세고, $v$는 노드 전체를 범위로 합니다. 이웃(neighborhood) $N(v)$는 $v$에 인접한 노드들의 집합입니다. 다중집합(multiset)은 같은 원소가 여러 번 나타날 수 있고 오직 그 개수만이 중요할 뿐 순서는 중요하지 않은 모음입니다. 보통의 집합과 구별하기 위해 이중 중괄호 $\{\!\{ 1, 1, 2 \}\!\}$로 씁니다. 마지막으로, 서로 다른 입력이 항상 서로 다른 출력을 내서 아무것도 병합되지 않을 때 함수는 단사적(injective)이라고 합니다.

1-WL 색 정제는 그러면 세 문장으로 요약됩니다. 모든 노드를 같은 색으로 시작합니다: 모든 $v$에 대해 $c_0(v) = 0$입니다. 매 라운드마다 모든 노드는 자신의 서명(signature), 즉 자기 자신의 현재 색과 이웃들의 현재 색으로 이루어진 다중집합의 쌍을 계산하고, 단사적인 재레이블링이 서로 다른 서명 각각을 새로운 색으로 바꿉니다:

$$c_{k+1}(v) \;=\; \operatorname{relabel}\Big( c_k(v),\; \{\!\{\, c_k(u) : u \in N(v) \,\}\!\} \Big).$$

라운드가 아무것도 바꾸지 않을 때 멈춥니다. 즉 그 라운드 이후 노드들의 색 클래스로의 분할(partition)이 그 이전과 같아지는 때입니다. 두 가지 관찰이 이 루프를 다루기 쉽게 만듭니다. 정제는 오로지 클래스를 나눌 뿐 결코 합치지 않습니다: 라운드 $k$에서 서로 다르게 색칠된 노드들은 라운드 $k+1$에서 첫 번째 성분이 다른 서명을 가지므로 계속 다르게 남습니다. 그리고 노드가 $n$개인 그래프는 클래스를 최대 $n$개까지만 허용하므로 루프는 $n$라운드 이내에 멈춥니다. 아무것도 나누지 않는 라운드는 이후의 어떤 라운드도 아무것도 나눌 수 없음을 증명합니다. 왜냐하면 이후의 모든 서명은 변하지 않은 분할로부터 계산되기 때문입니다.

여기 커밋된 그대로의 루프가 있습니다, wl.py 104–119번째 줄입니다. 교과서적인 "단사 해시"는 그 라운드의 정렬된 서로 다른 서명들 사이에서 각 서명의 순위로 구현되며, 이는 구성상 단사적이고 표준적인 작은 정수를 내어 줍니다:

    colour: dict[str, int] = {v: 0 for v in g}       # round 0: everyone colour 0
    history: list[dict[str, int]] = [colour]
    while True:
        # The 1-WL update:  c_{k+1}(v) = relabel( c_k(v), {{ c_k(u) : u ∈ N(v) }} )
        # where {{...}} is the MULTISET of neighbour colours, here represented
        # as a sorted tuple.  ``relabel`` in the textbook formulation is an
        # injective hash; we use the rank of the signature among the round's
        # distinct signatures in sorted order — injective by construction, so
        # no hash collisions, and canonical small ints each round.
        sig = {v: (colour[v], tuple(sorted(colour[u] for u in g[v]))) for v in g}
        canon = {s: i for i, s in enumerate(sorted(set(sig.values())))}
        new = {v: canon[sig[v]] for v in g}
        history.append(new)
        if _partition(new) == _partition(colour):    # nothing split: fixpoint
            return history, len(history) - 1
        colour = new

이 절차가 볼 수 있도록 허용된 것이 무엇인지 주목하십시오. 이 절차는 그래프를 무향이고 레이블 없는 것으로 읽습니다: 관계 유형과 엣지 방향이야말로 색 정제가 버리는 정보이며, 동반 파일은 학계 예시의 1-WL 관점을 만들 때 이를 명시적으로 밝힙니다 (wl.py 66–74번째 줄):

def academic_graph() -> Graph:
    """The running example as 1-WL sees it: the 18 triples become 18 undirected,
    unlabelled edges over the 13 entities (relation types and directions are
    exactly the information colour refinement throws away)."""
    adj: dict[str, set[str]] = defaultdict(set)
    for h, _r, t in kg.TRIPLES:
        adj[h].add(t)
        adj[t].add(h)
    return {v: tuple(sorted(adj[v])) for v in sorted(adj)}

이것은 메시지 전달의 유형 없는 GCN(그래프 합성곱 신경망, graph convolutional network)을 위한 정직한 기준선입니다. 앞 장의 R-GCN(관계형 그래프 합성곱 신경망, relational graph convolutional network)에서처럼 유형화된 메시지 전달은 1-WL에 엣지 레이블을 심어 주는 것에 해당합니다. 이는 더 빠르게 정제되지만 아래의 이론에서는 아무것도 바뀌지 않으며, 관계마다 하나의 이웃 다중집합을 갖는 레이블 붙은 변형에 대해서도 그 이론은 문자 그대로 성립합니다 [2][5].

학계 그래프에서 라운드별로

python3 wl.py를 실행하면 증거 2가 학계 세계의 13개 개체와 18개의 무향 엣지 위에서 정제 과정을 추적합니다. 다음은 커밋된 출력입니다:

exhibit 2 — 1-WL on the academic graph (13 nodes, 18 edges)
  colours per round: 1 -> 5 -> 12 -> 13 -> 13 (stable: round 4 reproduces round 3)
  round 1 non-singleton classes: {logic, ml, nesy}  {erin, mit}  {alice, cmu, dave, p3}  {carol, p1, p2}
  round 2 non-singleton classes: {logic, nesy}
  round 1 is exactly the degree partition; round 2 still cannot
  split logic from nesy (each has one neighbour, a degree-4 paper);
  round 3 splits them because p1 and p2 got different colours.
  fixpoint: 13 colours for 13 nodes — entities sharing a colour: none
  (the discrete partition: 1-WL names every individual here,
   in contrast with exhibit 1)

이 추적을 해독해 봅시다. 라운드 0은 균일한 시작으로, 색이 하나입니다. 라운드 1에서 모든 노드의 서명은 $(0, \{\!\{0, \ldots, 0\}\!\})$이며 이웃 수만큼의 0을 가지므로, 유일하게 구별되는 특징은 몇 개의 이웃을 가지는가입니다: 라운드 1은 정확히 차수(degree, 한 노드에 걸린 엣지의 수)에 의한 분할입니다. 학계 그래프는 다섯 개의 서로 다른 차수를 가지므로 다섯 개의 클래스가 생깁니다:

차수	클래스에 속한 개체	정체
1	logic, ml, nesy	각각 논문 하나에 붙어 있는 세 개의 주제
2	erin, mit	관계가 둘인 학생; 구성원이 둘인 기관
3	alice, cmu, dave, p3	교수, 기관, 학생, 논문
4	carol, p1, p2	학생 하나와 연결이 풍부한 논문 둘
5	bob	허브: 지도교수이자 저자이자 동시에 재직자

차수-3 행은 눈여겨볼 만합니다: 한 라운드가 지난 뒤 네 가지 서로 다른 온톨로지 유형의 개체 넷이 색 하나를 공유하는데, 이는 정확히 앞 장에서 관계 유형화를 동기 부여했던 바로 그 상황입니다. 라운드 2는 거의 모든 것을 나눠서 5개 클래스가 12개가 되는데, 두 번째 라운드의 서명이 이웃의 차수를 보기 때문입니다. 나누지 못하는 유일한 클래스는 $\{$logic, nesy$\}$입니다: 각각은 차수 1의 주제이고 그 유일한 이웃은 차수 4의 논문(logic에는 p1, nesy에는 p2)이므로, 둘 다 라운드 2에 (라운드 1의 색으로 구성된) 같은 서명을 제시합니다: "차수 4 노드에 붙은 차수 1 노드." 라운드 3이 그 일을 마무리하지만, 이는 오직 논문들이 라운드 2에서 분리되었기 때문입니다: p1의 이웃은 alice, bob, logic, p2인 반면 p2의 이웃은 carol, nesy, p1, p3이어서 차수 구성이 서로 다른 이웃 관계이므로 $c_2(\mathrm{p1}) \neq c_2(\mathrm{p2})$이고, 라운드 3에서 주제들이 그 차이를 물려받습니다. 정보는 라운드마다 한 홉씩 전파되므로, 노드는 라운드 $k+1$에서 $k+1$홉 떨어진 구조에 의해 구별됩니다.

고정점은 이산 분할(discrete partition)입니다: 13개 노드에 13개 색이 있고, 구조적으로 구별 불가능한 두 개체는 없으며, 라운드 3에서 도달하고 라운드 4에서 증명됩니다(라운드 4는 라운드 3을 재현합니다; 요약 줄의 academic_rounds=4). 이 그래프에서는 1-WL이 구조만으로 모든 개체 각각의 이름을 붙입니다. 이 생각을 잠시 붙들어 두십시오. 다음 그래프에서는 아무것도 이름 붙이지 못하기 때문입니다.

실패 사례: 두 삼각형 대 육각형

증거 1은 cycle 생성자(wl.py 48–53번째 줄)를 사용해 각각 노드 여섯 개짜리 그래프 두 개를 만듭니다: $G_1$은 3-사이클 두 개의 서로소 합집합($2 \times C_3$, 노드 x0 x1 x2 y0 y1 y2)이고, $G_2$는 단일 6-사이클($C_6$, 노드 z0부터 z5까지)입니다. 이 그래프들은 증명 가능하게 비동형(non-isomorphic)입니다. 즉 어떤 노드 재레이블링으로도 하나를 다른 하나로 바꿀 수 없습니다: 삼각형(3-클리크)의 개수는 부분그래프 불변량이고, 커밋된 개수는 $G_1$이 2개, $G_2$가 0개입니다. 그런데도 두 그래프의 모든 노드는 정확히 두 개의 이웃을 갖는 2-정규(2-regular)입니다. 두 그래프의 서로소 합집합 위에서 1-WL을 실행하면(공유되고 비교 가능한 색으로 두 그래프를 비교하는 표준적인 방법입니다) 다음과 같은 일이 벌어집니다:

exhibit 1 — the classic failure: two triangles vs one hexagon
  G1 = C3 + C3 (nodes x0 x1 x2 y0 y1 y2)   triangles: 2
  G2 = C6      (nodes z0 z1 z2 z3 z4 z5)   triangles: 0
  triangle counts differ -> the graphs are NOT isomorphic
  1-WL on the disjoint union (12 nodes, colours comparable):
    round 0: 1 colour (uniform start)
    round 1: every node has signature (0, (0, 0)) — all 2-regular —
             nothing splits; stable after 1 round
  histogram(G1) = {0: 6}    histogram(G2) = {0: 6}    identical = True
  1-WL returns 'possibly isomorphic' for provably different graphs,
  so no message-passing GNN can embed G1 and G2 differently.

이 메커니즘은 서명에서 드러납니다: 열두 개 노드 모두가 색 0을 지니고, 모두 정확히 두 개의 색-0 이웃을 가지므로, 열두 개의 서명 모두가 $(0, \{\!\{0, 0\}\!\})$이고, 아무것도 나뉘지 않으며, 균일한 색칠은 단 한 번의 증명 라운드 만에 이미 고정점입니다. 안정된 색 히스토그램(color histogram), 즉 각 색을 몇 개의 노드가 지니는지를 나타내는 사상은 두 그래프 모두에서 $\{ 0 \mapsto 6 \}$로 동일합니다. 이 쌍에 대한 1-WL의 판정은 "동형일 가능성이 있다"이며, 그 판정은 틀렸습니다. 삼각형 개수가 이미 그 반대를 증명했기 때문입니다. 동반 파일은 이 주장들 각각을 단언문으로 못박습니다 (wl.py 273–275번째 줄):

    assert tri1 == 2 and tri2 == 0, "triangle counts must prove non-isomorphism"
    assert hist_g1 == hist_g2, "1-WL must FAIL to separate 2xC3 from C6"
    assert rounds1 == rounds2 == union_rounds == 1, "2-regular graphs are stable at once"

다음에 이어지는 것을 분명히 밝혀 둡니다. 이 장에서 가장 강력한 문장이기 때문입니다. 다음 절의 천장 정리가 자리 잡고 나면, 이 사례는 다음을 함의합니다: 메시지 전달로 계산되는 어떤 함수든, 어떤 GCN이든, 어떤 R-GCN이든, 이웃 다중집합으로부터 노드를 갱신하고 순열 불변 요약을 읽어 내는 어떤 아키텍처든, $G_1$과 $G_2$에서 같은 값을 취합니다. 특히 어떤 메시지 전달 GNN도 "이 그래프에 삼각형이 몇 개 있는가"라는 함수나 "어떤 노드가 삼각형 위에 있다"라는 속성을 계산할 수 없고, 두 입력 모두에 대해 동시에 근사조차 할 수 없습니다. 이 함수들은 신경망이 증명 가능하게 구별할 수 없는 한 쌍에서 서로 다른 값을 갖기 때문입니다 [1][2]. 삼각형 세기는 메시지 전달에게 어려운 것이 아닙니다. 그것은 메시지 전달의 한계 너머에 있습니다.

한 장의 그림에 담긴 천장: 1-WL 정제(가운데)는 학계 그래프를 완전히 풀어내지만 두 삼각형을 육각형으로부터 나누지는 못하며(왼쪽), 계수 논리 C²(오른쪽)는 메시지 전달이 넘을 수 없는 선 아래에 정확히 어떤 조건들이 사는지를 말해 줍니다. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

천장이 성립하는 이유

이 정리는 위협이 아니라 진짜 논증을 받을 자격이 있으며, 그 논증은 짧은 귀납법입니다. 앞 두 장의 표기법을 고정합니다: 메시지 전달 신경망은 각 노드 $v$와 각 층 $k$에 대해, 다음의 일반적인 두 단계 갱신을 통해 은닉 상태 $\mathbf{h}_v^{(k)} \in \mathbb{R}^d$($d$개의 실수로 이루어진 벡터이며 $d$는 층의 너비입니다)를 계산합니다:

$$\mathbf{h}_v^{(k)} \;=\; \mathrm{COMBINE}^{(k)}\Big( \mathbf{h}_v^{(k-1)},\; \mathrm{AGGREGATE}^{(k)}\big( \{\!\{\, \mathbf{h}_u^{(k-1)} : u \in N(v) \,\}\!\} \big) \Big),$$

여기서 AGGREGATE는 이웃 상태들의 다중집합을 하나의 요약으로 사상하고(GCN에서는 차수로 정규화된 평균이며, [1]는 이를 원소별 평균-풀링 형태로 분석합니다; R-GCN에서는 관계별로 정규화된 합입니다), COMBINE은 그 요약을 노드 자신의 상태와 융합합니다. 이 함수들은 선형 사상이든 다층 퍼셉트론이든, 학습된 것이든 손으로 정한 것이든, 무엇이든 될 수 있습니다. 유일하게 구조적으로 약속된 것은 노드 $v$에 대한 층 $k$의 입력이 정확히 (자신의 이전 상태, 이웃들의 이전 상태로 이루어진 다중집합)의 쌍이라는 것입니다. 그 쌍은 또한 정확히 1-WL 라운드가 해시하는 것이기도 합니다. 이 정리는 이 우연의 일치를 하나의 상한으로 바꿉니다 [1][2].

정리 (천장). 모든 노드가 동일한 초기 특징으로 시작한다고, 즉 모든 $v, w$에 대해 $\mathbf{h}_v^{(0)} = \mathbf{h}_w^{(0)}$라고 합시다. 이는 1-WL의 균일한 시작과 일치합니다. 그러면 모든 층 수 $k$와 모든 노드 $u, v$에 대해(하나의 그래프 안에서든, 함께 정제된 두 그래프에 걸쳐서든): $c_k(u) = c_k(v)$이면 $\mathbf{h}_u^{(k)} = \mathbf{h}_v^{(k)}$입니다. 동일한 1-WL 색은 동일한 은닉 상태를 강제하므로, GNN은 오직 1-WL이 분리하는 것만을 분리할 수 있습니다.

증명, $k$에 대한 귀납법. 기저 사례 $k = 0$은 가정 그 자체입니다: 모든 초기 색이 같고 모든 초기 특징이 같으므로 함의는 즉시 성립합니다. 귀납 단계에서는 층 $k$에서 주장이 성립한다고 가정하고 $c_{k+1}(u) = c_{k+1}(v)$라고 합시다. 1-WL 갱신에서의 재레이블링은 단사적이고, 단사 함수는 오직 동일한 입력에 대해서만 동일한 출력을 반환하므로, 두 서명은 쌍으로서 같아야 합니다:

$$c_k(u) = c_k(v) \qquad\text{and}\qquad \{\!\{\, c_k(w) : w \in N(u) \,\}\!\} \;=\; \{\!\{\, c_k(w') : w' \in N(v) \,\}\!\}.$$

첫 번째 등식은 곧바로 귀납 가정에 먹입니다: $\mathbf{h}_u^{(k)} = \mathbf{h}_v^{(k)}$. 두 번째 등식은 두 이웃 색 다중집합이 일치한다는 것을 말하며, 두 개의 유한 다중집합이 같다는 것은 정확히 $u$의 모든 이웃 $w$에 대해 $c_k(w) = c_k(\pi(w))$를 만족하는 전단사(bijection, 일대일 대응이면서 전사인 매칭) $\pi : N(u) \to N(v)$가 존재할 때입니다; 특히 $u$와 $v$는 이웃의 수가 같습니다. 귀납 가정을 매칭된 각 쌍에 적용합니다: $c_k(w) = c_k(\pi(w))$는 $\mathbf{h}_w^{(k)} = \mathbf{h}_{\pi(w)}^{(k)}$를 줍니다. 동일한 원소를 동일한 원소로 대응시키는 전단사는 상태 다중집합 또한 같음을 뜻합니다:

$$\{\!\{\, \mathbf{h}_w^{(k)} : w \in N(u) \,\}\!\} \;=\; \{\!\{\, \mathbf{h}_{w'}^{(k)} : w' \in N(v) \,\}\!\}.$$

이제 층 $k+1$에 대한 두 입력 모두가 $u$와 $v$에 대해 일치합니다: 자신의 상태가 같고, 이웃 다중집합이 같습니다. AGGREGATE와 COMBINE은 함수이고, 함수가 무엇이든 간에 동일한 입력에 적용된 함수는 동일한 출력을 반환합니다. 따라서 $\mathbf{h}_u^{(k+1)} = \mathbf{h}_v^{(k+1)}$이고, 이로써 귀납이 완결됩니다. $\blacksquare$

두 가지 소견이 이 증명을 실제로 써먹게 해 줍니다. 첫째, 실패 사례에서 주장된 그래프 수준의 결론은 한 줄로 따라 나옵니다: 그래프 수준의 예측은 최종 노드 상태들의 다중집합에 적용된 읽어내기(readout)이고, $2 \times C_3$와 $C_6$에서 그 다중집합들은 동일하므로(양쪽 모두 같은 벡터의 사본 여섯 개), 어떤 읽어내기든 일치합니다. 둘째, 이 증명이 단사성을 사용하지 않는 지점에 주목하십시오: AGGREGATE와 COMBINE은 임의적일 수 있고, 상한은 여전히 성립합니다. 단사성은 역방향에 관여합니다. 즉 GNN이 천장 아래에 머무르지 않고 천장까지 완전히 올라가는지에 관한 것입니다. 만약 어떤 층의 집계가 1-WL이라면 구별했을 두 이웃 다중집합을 병합해 버린다면, 그 신경망은 1-WL보다 엄격하게 약합니다; 만약 모든 층의 (상태, 다중집합) 사상이 단사적이라면, 대칭적인 귀납법이 동일한 은닉 상태가 동일한 색을 강제함을 보여 주고, 그 신경망은 1-WL과 정확히 일치합니다 [1]. 그래서 천장 안에서의 실용적인 질문은 다음이 됩니다: 어떤 집계 함수가 다중집합에 대해 단사적인가?

합, 평균, 최댓값: 단사성의 경계

증거 3은 각 집계 함수의 사각지대가 고립되도록 두 쌍으로 배열된 네 개의 증거 다중집합으로 답합니다 (wl.py 214–217번째 줄):

    m1 = np.array([1.0, 1.0, 2.0, 2.0])   # M1 = {{1,1,2,2}}  (= M2 duplicated)
    m2 = np.array([1.0, 2.0])             # M2 = {{1,2}}
    m3 = np.array([1.0, 1.0, 2.0])        # M3 = {{1,1,2}}  same set {1,2} as M4,
    m4 = np.array([1.0, 2.0, 2.0])        # M4 = {{1,2,2}}  different multiplicities

커밋된 실행은 각 쌍을 세 가지 방식으로 집계합니다:

exhibit 3 — aggregators on neighbour multisets (the GIN argument)
  pair      A            B          mean(A) mean(B)  max(A) max(B)  sum(A) sum(B)  separated by
  M1 vs M2  {1,1,2,2}    {1,2}       1.5000  1.5000     2.0    2.0     6.0    3.0  sum
  M3 vs M4  {1,1,2}      {1,2,2}     1.3333  1.6667     2.0    2.0     4.0    5.0  sum, mean
  sum separates both pairs; mean misses the k-fold copy (M1 = 2·M2);
  max misses multiplicities (M3, M4 share the set {1, 2}).

쌍	다중집합	평균	최댓값	합
$M_1$ 대 $M_2$	$\{\!\{1,1,2,2\}\!\}$ 대 $\{\!\{1,2\}\!\}$	$1.5 = 1.5$ ✗	$2.0 = 2.0$ ✗	$6.0 \neq 3.0$ ✓
$M_3$ 대 $M_4$	$\{\!\{1,1,2\}\!\}$ 대 $\{\!\{1,2,2\}\!\}$	$1.3333 \neq 1.6667$ ✓	$2.0 = 2.0$ ✗	$4.0 \neq 5.0$ ✓

각 실패에는 증거뿐 아니라 한 줄짜리 도출도 있습니다. 평균은 오직 분포만을 봅니다. 다중집합 $M$의 크기를 $|M|$로 쓰고, 모든 중복도(multiplicity)를 $k$배 한 $k$중 사본을 $kM$이라 합시다. 그러면 합은 $\operatorname{sum}(kM) = k \cdot \operatorname{sum}(M)$으로 스케일되고 크기는 $|kM| = k\,|M|$로 스케일되므로,

$$\operatorname{mean}(kM) \;=\; \frac{\operatorname{sum}(kM)}{|kM|} \;=\; \frac{k \cdot \operatorname{sum}(M)}{k\,|M|} \;=\; \operatorname{mean}(M),$$

그리고 $M_1 = 2 M_2$가 정확히 성립하므로, 평균으로 집계하는 어떤 층도 한 이웃 관계를 그 두 배 사본으로부터 구별할 수 없습니다. 최댓값은 오직 바탕이 되는 집합만을 봅니다. 다중집합의 최댓값은 어떤 원소가 나타나는지에만 의존할 뿐 얼마나 자주 나타나는지에는 결코 의존하지 않으며, $M_3, M_4$는 집합 $\{1, 2\}$를 공유하므로 최댓값은 동점이 됩니다(이들의 평균은 다릅니다, $4/3$ 대 $5/3$이며, 이것이 두 번째 행에서 평균 검사가 통과하는 이유입니다). 합은 모든 것을 봅니다, 그리고 이것은 운이 아니라 정리입니다. 원소들이 가산(countable) 정의역에서 온다는 조건 아래에서 그렇습니다(원소들을 $x_1, x_2, x_3, \ldots$로 나열할 수 있는 정의역을 뜻하며, 이는 디지털 컴퓨터가 표현할 수 있는 모든 정의역을 포괄합니다). 모든 단계를 보여 주는 구성이 여기 있습니다 [1]. 모든 이웃 관계의 크기가 최대 $N$이라고 합시다. 정의역의 $i$번째 원소를 수 $f(x_i) = (N+1)^{-i}$로 부호화합니다. 중복도 $m_1, m_2, m_3, \ldots$를 갖는 다중집합 $M$(원소 $x_i$가 $m_i$번 나타나고, 그중 유한 개만 0이 아니며, 각 $m_i \le N$)은 다음과 같이 합해집니다:

$$\sum_{x \in M} f(x) \;=\; \sum_{i \ge 1} m_i\, (N+1)^{-i},$$

이는 정확히 $(N+1)$진법 전개에서 위치 $i$에 숫자 $m_i$를 갖는 수입니다. 합이 모든 $m_i$를 결정한다는 것을 보이기 위해, 숫자열 $m_i$와 $m_i'$를 갖는 두 다중집합 $M \neq M'$이 같은 합을 가진다고 가정하고, $j$를 숫자가 처음으로 달라지는 가장 작은 위치라고 합시다. 두 합의 차이는 다음과 같습니다:

$$\big(m_j - m_j'\big)(N+1)^{-j} \;+\; \sum_{i > j} \big(m_i - m_i'\big)(N+1)^{-i}.$$

첫째 항은 절댓값이 적어도 $(N+1)^{-j}$입니다. $m_j \neq m_j'$는 정수이므로 적어도 1만큼 차이가 나기 때문입니다. 꼬리 항은 모든 숫자 간극이 가능한 최댓값 $N$을 취하는 기하급수에 의해 위로 유계입니다:

$$\Big|\sum_{i > j} (m_i - m_i')(N+1)^{-i}\Big| \;\le\; \sum_{i > j} N (N+1)^{-i} \;=\; N \cdot \frac{(N+1)^{-(j+1)}}{1 - \frac{1}{N+1}} \;=\; N \cdot \frac{(N+1)^{-(j+1)} (N+1)}{N} \;=\; (N+1)^{-j},$$

등식은 오직 무한히 많은 숫자 간극이 $N$과 같을 때만 성립하는데, 유한 다중집합은 이를 달성할 수 없습니다. 따라서 꼬리 항은 $(N+1)^{-j}$보다 엄격히 작고 첫째 항을 상쇄할 수 없습니다. 차이는 0이 아니고, 합은 서로 다르며, $f$에 이어 합산을 적용하는 것은 크기가 최대 $N$인 모든 다중집합에 대해 단사적입니다. 합 집계는 평균이나 최댓값과 달리 이웃 관계의 완전하고 손실 없는 지문을 담아낼 수 있습니다.

그래프 동형 신경망(Graph Isomorphism Network, GIN)은 정확히 이 관찰 위에 지어진 아키텍처입니다 [1]. 그 층은 다음과 같습니다:

$$\mathbf{h}_v^{(k)} \;=\; \mathrm{MLP}^{(k)}\Big( \big(1 + \varepsilon^{(k)}\big)\, \mathbf{h}_v^{(k-1)} \;+\; \sum_{u \in N(v)} \mathbf{h}_u^{(k-1)} \Big),$$

여기서 스칼라 $\varepsilon^{(k)}$는 노드 자신의 상태가 이웃 합에 흡수되지 않도록 지켜 줍니다. $\varepsilon^{(k)}$를 적절히 선택하면(특징이 가산 정의역에 걸쳐 있을 때는 어떤 무리수 값이든 충분합니다 [1]), 그 층은 다중집합뿐 아니라 (자신의 상태, 이웃 다중집합) 쌍에 대해서도 단사적입니다. 흔히 쓰이는 GIN-0 변형의 $\varepsilon = 0$처럼 임의의 값을 쓰면 그러한 보장은 없습니다. 다층 퍼셉트론은 단사적 부호화와 합성된 임의의 함수를 제공합니다. 그 결과로 얻는 정리가 천장 안의 정확한 경계입니다: 단사적인 집계와 결합을 갖는 메시지 전달 GNN은 1-WL이 구별하는 모든 것을 구별하며, 천장 정리에 의해 그 이상은 아니므로, GIN은 최대로 강력한 메시지 전달 아키텍처입니다 [1][2]. [1]이 분석하는 평균-풀링 형태의 GCN을 포함해, 평균으로 집계하는 아키텍처들은 이 경계보다 엄격히 아래에 있습니다(이들은 한 이웃 관계를 그 두 배 사본으로부터조차 구별하지 못합니다); 메시지 전달로 남아 있는 한 그 경계 위에는 아무것도 없습니다. 커밋된 단언문들은 이 경계를 숫자로 기록하며(wl.py 276–279번째 줄), 요약 줄은 sum_separates=2/2 mean_separates=1/2 max_separates=0/2를 보고합니다.

천장의 논리: C²와 등급 양상 논리

지금까지 천장은 조합론적이었습니다: "1-WL이 나눌 수 없는 것은 무엇이든." 이 장에서 가장 유용한 정리는 그것을 논리로 바꾸는데, 이는 GNN보다 수십 년 앞서 있었습니다 [3][6]. C²를 정확히 두 개의 변수 기호 $x$와 $y$로 제한되고, 중첩된 한정 기호에 의해 재사용될 수 있으며, 계수 한정 기호(counting quantifier) $\exists^{\ge n}$로 확장된 1차 논리로 정의합니다. 여기서 $\exists^{\ge n} y\, \varphi(x, y)$는 "$\varphi$를 참으로 만드는 서로 다른 $y$가 적어도 $n$개 존재한다"라고 읽습니다. $E(x, y)$는 엣지 관계(edge relation)를 나타내며 "$x$와 $y$ 사이에 엣지가 있다"라고 읽고, $\wedge$는 논리곱(conjunction)을 나타내며 "그리고"라고 읽습니다. 재사용이야말로 미묘한 힘입니다: 다음 논리식은

$$\varphi(x) \;=\; \exists y \Big( E(x,y) \;\wedge\; \exists x \big( E(y,x) \big) \Big)$$

"$x$는 이웃을 가지며 그 이웃 또한 이웃을 가진다"라고 말하며, 안쪽 한정 기호 안에서 $x$를 새로운 역할로 재사용합니다. 이는 정당한 C² 논리식입니다: 두 변수로 두 홉을 표현한 것입니다. 특징화 정리는 두 노드가 동일한 안정된 1-WL 색을 받는 것이 정확히 자유 변수 하나짜리 C² 논리식 모두에 동의하는 것과 동치라고 말하며, 두 그래프가 1-WL로 구별 불가능한 것은 그것들이 동일한 C² 문장(자유 변수가 없는 논리식)에 동의하는 것과 동치입니다 [3][6]; 더 일반적으로는, WL의 $k$차원 일반화가 같은 방식으로 $k+1$개의 변수를 갖는 논리 $\mathrm{C}^{k+1}$에 대응합니다 [3][5]. 천장 정리와 결합하면, 이는 신경-기호 독자에게 정확한 표어를 하나 건네줍니다: 메시지 전달 GNN은 오직 어떤 C² 논리식이 두 노드를 분리할 때에만 그 둘을 분리할 수 있다. 천장은 아키텍처의 우연한 특성이 아닙니다. 그것은 2변수 계수 논리의 표현적 도달 범위입니다.

따름정리 하나는 프로그램으로 검사할 수 있습니다: C²로 표현 가능한 모든 노드 속성은 모든 안정된 색 클래스 위에서 상수여야 합니다. 같은 색은 같은 C² 속성을 뜻하기 때문입니다. 증거 4는 등급 논리식 $\varphi(x) = \exists^{\ge 2} y\, E(x,y)$, 즉 "x는 적어도 2개의 이웃을 가진다"로 이를 검사합니다 (wl.py 257–261번째 줄, 137–144번째 줄의 constant_on_classes를 사용합니다):

    def phi(graph: Graph) -> Callable[[str], bool]:
        return lambda v: len(graph[v]) >= 2

    c2_academic = constant_on_classes(stable_acad, phi(acad))
    c2_union = constant_on_classes(stable_union, phi(union))

exhibit 4 — counting logic: the ceiling is exactly C²
  theorem: same stable 1-WL colour  <=>  same C² properties
  witness φ(x) = 'x has at least 2 neighbours'  (∃^{≥2} y. E(x,y))
  academic graph: φ constant on all 13 stable classes -> True
  triangles-vs-hexagon union: φ constant on the single 12-node class -> True

학계 그래프에서는 이 검사가 쉽습니다(13개의 단일원소 클래스는 무엇으로도 나뉠 수 없기 때문입니다). 그러나 삼각형-대-육각형 합집합에서는 실제로 의미가 있습니다: 열두 개 노드짜리 단일 클래스는 하나의 답만을 내놓아야 하고, 실제로 그렇습니다. 열두 노드 모두가 2-정규이고 $\varphi$가 그 모두에 대해 성립하기 때문입니다.

노드 분류기에 대해서는 이 파편을 훨씬 더 정확히 못박을 수 있습니다 [4]. 등급 양상 논리(graded modal logic)는 C²의 국소적 파편입니다: 논리식은 노드 레이블과 불 연결사, 그리고 등급 양상 연산자 $\Diamond^{\ge n} \varphi$("내 이웃 중 적어도 $n$개가 $\varphi$를 만족한다")로부터 지어지며, 그래서 모든 한정 기호는 엣지 관계로 보호되고 평가는 오직 그 노드로부터 엣지를 통해 바깥쪽만을 바라봅니다. 대응 정리는 어떤 논리적 노드 분류기가 평범한 집계-결합 GNN(4부의 청사진)으로 표현 가능한 것은 정확히 그것이 등급 양상 논리로 정의 가능할 때라고 말합니다. 매 층마다 전역적인 읽어내기를 더해 이 아키텍처를 확장하면(집계-결합-읽어내기의 ACR-GNN), 순수하게 국소적인 교환으로는 도달할 수 없는 "그래프 어딘가에 고립된 노드가 있다"와 같은 비국소적 조건을 포착하며 C²의 단항 파편에 속한 모든 분류기를 표현할 수 있습니다 [4]. (읽어내기 변형의 경우 이는 동치가 아니라 포함 관계입니다: 모든 단항 C² 분류기는 어떤 ACR-GNN을 가지지만, ACR-GNN 자체의 정확한 논리적 특징화는 아직 열려 있습니다.) 이 두 수준을 계약으로 읽으십시오: 청사진은 노드 레이블 위의 중첩된 등급 양상으로 표현되는 조건이라면 무엇이든 검사하고 그 이상은 검사하지 않으며, 읽어내기는 C²의 나머지를 사 오지만 결코 세 번째 변수는 사 오지 못합니다.

천장을 통해 다시 읽는 2권

이제 C² 렌즈를 2권의 기술 논리(description logic)에 대어 봅시다. 두 어휘 체계는 거의 단어 그대로 번역되기 때문입니다. "개체 $x$가 개념 $C$를 만족하는가"라는 개념 소속 검사는 노드 속성이고, 역할(role)은 엣지 관계입니다. 표에 들어가기 전에 세 가지 기호를 더 해독해야 합니다: $\top$은 모든 개체가 만족하는 개념인 전칭 개념(universal concept)이므로, $\exists r.\exists r.\top$은 "$r$로 어떤 것과 관계되고 그것이 다시 $r$로 어떤 것과 관계된다"라고 읽습니다; $\circ$는 역할 합성(role composition)이므로, $r \circ s$는 $x$로부터의 $r$-단계가 어떤 $y$에 도달하고 $y$로부터의 $s$-단계가 $z$에 도달할 때마다 $x$를 $z$와 관계시킵니다; 그리고 $\sqsubseteq$는 포섭(subsumption)이며 "~에 포함된다"라고 읽으므로, 공리의 좌변은 우변을 함의합니다. 구성자들을 나란히 놓아 봅시다:

2권의 구성자	1차 논리 형태	변수	판정
논리곱 $C \sqcap D$	$C(x) \wedge D(x)$	1	천장 아래
존재 제약 $\exists r.C$	$\exists y\, (r(x,y) \wedge C(y))$	2	천장 아래: 양상 연산자 $\Diamond^{\ge 1}$
수량 제약 $\ge n\; r.C$	$\exists^{\ge n} y\, (r(x,y) \wedge C(y))$	2	천장 아래: 등급 양상 연산자 $\Diamond^{\ge n}$
중첩된 존재 제약 $\exists r.\exists r.\top$	$\exists y (r(x,y) \wedge \exists x\, r(y,x))$	재사용으로 2	천장 아래
"삼각형 위에 있다"	$\exists y \exists z\, (E(x,y) \wedge E(y,z) \wedge E(z,x))$	3	천장 위
역할 연쇄 $\text{advises} \circ \text{advises} \sqsubseteq \text{grandAdvisor}$	$\exists y\, (\text{advises}(x,y) \wedge \text{advises}(y,z))$	3	천장 위

처음 네 행은 그래프 신경망에게 좋은 소식입니다. EL의 주력 구성자인 $\exists r.C$, "어떤 학생을 지도한다"는 문자 그대로 노드 레이블에 적용된 양상 연산자 $\Diamond^{\ge 1}$이고, 더 풍부한 기술 논리의 한정된 수량 제약 $\ge n\; r.C$, "적어도 2명의 학생을 지도한다"는 노드 레이블에 적용된 등급 양상 연산자 $\Diamond^{\ge 2}$이며, 그 무한정 특수 사례인 "어떤 종류든 적어도 2개의 이웃"은 정확히 증거 4가 안정된 클래스에 대해 검사하는 속성입니다: C²로 표현 가능하고 GNN으로 검사 가능하며, 커밋된 실행은 안정된 색들이 이를 존중함을 확인해 줍니다. 중첩된 존재 제약 또한 위에서 보인 변수 재사용 요령 덕분에 천장 아래에 머무릅니다. 앞 장의 R-GCN과 같은 관계형 신경망은 원리적으로 이러한 조각들로 지어진 어떤 개념에 대해서도 분류기를 학습할 수 있습니다.

마지막 두 행은 경고입니다. "삼각형 위에 있다"는 진정으로 동시에 관계된 세 대상을 필요로 하며, 어떤 C² 논리식도 이를 표현하지 못합니다. 이는 실패 사례의 논리적인 해석입니다: $2 \times C_3$은 삼각형-노드로 가득하고 $C_6$은 하나도 없지만, 이들은 C²로는 동치입니다 [3][5]. 역할-연쇄 행은 더 뼈아픈 이야기입니다. 2권의 완결 엔진은 공리 $\text{advises} \circ \text{advises} \sqsubseteq \text{grandAdvisor}$를 단 한 단계로 처리했습니다: 규칙 CRχ가 공유된 중간 개념을 통해 두 개의 원장 엣지를 융합했습니다. 그러나 그 정의 조건은 중간 증인 $y$를 통해 쌍 $(x, z)$를 관계시킵니다: 논리식 안에는 세 개의 변수가 동시에 살아 있으며, $x$와 $z$가 모두 자유로 남아 있어야 하고 $y$만 한정되어야 하므로 어떤 재사용 요령도 하나를 없애지 못합니다. 이 합성된 관계는 C²로 정의할 수 없습니다.

실패 사례의 안정된 색칠은 그 정의 불가능성을 표준적인 신경망 파이프라인에 대한 구체적인 불가능성으로 바꿔 놓습니다. 이 책 전체를 관통하는 패턴인 부호화-후-점수화(encode-then-score) 링크 예측기를 생각해 봅시다: 메시지 전달이 노드마다 임베딩을 계산한 다음, 두 끝점 임베딩에 대한 점수화 함수(TransE 거리, DistMult 곱, MLP 등)가 그 쌍이 관계에 속하는지를 결정합니다. 정보가 없는 특징을 갖는 육각형 $C_6$ 위에서 이를 실행해 봅시다. 천장 정리에 의해 모든 노드는 같은 임베딩을 받습니다. 여섯 개 모두가 하나의 안정된 색을 공유하기 때문입니다. 이제 쌍 $(z_0, z_2)$와 쌍 $(z_0, z_3)$을 비교해 봅시다: $z_0$와 $z_2$는 공통 이웃 $z_1$을 가지므로 길이-2 경로가 이들을 연결하고 연쇄 조건이 성립합니다; $z_0$의 이웃은 $z_1, z_5$이고 $z_3$의 이웃은 $z_2, z_4$로 서로소인 집합이므로 조건이 성립하지 않습니다. $f(\mathbf{h}_{z_0}, \mathbf{h}_{z_2})$ 대 $f(\mathbf{h}_{z_0}, \mathbf{h}_{z_3})$ 형태의 어떤 점수든 동일한 인자들을 비교하여 동일한 값을 반환하므로, 둘 중 하나의 답은 틀릴 수밖에 없습니다. 메시지 전달 GNN은 일반적으로 2권의 완결이 규칙 발화 한 번으로 도출했던 역할-연쇄 공리를 검증할 수 없습니다. 정직한 각주 하나: 이 불가능성은 구조만을 특징으로 삼는 부호화-후-점수화 패턴을 구속합니다; 앞 장 말미에서 언급된 경로 기반 모델처럼 쌍 자체를 조건으로 삼는 예측기는 신경망이 보는 것 자체를 바꿈으로써 이 논증을 피해 갑니다.

천장을 넘는 방법들, 정직하게 값이 매겨진

천장은 하나의 계산 패턴에 관한 정리이므로, 모든 탈출 경로는 그 패턴을 바꾸며, 각각은 메시지 전달 청사진이 사 두었던 무언가를 대가로 치르고 그 힘을 얻습니다.

고차 신경망. $k$차원 바이스파일러-레만 알고리즘($k$-WL)은 단일 노드가 아니라 노드들의 순서 있는 $k$-튜플을 색칠합니다. 여기서는 변형 이름이 중요한데, 서로 다른 두 알고리즘이 같은 이름을 공유하기 때문입니다. 민간전승(folklore) 튜플 버전은 후보 노드 $w$마다, $w$를 각 좌표에 차례로 대입해서 얻는 색들의 결합 패턴을 기록함으로써 튜플을 정제하며, 그 구별력은 정확히 논리 $\mathrm{C}^{k+1}$에 대응하고 $k$에 따라 엄격하게 증가합니다 [3]; GNN 문헌에서 더 흔한 "무심한"(oblivious) 변형은 각 좌표의 대입을 따로 집계하며 한 단계 아래에 놓입니다(그 2차원 형태는 정확히 1-WL의 힘을 갖습니다). 민간전승 판독에서는 $k = 2$일 때 삼각형을 셀 수 있게 되고 역할 연쇄를 검사할 수 있게 됩니다. 신경망 버전에도 같은 주의 사항이 붙습니다: [2]의 $k$-GNN은 $k$개 원소로 된 노드 집합 사이에 메시지를 전달하며 증명 가능하게 집합 기반 정제와 일치하는데, 이는 튜플 계층보다 다시 약합니다. 반면 튜플 기반 고차 아키텍처는 그 전체 계층을 단계별로 실현합니다 [5]. 모든 변형에 대해 그 대가는 상태 공간입니다. 노드가 $n$개인 그래프는 순서 있는 $k$-튜플을 $n^k$개 가집니다: 우리의 13개체짜리 장난감 예시조차 이미 169개의 쌍과 2,197개의 삼중을 가지며, 백만 노드짜리 그래프는 가중치 하나를 배정하기도 전에 $10^{12}$개의 쌍을 갖게 됩니다. 그 비용은 색칠되는 대상의 조합론적 규모이며, 이것이 고차 신경망이 작은 분자 영역 바깥에서는 드문 채로 남아 있는 이유입니다.

고유 식별자와 무작위 특징. 모든 노드에 구별되는 입력 특징, 즉 원-핫 신원(identity)이나 무작위 벡터를 부여하면, 천장 정리의 가정(동일한 초기 특징)은 즉시 깨집니다: 서로 다른 색으로 씨뿌려진 1-WL은 모든 것을 분리하고, 신경망은 원리적으로 그래프의 어떤 함수든 계산할 수 있습니다. 그 대가는 순열 불변성(permutation invariance), 즉 노드가 우연히 나열된 임의의 순서에 출력이 의존하지 않는다는 보장입니다. 입력에 신원이 있으면 동형인 그래프들이 서로 다른 출력을 받을 수 있고, $z_1$이라 불리는 노드에 대해 학습한 것이 구조적으로 동일한 $z_4$라는 노드에는 전이되지 않으며, 무작위 특징을 쓰면 같은 그래프에 대한 두 번의 실행조차 서로 일치하지 않을 수 있습니다. 표현력은 그래프의 한 부분에서 학습된 모델이 다른 부분에 대해 무언가를 말할 수 있게 해 주던 대칭성을 포기하는 대가로 얻어집니다.

부분그래프 및 위치 인코딩. 실용적인 중간 길은 신경망이 표현할 수 없는 것을 미리 계산해서 입력 특징에 덧붙입니다: 삼각형 개수, 작은 부분그래프의 개수, 앵커 노드까지의 거리, 또는 그래프 라플라시안(Laplacian)의 고유벡터로부터 얻는 스펙트럼 좌표 등입니다. 이렇게 증강된 모델은 이미 평범한 1-WL을 능가합니다. 삼각형 개수로 씨뿌려진 1-WL은 라운드 0에서 이미 $2 \times C_3$을 $C_6$으로부터 나누기 때문입니다. 그 대가는 결정적인 불변량이 이제 학습되는 것이 아니라 선택되는 것이라는 데 있습니다: 누군가는 삼각형이 중요하다는 것을 미리 알고, 그것을 기호적으로 계산해서 건네주어야 하며, 선택된 목록 바깥의 어떤 구조든 보이지 않는 채로 남습니다. 신경-기호 독자에게 이 길은 요령이라기보다는 하나의 논제입니다: 신경망의 천장을 고친 방법은 작은 기호적 전처리 조각이었고, 이는 4권의 패턴을 축소판으로 보여 줍니다.

아직 풀리지 않은 부분

이 장의 정리는 빈틈이 없지만, 진정으로 열려 있는 두 방향에서 보기보다 좁기도 합니다. 첫째, 천장은 구조만 주어진 입력에 대해 최악의 경우 구별하는 것에 관한 진술이며, 천장 안의 함수들을 학습하는 것이 얼마나 어려운지에 대해서는 아무것도 말하지 않습니다. GIN은 1-WL 지문을 표현할 수 있지만, 유한한 표본에 대한 경사 하강법이 그것을 계산하는 가중치를 찾아내는지는 그에 견줄 만큼 깔끔한 정리가 없는 별개의 질문이며, 경험적으로 어떤 아키텍처가 표현할 수 있는 것과 훈련이 안정적으로 도달하는 것 사이의 간극은 넓습니다. 이 분야는 표현력에 대한 정확한 지도는 갖고 있지만 학습 가능성에 대해서는 스케치만을 갖고 있을 뿐입니다. 둘째, 그리고 이 책의 중심축에 더 가까운 이야기로: 천장은 그래프가 주어지고 계산이 그것을 따라 흐르는, 고정된 배선을 읽는 모든 아키텍처를 구속합니다. 같은 벡터 기계 장치를 사용하는 또 다른 방법이 있습니다. "누가 내 이웃인가?"라고 묻는 대신, 노드는 "모두 중에서 지금 나와 관련 있는 사람은 누구인가?"라고 물을 수 있고, 그 답을 내용으로부터 계산하여 매 층마다 자신의 상호작용 그래프를 즉석에서 지을 수 있습니다. 그 연산, 즉 어텐션(attention)은 고정된 그래프 위에서의 메시지 전달이 아니므로, 이 장의 무엇도 그것을 구속하지 않습니다; 어텐션은 그 나름의 다른 힘과 다른 비용을 갖습니다.

왜 중요한가

이 장은 4부가 가진 평결에 가장 가까운 것이며, 신경-기호 엔지니어에게 이 권 안에서 가장 곧바로 쓸모 있는 정리입니다. 4권은 논리적 조건을 검사하거나, 강제하거나, 근사한다고 주장하는 신경망 구성 요소를 거듭 제안할 것이며, C² 대응은 메시지 전달 구성 요소에게 어떤 주장이 애초에 가능한지를 미리 말해 주는 조견표입니다: 등급이 있고 국소적이며 2변수인 조건은 가능하지만, 삼각형, 합성, 연쇄는 고차 상태나 신원, 또는 기호적 특징 없이는 불가능합니다. 역할-연쇄 결과는 특별한 무게를 받을 자격이 있습니다. 함의에 대한 우리의 금본위인 2권의 포화된 원장은 규칙 한 번의 적용으로 도출된 grandAdvisor 엣지를 담고 있습니다; 이 장은 지식 그래프를 위한 지배적인 신경망 패턴이 일반적으로 그 추론을 재현할 수 없음을 증명했습니다. 이후의 어떤 장이 역할 합성을 존중하는 신경 시스템을 필요로 할 때, 그 장은 무언가를 더해야 할 것이며, 이제 우리는 그 필요성이 조율의 문제가 아니라 수학적인 것임을 압니다. 진술할 수 있는 천장은 그 주위를 설계할 수 있는 천장입니다.

핵심 용어

• 1-WL 색 정제(Weisfeiler-Leman) — 분할이 안정될 때까지 각 노드를 그 서명(signature), 즉 (자신의 색, 이웃 색들의 다중집합) 쌍의 단사 해시로 다시 색칠하는 반복 알고리즘; 메시지 전달 구별력의 정확한 상한입니다.
• 안정된 분할(고정점) — 정제 라운드가 재현하는 색칠; 정제는 오직 클래스를 나눌 뿐이므로, 아무것도 만들어 내지 못하는 라운드 하나가 영원한 안정성을 증명합니다.
• 다중집합(multiset) — 오직 원소 개수만이 중요한 모음이며 $\{\!\{ \cdot \}\!\}$로 씁니다; 이웃 집계의 입력입니다.
• 단사적 집계(injective aggregation) — 서로 다른 다중집합을 결코 병합하지 않는 다중집합 함수; 합은 가산 정의역 위에서 이를 허용하지만(진법-$(N+1)$ 구성), 평균과 최댓값은 그렇지 않습니다.
• GIN(그래프 동형 신경망, Graph Isomorphism Network) — 층이 (상태, 다중집합)에 대해 단사적인 합-더하기-MLP 아키텍처로, 정확히 1-WL만큼 강력합니다: 천장 안의 경계입니다.
• C²(2변수 계수 논리) — 재사용 가능한 두 개의 변수와 계수 한정 기호 $\exists^{\ge n}$를 갖는 1차 논리; 동일한 안정된 1-WL 색은 모든 C² 논리식에 대한 동의와 일치합니다.
• 등급 양상 논리(graded modal logic) — 노드 레이블과 양상 연산자 $\Diamond^{\ge n}\varphi$("적어도 $n$개의 이웃이 $\varphi$를 만족한다")로부터 지어지는 C²의 국소적 파편; 평범한 집계-결합 GNN이 표현할 수 있는, 1차 논리로 표현 가능한 노드 분류기와 정확히 일치합니다.
• ACR-GNN — 매 층마다 전역 요약을 갖는 집계-결합-읽어내기 아키텍처; C²의 단항 파편에 속한 모든 분류기를 표현할 수 있습니다(아키텍처 자체의 정확한 특징화는 열려 있습니다).
• 순열 불변성(permutation invariance) — 출력이 노드 순서에 무관하다는 성질; 고유 식별자와 무작위 특징이 표현력을 위해 희생하는 속성입니다.
• k-WL과 k-GNN — 민간전승 $k$-WL은 순서 있는 $k$-튜플을 정제하며, 힘은 $\mathrm{C}^{k+1}$이고 비용은 $n^k$입니다; 무심한 변형과 집합 기반 $k$-GNN은 이 계층에서 엄격히 더 낮은 곳에 자리합니다.

이 장이 이끄는 곳

4부는 하나의 단일한 가정 주위에 그어진 경계에서 끝납니다: 그래프는 주어져 있고, 계산은 그 고정된 엣지를 따라 흐른다는 가정입니다. 어텐션은 이 가정을 버립니다. 어텐션 층에서는 모든 원소가 자신의 내용으로부터 다른 모든 원소와의 관련성을 점수화하고, 그 점수들을 정규화한 다음, 가중 혼합을 읽어 내는데, 이는 사실상 매 층, 매 입력마다 새롭고 가중치가 붙은 완전한 상호작용 그래프를 짓는 것입니다. 그 메커니즘은 트랜스포머의 엔진이며, 이 책에게는 그 이상입니다: 쿼리가 키와 맞춰지는 것은 1권이 손으로 지었던 기호적 연산인 단일화(unification)의 신경망적 메아리입니다. 다음 장은 여기서 적용한 것과 똑같은 규율로 어텐션을 분해합니다: 모든 행렬을 해독하고, 모든 기울기를 유도하며, 모든 숫자를 커밋된 실행에서 가져오고, 자기 자신의 배선을 계산하는 메커니즘이 고정된 배선이 넘을 수 없었던 천장과 어떤 관계에 있는지를 묻습니다.

---

동반 코드: examples/neural/wl.py는 단사적인 표준 재레이블링을 갖는 1-WL 색 정제, 이 장에서 인용된 네 가지 증거(삼각형-대-육각형 실패, 학계 그래프 추적, 합/평균/최댓값 다중집합 표, C² 클래스-불변성 검사), 그리고 모든 주장에 대한 능력 단언문을 구현합니다. 모든 숫자를 재현하려면 python3 examples/neural/wl.py를 실행하십시오; 이 모듈은 구성상 결정론적이므로 반복 실행은 바이트 단위로 동일한 출력을 인쇄합니다.