GNN은 어디까지 그래프를 구분할 수 있는가

1-WL 색 정제부터 GIN의 최적성 증명, k-WL 위계, 위치 인코딩까지 — GNN 표현력의 이론적 천장과 그 우회 전략을 추적한다.

GNN은 두 그래프가 같은지 다른지 구분할 수 있는가? 이 질문은 단순해 보이지만, GNN이 학습할 수 있는 것과 학습할 수 없는 것의 경계를 정확히 긋는다. 그 경계의 이름은 Weisfeiler-Lehman test다. message passing GNN이 1-WL을 초과하는 표현력을 가질 수 없다는 사실은 이론인 동시에 실전적 진단 도구다. 그렇다면 이 천장은 왜 생겨났고, 어떻게 뚫을 수 있는가?

1-WL: 색으로 그래프를 읽는 알고리즘

Weisfeiler-Lehman test의 핵심 아이디어는 **색 정제(color refinement)**다. 각 노드에 색을 부여하고, 매 step마다 자신과 이웃의 색 multiset을 해시하여 새 색을 부여한다.

c_i^{(l+1)} = \text{hash}\!\left(c_i^{(l)},\, \{\!\{c_j^{(l)} : j \in N(i)\}\!\}\right)

색 분할이 더 이상 변하지 않으면 stable partition에 도달한다. 두 그래프의 stable color multiset이 같으면 1-WL 동등, 다르면 확실히 비동형(non-isomorphic)이다.

정리 1 · 1-WL의 필요조건

$G_1 \cong G_2 \Rightarrow G_1 \stackrel{1\text{-WL}}{\equiv} G_2$ .

▷ 증명

동형사상 $\pi: V_1 \to V_2$ 가 존재한다고 가정하자. 귀납법으로, step $l$ 에서 $c_i^{(l)}(G_1) = c_{\pi(i)}^{(l)}(G_2)$ 가 성립하면, $\pi$ 가 이웃을 보존하므로 이웃 color multiset도 동일하다. 결정론적 해시 함수에 의해 $c_i^{(l+1)}(G_1) = c_{\pi(i)}^{(l+1)}(G_2)$ . 모든 step에서 color sequence가 일치하므로 두 그래프는 1-WL 동등이다. $\square$

∎

역은 성립하지 않는다. Circulant Skip Link $\text{CSL}(n, k)$ — $C_n$ 에 skip- $k$ edge를 추가한 그래프 — 는 결정적 반례다. $\text{CSL}(8, 2)$ 와 $\text{CSL}(8, 3)$ 은 둘 다 4-regular이고 1-WL이 구분하지 못하지만, 실제로는 비동형이다. 고도로 대칭적인 그래프에서 1-WL의 한계가 드러난다.

GNN 표현력의 천장

message passing GNN의 hidden state $h_i^{(l)}$ 와 1-WL의 색 $c_i^{(l)}$ 는 정보적으로 평행하다. Xu et al. (2019)의 핵심 정리는 이 평행을 등치로 만든다.

정리 2 · 1-WL은 GNN 표현력의 상한 (Xu 2019)

모든 message passing GNN $\phi$ 와 그래프 $G_1, G_2$ 에 대해, $G_1 \stackrel{1\text{-WL}}{\equiv} G_2 \Rightarrow \phi(G_1) = \phi(G_2).$

▷ 증명

귀납법. $l = 0$ 에서 초기 feature가 같으면 hidden state multiset도 같다. step $l$ 에서 두 그래프의 1-WL color partition이 같다고 가정하면, 귀납 가정에 의해 이웃 hidden state의 multiset도 같다. aggregator $\bigoplus$ 가 permutation-invariant이므로 aggregate가 같고, $U_l$ 이 결정론적이므로 $h_i^{(l+1)} = h_j^{(l+1)}$ . readout $R$ 도 같은 multiset에서 같은 값을 반환한다. $\square$

∎

⚠ 트레이드오프

이 정리는 모든 message passing GNN에 적용된다 — GCN, GraphSAGE, GAT, GIN 모두. 1-WL이 구분하지 못하는 CSL, Paley graph 위에서 이들은 모두 동일한 출력을 낸다. 표현력을 높이려면 message passing 프레임워크 자체를 벗어나야 한다.

GIN: 천장에 정확히 닿는 GNN

상한이 있다면 그 상한을 달성하는 GNN이 존재하는가? Xu et al.의 두 번째 결과가 이를 답한다: GIN이 정확히 1-WL 표현력에 도달한다.

핵심은 aggregator의 선택이다.

Mean: $\{1, 1\}$ 과 $\{1\}$ 의 mean이 모두 1 → multiset 구분 불가
Max: $\{1, 2\}$ 와 $\{2\}$ 의 max가 모두 2 → multiset 구분 불가
Sum + MLP: countable domain에서 multiset을 단사적(injective)으로 인코딩 가능

# GCN/GraphSAGE의 mean aggregator: 이웃 수가 달라도 같은 결과
S1 = torch.tensor([1., 1.])  # {1, 1}
S2 = torch.tensor([1.])      # {1}
print(S1.mean(), S2.mean())  # 둘 다 1.0

# GIN의 sum: 구분 가능
print(S1.sum(), S2.sum())    # 2.0 vs 1.0

정리 3 · Sum + MLP = Multiset Universal (Xu 2019)

Countable $\mathcal{X}$ 와 bounded multiset size에 대해, 임의의 multiset 함수 $g: \mathcal{X}^* \to \mathbb{R}^k$ 를 MLP $\phi$ 와 injective embedding $f$ 의 합성으로 근사할 수 있다: $g(S) \approx \phi\!\left(\sum_{x \in S} f(x)\right).$

GIN의 update rule은 이 결과를 구현한다.

$h_i^{(l+1)} = \text{MLP}\!\left((1 + \epsilon)\, h_i^{(l)} + \sum_{j \in N(i)} h_j^{(l)}\right)$

$\epsilon$ 항은 자기 자신의 정보를 이웃 multiset과 분리한다. 충분한 depth와 MLP 표현력이 주어지면 GIN은 1-WL refinement를 시뮬레이션할 수 있으므로, $\text{GIN} \stackrel{\text{표현력}}{\equiv} \text{1-WL}$ 이 성립한다.

k-WL과 그 너머

1-WL의 한계를 넘으려면 어떻게 해야 하는가? 자연스러운 확장이 k-WL이다. 개별 노드 대신 $k$ -tuple $(v_1, \ldots, v_k) \in V^k$ 를 super-node로 보고, 한 자리씩 바꿔가며 message passing을 수행한다.

1\text{-WL} \subsetneq 2\text{-WL} \subsetneq 3\text{-WL} \subsetneq \cdots

이 위계는 strict하다 (Cai-Fürer-Immerman 1992). 3-WL부터는 strongly regular graph — Paley graph, $4\times4$ rook vs Shrikhande — 를 구분할 수 있다.

그러나 대가가 크다.

$k$	표현력	메모리	실용성
1 (GIN)	1-WL	$O(n)$	표준
2 (2-IGN)	2-WL	$O(n^2)$	소형 그래프 가능
3 (3-FGNN)	3-WL	$O(n^3)$	$n=100$ 한계
4+	이론적	$O(n^4)$	비실용

$k=3$ , $n=1000$ 이면 $10^{12}$ 개의 tuple — GPU로도 불가능하다. 표현력을 올리려면 지수적 비용을 치러야 한다는 것이 k-WL의 근본 딜레마다.

위치 인코딩: 효율적인 우회로

k-WL이 “더 강한 test”로 한계를 넘는다면, **위치 인코딩(PE)**은 “추가 정보 주입”으로 1-WL을 우회한다. 노드에 그래프 내 위치를 인코딩한 벡터를 더하면, 구조적으로 동등한 노드들도 다른 표현을 가질 수 있다.

세 가지 주요 접근이 있다.

Laplacian PE (LapPE): 정규화 Laplacian의 eigenvector $u_k$ 를 노드의 좌표로 사용한다. 같은 structural role의 노드도 스펙트럼 좌표가 다르면 구분된다. 단, $u_k$ 와 $-u_k$ 모두 valid eigenvector이므로 부호 모호성이 생긴다. 학습 시 무작위 부호 뒤집기(random sign flip)로 처리하거나, SignNet (Lim 2022)처럼 $\phi(u_k) + \phi(-u_k)$ 를 계산해 부호에 invariant한 표현을 만든다.

Random-Walk PE (RWPE): 전이 행렬 $P = D^{-1}A$ 의 대각 원소 $P^k_{ii}$ — $k$ -step return probability — 를 PE로 사용한다. 부호 문제가 없고 노이즈에 robust하다.

$\text{PE}_{\text{RW}}(i) = (P^1_{ii},\, P^2_{ii},\, \ldots,\, P^K_{ii})$

P-GNN (You 2019): 랜덤 anchor set $S$ 를 샘플링하고, 각 노드에서 anchor까지의 최단 거리를 PE로 사용한다. 대칭적 그래프도 anchor가 다른 위치에 놓이면 구분된다. 단 랜덤 샘플링으로 인한 분산이 크다.

정리

1-WL color refinement는 message passing GNN 표현력의 정확한 상한이다 — Xu et al. (2019) 정리.
GIN(sum + MLP)은 이 상한을 달성하는 유일한 표준 aggregator다. Mean과 Max는 multiset 단사성이 없어 strictly 약하다.
k-WL은 표현력 위계를 strict하게 높이지만 $O(n^k)$ 비용으로 $k \geq 3$ 은 비실용적이다.
위치 인코딩(LapPE, RWPE, P-GNN)은 message passing 프레임워크 안에서 1-WL 한계를 효율적으로 우회하는 현실적 선택지다.

GNN의 표현력 이론은 “무엇을 할 수 없는가”를 정확히 말할 수 있다는 점에서 강력하다. 그 경