How Powerful are Graph Neural Networks? (GIN)

Paper: Xu, Keyulu; Hu, Weihua; Leskovec, Jure; Jegelka, Stefanie. (2019). "How Powerful are Graph Neural Networks?" International Conference on Learning Representations (ICLR 2019), arXiv:1810.00826.

**GIN(Graph Isomorphism Network)**은 이웃 집계 기반 GNN의 판별력 상한이 Weisfeiler-Lehman(WL) test와 동등함을 이론적으로 증명하고, 그 상한에 도달하는 조건(단사적 집계·결합·readout)을 만족하는 sum-MLP 집계 아키텍처를 제안한다(Xu et al., ICLR 2019). feature가 없는 Reddit에서 mean 계열(GCN 포함)이 무작위 추측 수준(50.0/20.0)에 그칠 때 GIN-0는 Reddit-Binary 92.4±2.5를 달성했다.

Abstract: 본 문서는 GNN 표현력 연구의 기준점이 된 GIN(Graph Isomorphism Network) 논문을 해설한다. 논문은 이웃 집계(message passing) 방식의 GNN이 그래프를 구별하는 능력이 Weisfeiler-Lehman(WL) test를 넘을 수 없음을 보이고, WL test와 같은 판별력에 도달하는 조건(집계·결합·readout 함수의 단사성)을 확립한 뒤, 그 조건을 만족하는 단순한 아키텍처 GIN을 제안한다. 같은 틀에서 GCN의 mean, GraphSAGE의 max aggregator가 구별하지 못하는 그래프 구조도 정밀하게 특성화한다. 다만 이론은 판별력에 관한 것이고 일반화는 별개라는 점을 논문 스스로 밝힌다. 평가 프로토콜(10-fold CV validation accuracy 보고)과, 단사성이 유한 정밀도로는 그대로 실현되지 않는다는 이론-구현 간극도 함께 봐야 한다.

---

Executive Summary

항목	설명
연구 질문	이웃 집계 기반 GNN은 서로 다른 그래프 구조를 어디까지 구별할 수 있으며, 그 상한에 도달하는 설계 조건은 무엇인가?
핵심 기여	GNN 판별력의 상한이 WL test임을 보이고(Lemma 2), 상한 도달 조건을 단사성으로 특성화하며(Theorem 3), 이를 만족하는 GIN을 제안한다(Eq 4.1).
방법적 결과	h^{(k)}_v = \mathrm{MLP}^{(k)}\big((1+\epsilon^{(k)})\cdot h^{(k-1)}v + \sum{u\in\mathcal N(v)} h^{(k-1)}_u\big). 비교된 세 aggregator 중 sum만 multiset 전체를 보존하고, mean은 분포, max는 집합만 남긴다(Figure 2, Corollary 8·9).
실험 결과	저자 보고 기준 GIN-0은 9개 그래프 분류 벤치마크에서 최고 수준이고, feature가 없는 Reddit에서 mean 계열(GCN 포함)은 random guessing 수준(50.0/20.0)에 그친다(Table 1).
핵심 한계	이론은 일반화를 직접 말하지 않는다(§7.1). 단사성 구성은 존재 논증이며, 이론상 더 강한 GIN-ε이 실험에서는 GIN-0에 진다.

TL;DR — (1) GIN은 이웃 집계 GNN의 표현력 상한이 WL test임을 이론으로 증명하고, 단사성 조건을 만족하는 sum-MLP 집계 아키텍처를 제안한다. (2) GIN-0는 9개 그래프 분류 벤치마크에서 최고 수준이며, feature가 없는 Reddit에서 mean 계열(GCN 포함)이 50.0/20.0의 무작위 추측 수준에 그칠 때 GIN-0는 Reddit-Binary 92.4±2.5를 달성했다. (3) 이론은 판별력에 관한 것이고 일반화를 직접 보장하지 않으며, 이론상 더 강한 GIN-ε이 실험에서는 GIN-0에 뒤지는 이론-구현 간극이 있다.

목차

1. 서론
2. 예비 지식
3. 이론 골격: GNN의 상한과 도달 조건
4. GIN: 조건을 만족하는 단순한 아키텍처
5. 덜 강한 변형들: mean, max, 1-layer가 놓치는 것
6. 실험 결과 및 분석
7. 주의해서 읽을 점
8. 방법적 한계와 확장
9. 결론

---

1. 서론

1.1 연구 배경

이 논문의 출발점은 진단이다. GCN, GraphSAGE 등 이웃 집계 기반 GNN이 여러 과제에서 좋은 성능을 냈지만, 새 아키텍처의 설계는 대체로 "경험적 직관, 휴리스틱, 실험적 시행착오"에 기반하고, 무엇을 표현할 수 있고 무엇을 못 하는지에 대한 형식적 분석이 없다는 것이다(§1).

논문이 택한 표현력의 기준은 서로 다른 그래프 구조를 구별하는 능력이다. 이상적으로는 동형이 아닌 임의의 두 그래프를 다른 embedding으로 보내야 하지만, 이는 graph isomorphism 문제 자체(다항 시간 알고리즘이 알려지지 않음)를 푸는 것과 같다. 그래서 논문은 "약간 더 약한 기준"인 WL graph isomorphism test 대비 판별력으로 표현력을 측정한다(논문 §4).

핵심 통찰은 WL test가 강력한 이유에 있다. WL은 서로 다른 이웃 구성을 항상 서로 다른 라벨로 보내는 단사 집계 갱신을 쓴다. GNN의 집계 스킴이 단사 함수를 표현할 수 있다면 GNN도 WL만큼의 판별력을 가질 수 있다는 것이 논문의 중심 논리다(§1).

그림 1. 이론 프레임워크 개관. WL test는 각 노드를 루트로 한 subtree 구조로 그래프를 구별하고(가운데), GNN의 집계 함수가 이웃 feature의 multiset 전체를 보존하면 GNN도 재귀적으로 subtree를 포착해 WL만큼 강해질 수 있다(오른쪽). — Xu et al. (2019), Figure 1에서 연구·학습 목적상 발췌.

1.2 핵심 질문

질문	내용
Q1	이웃 집계 기반 GNN의 그래프 판별력에 상한이 있는가?
Q2	그 상한에 도달하려면 집계·결합·readout 함수(2장에서 정의)가 어떤 성질을 가져야 하는가?
Q3	GCN·GraphSAGE 같은 기존 변형은 정확히 어떤 구조를 구별하지 못하는가?

1.3 학술적 위치

논문이 §1 말미에 밝히는 기여는 네 가지다: (1) GNN이 그래프 구별에서 기껏해야 WL test만큼 강력함을 보임, (2) WL test와 동등해지는 집계·readout 조건 확립, (3) GCN·GraphSAGE가 구별 못 하는 구조의 식별과 이들이 포착하는 것의 정밀한 특성화, (4) 판별력이 WL과 같은 단순 아키텍처 GIN 개발.

원논문 §6(related work)이 언급하는 선행 이론은 두 건뿐이다. Scarselli et al.(2009a)의 measurable 함수 근사 결과와, 자신들의 아키텍처가 graph kernel의 RKHS(커널이 정의하는 함수 공간) 안에 있음을 보인 Lei et al.(2017)이다. 논문의 차별점은 특정 아키텍처가 아니라 이웃 집계라는 클래스 전체를 다루는 일반 프레임워크라는 데 있다(§6). 이후 이 논문은 GNN 표현력 연구의 표준 좌표계가 됐고, GIN 자체는 그래프 분류 벤치마크의 기본 baseline이 됐다(8.2절, 논문 외 지식).

이 논문은 이 위키의 GraphSAGE·GCN 리뷰와도 여기서 만난다. 두 논문에서 경험적 선택지였던 aggregator(mean, max-pooling)가 이 논문에서 이론적 서열을 부여받는다. 5장에서 자세히 다룬다.

---

2. 예비 지식

2.1 이웃 집계의 일반형

논문은 GNN의 k번째 층을 두 단계로 일반화한다(§2, Eq 2.1):

초기값은 h^{(0)}_v = X_v(입력 feature)이고, k번 반복하면 노드 표현은 k-hop 이웃의 정보를 반영한다. 기존 모델들이 이 틀의 인스턴스로 재표현된다.

• GraphSAGE(pooling 변형): \mathrm{AGGREGATE} = \mathrm{MAX}({\mathrm{ReLU}(W \cdot h^{(k-1)}_u)}) — 원소별 max-pooling(Eq 2.2). COMBINE은 concat 후 선형 변환.
• GCN: AGGREGATE와 COMBINE이 통합된 h^{(k)}_v = \mathrm{ReLU}(W \cdot \mathrm{MEAN}{h^{(k-1)}_u, \forall u \in \mathcal N(v) \cup {v}}) — 원소별 mean pooling(Eq 2.3).

그래프 분류에서는 마지막에 READOUT이 노드 표현들을 그래프 표현으로 모은다: h_G = \mathrm{READOUT}({h^{(K)}_v \mid v \in G})(Eq 2.4).

2.2 WL test와 WL subtree kernel

WL test의 1차원 형태("naive vertex refinement", 이하 1-WL)는 (1) 각 노드의 라벨과 이웃 라벨들을 집계하고 (2) 집계 결과를 유일한 새 라벨로 해시하는 과정을 반복한다. 어느 반복에서든 두 그래프의 노드 라벨 구성이 달라지면 non-isomorphic으로 판정한다(§2). 다항 시간에 넓은 클래스의 그래프를 구별하지만, regular graph(모든 노드의 차수가 같은 그래프) 등 예외가 있다는 것도 논문이 명시한다(§2, §4).

Shervashidze et al.(2011)의 WL subtree kernel은 WL 각 반복의 노드 라벨 개수를 그래프의 feature vector로 쓰는 graph kernel이다. k번째 반복의 라벨은 그 노드를 루트로 하는 높이 k의 subtree 구조에 대응한다(§2, Figure 1).

2.3 Multiset과 countable 가정

서로 다른 노드가 같은 feature를 가질 수 있으므로, 이웃 feature들의 모임은 집합이 아니라 multiset이다. 형식적으로 X = (S, m), S는 서로 다른 원소들의 집합, m: S \to \mathbb N_{\ge 1}은 중복도다(Definition 1, §3).

논문 §3의 환원 논리는 이렇다. 최대로 강한 GNN이라면 두 노드를 같은 embedding으로 보내는 경우는 두 노드의 rooted subtree 구조와 대응 feature가 같을 때뿐이어야 하는데, subtree는 이웃을 통해 재귀적으로 정의되므로, 문제는 결국 "GNN이 두 이웃 multiset을 같은 표현으로 보내버리는가"로 환원된다.

전제 하나가 이론 전체에 깔려 있다. 노드 입력 feature가 countable universe에서 온다는 가정이다(§3). 입력이 countable이면 각 층의 은닉 feature 공간도 countable로 유지된다(Lemma 4). 연속(uncountable) feature는 논문이 명시적으로 future work로 남긴다(논문 §4).

---

3. 이론 골격: GNN의 상한과 도달 조건

3.1 Lemma 2 — 상한: GNN ≤ WL

임의의 이웃 집계 기반 GNN이 두 그래프 G_1, G_2를 다른 embedding으로 보내면, WL test도 G_1, G_2를 non-isomorphic으로 판정한다(논문 §4).

즉 이 클래스의 GNN은 그래프 구별에서 WL test보다 강할 수 없다. 증명(Appendix A)은 귀납이다. WL이 구별하지 못하면 두 그래프의 WL 라벨 구성이 매 반복 같고, "같은 WL 라벨이면 같은 GNN feature"가 유지되며, readout이 순열 불변이므로 최종 그래프 embedding도 같아진다.

3.2 Theorem 3 — 도달 조건: 단사성

층 수가 충분하고, (a) 노드 갱신 h^{(k)}_v = \varphi\big(h^{(k-1)}_v, f({h^{(k-1)}_u})\big)에서 multiset 위의 f와 \varphi가 단사이고, (b) graph-level readout이 단사이면, GNN은 WL test가 구별하는 모든 그래프 쌍을 구별한다(논문 §4).

증명(Appendix B)도 귀납으로, 매 반복 k마다 GNN feature가 WL 라벨의 단사 함수(h^{(k)}_v = \varphi(l^{(k)}_v))임을 유지한다. 단사 함수의 합성은 단사이기 때문이다. WL이 K번째 반복에서 두 그래프를 구별하면 노드 feature의 multiset도 달라지고, 단사 readout이 그 차이를 그래프 embedding의 차이로 보존한다.

Lemma 2와 합치면 "단사 집계 + 단사 readout GNN의 판별력 = WL test"가 된다. 문제는 이제 함수 설계로 넘어간다: multiset 위에서 단사인 함수를 신경망으로 어떻게 만드는가.

논문은 같은 절에서 WL 대비 GNN의 이점도 정리한다. WL의 노드 라벨은 본질적으로 one-hot이라 subtree 사이의 유사도를 표현하지 못하지만, Theorem 3를 만족하는 GNN은 subtree를 저차원 공간에 embedding하도록 학습하므로 구조가 비슷한 그래프를 가깝게 배치할 수 있다. subtree 패턴이 희소하거나 노이즈가 있을 때 일반화에 유리한 성질이다(논문 §4).

---

4. GIN: 조건을 만족하는 단순한 아키텍처

논문 스스로 GIN을 "최대 판별력을 갖는 많은 GNN 중 단순한 한 예"라고 부른다(§4.1). 유일한 해가 아니라 조건을 만족하는 구성 하나다.

4.1 sum이 특별한 이유 — Lemma 5

\mathcal X가 countable이면, h(X) = \sum_{x\in X} f(x)가 크기 제한이 있는 각 multiset X마다 유일하도록 하는 f: \mathcal X \to \mathbb R^n이 존재한다. 나아가 임의의 multiset 함수 g는 g(X) = \varphi(\sum_{x\in X} f(x))로 분해할 수 있다(§4.1).

sum aggregator는 multiset 위에서 단사일 수 있고, 그 위에 임의의 multiset 함수를 얹을 수 있다는 뜻이다. 집합 위 함수를 원소별 변환의 합으로 표현한 Deep Sets(Zaheer et al., 2017)를 multiset으로 확장한 결과인데, 차이가 결정적이다: mean처럼 set 위에서는 단사인 함수도 multiset 위에서는 단사가 아니다(§4.1). 증명(Appendix D)은 countable 원소에 번호 Z(x)를 매기고 f(x) = N^{-Z(x)}(N은 multiset 크기 상한)로 두는 구성이다. 합이 일종의 N진법 표현 역할을 해서 단사가 된다.

4.2 자기 자신과 이웃의 구별 — Corollary 6

Theorem 3의 조건 (a)는 노드 자신 c와 이웃 multiset X의 쌍 위에서 단사여야 한다. Corollary 6은 모든 무리수를 포함한 무한히 많은 \epsilon에 대해

가 각 쌍 (c, X)마다 유일하도록 하는 f가 존재하고(c \in \mathcal X, X는 크기 제한이 있는 multiset), 그런 쌍 위의 임의의 함수 g를 g(c,X) = \varphi\big((1+\epsilon)\cdot f(c) + \sum_{x\in X} f(x)\big)로 분해할 수 있음을 보인다. 증명(Appendix E)은 무리수의 성질을 쓴다. f의 값이 유리수이므로, \epsilon이 무리수면 \epsilon \cdot (f(c) - f(c'))가 무리수가 되어 유리수 합과 같아질 수 없다. 이 논법의 함의는 7.3절에서 다시 본다.

4.3 GIN 갱신식과 readout

Corollary 6의 f와 \varphi를 MLP로 모델링하면 GIN이 나온다. 임의의 연속함수를 근사할 수 있다는 universal approximation theorem에 기댄 선택이다(§4.1):

MLP가 함수 합성을 표현할 수 있으므로 f^{(k+1)} \circ \varphi^{(k)}를 하나의 MLP로 합친다. 입력 feature가 one-hot이면 첫 반복에서는 합산 자체가 단사라 합 앞에 MLP가 필요 없다(§4.1). sum 집계가 GCN류와의 첫 번째 차이라면, 1-layer perceptron이 아닌 MLP가 두 번째 차이다(5.1절, Lemma 7). \epsilon은 학습 파라미터(GIN-ε) 또는 0 고정(GIN-0)이다. GIN-0은 이론상 약간 덜 강력하다. GIN-ε만 구별하는 (다소 인위적인) 그래프가 존재한다(§7 각주).

Graph-level readout은 모든 층의 readout을 이어 붙인다(Eq 4.2). 층별 표현을 함께 쓰는 Jumping Knowledge Networks(Xu et al., 2018)와 유사한 구조다:

이른 반복의 feature가 때로 더 잘 일반화되기 때문이라는 것이 이유다(§4.2). READOUT을 sum으로 하면 GIN이 WL test와 WL subtree kernel을 일반화함이 증명된다(§4.2).

---

5. 덜 강한 변형들: mean, max, 1-layer가 놓치는 것

§5의 제목은 "Less powerful but still interesting GNNs"다. 격하가 아니라 특성화가 목적이다. GIN의 두 요소를 하나씩 제거해 본다: MLP 대신 1-layer perceptron, sum 대신 mean/max.

5.1 1-layer perceptron은 부족하다 — Lemma 7

임의의 선형사상 W에 대해 \sum_{x\in X_1} \mathrm{ReLU}(Wx) = \sum_{x\in X_2} \mathrm{ReLU}(Wx)가 성립하는 유한 multiset X_1 \ne X_2가 존재한다(§5.1).

반례는 단순하다: X_1 = {1,1,1,1,1}, X_2 = {2,3} — 합이 같은 서로 다른 multiset이다(Appendix F). 원소가 모두 양수면 ReLU가 선형처럼 거동해 층 전체가 이웃 feature의 단순 합산으로 퇴화한다. 증명은 bias 항이 없는 경우이고, 논문은 bias가 있어도 1-layer perceptron이 multiset 함수의 universal approximator는 아니라고 덧붙인다. 서로 다른 그래프를 어느 정도 다른 위치로 보내더라도, 그 embedding이 구조 유사도를 담지 못해 선형 분류기 같은 단순한 분류기로는 적합이 어려울 수 있다. 논문이 함께 적어 둔 함의다(§5.1).

5.2 mean은 분포, max는 집합

그림 2. multiset 위 표현력 순위: sum(전체 multiset) > mean(원소 비율·분포) > max(중복을 버린 집합). — Xu et al. (2019), Figure 2에서 연구·학습 목적상 발췌.

각 aggregator가 무엇을 보존하는지는 적절한 f의 존재를 전제로 한 양방향 조건으로 증명된다.

• Corollary 8 (mean): 적절한 f가 존재하여, h(X_1) = h(X_2) ⟺ 두 multiset이 같은 분포를 가짐(X_1 = (S, m), X_2 = (S, k \cdot m))이 성립한다. mean은 중복도의 절대량을 버리고 비율만 남긴다(논문 §5.3).
• Corollary 9 (max): 적절한 f가 존재하여, h(X_1) = h(X_2) ⟺ 두 multiset의 underlying set이 같음이 성립한다. max는 중복도를 완전히 버린다(논문 §5.4).

그림 3. mean·max가 구별하지 못하는 구조 쌍. (a) 모든 노드 feature가 같으면 mean·max 모두 실패하고 sum은 개수로 구별한다. (b) max는 중복을 무시해 실패하고 mean은 비율이 달라 구별한다. (c) \frac{1}{2}(h_g + h_r) = \frac{1}{4}(2h_g + 2h_r)이므로 mean·max 모두 실패한다. — Xu et al. (2019), Figure 3에서 연구·학습 목적상 발췌.

주의할 대목은 논문이 여기서 지키는 균형이다. 원논문 §5.3은 mean이 node classification에서 잘 작동하는 이유도 함께 설명한다. 과제의 신호가 정확한 구조가 아니라 이웃 feature의 분포일 때 mean으로 충분하고, feature가 다양해서 거의 반복되지 않으면 mean은 sum만큼 강력해진다. 논문 주제 분류나 커뮤니티 탐지처럼 feature가 풍부한 node classification에서 GCN 계열이 잘 되는 것과 정합적이다. 그림 3(a) 같은 상황도 degree를 feature로 주면 mean은 원리적으로 sum을 복원할 수 있지만 max는 그래도 못 한다(§5.2). max에 대한 긍정적 특성화도 있다. 정확한 구조나 분포보다 대표 원소("skeleton")를 찾는 과제에는 max가 적합할 수 있고, 논문은 point cloud 학습에서 max-pooling이 노이즈에 강건하다는 Qi et al.(2017)의 실증을 근거로 든다(논문 §5.4). attention 가중 평균(GAT)과 LSTM pooling은 분석 범위 밖이라고 명시한다(§5.5).

GraphSAGE 리뷰와 이어지는 대목이 여기다(논문 외 해석). GraphSAGE 원 논문에서 mean/pooling/LSTM은 경험적 비교 대상이었는데, 이 논문은 그중 mean과 max-pooling에 "무엇을 보존하는가"라는 기준을 부여한다(LSTM은 §5.5가 명시한 범위 밖이다). GraphSAGE의 max-pooling은 multiset을 집합으로 붕괴시키는 가장 약한 축에 놓인다. 다만 이 서열은 graph-level 구별 기준이고, GraphSAGE가 원래 다루던 feature 풍부한 inductive node classification에서는 §5.3의 논리가 실전 성능을 설명해 준다.

---

6. 실험 결과 및 분석

6.1 데이터셋과 설정

9개 그래프 분류 벤치마크: bioinformatics 4종(MUTAG, PTC, NCI1, PROTEINS)과 social network 5종(IMDB-B, IMDB-M, RDT-B, RDT-M5K, COLLAB)이다(§7).

Dataset	# graphs	# classes	평균 노드 수	feature
IMDB-B	1000	2	19.8	degree one-hot
IMDB-M	1500	3	13.0	degree one-hot
RDT-B	2000	2	429.6	전 노드 동일(상수)
RDT-M5K	5000	5	508.5	전 노드 동일(상수)
COLLAB	5000	3	74.5	degree one-hot
MUTAG	188	2	17.9	categorical
PROTEINS	1113	2	39.1	categorical
PTC	344	2	25.5	categorical
NCI1	4110	2	29.8	categorical

social 데이터셋의 feature 처리는 의도적이다. "모델이 입력 feature에 의존하지 않고 주로 네트워크 구조에서 학습하게" 하려고 Reddit은 전 노드 동일 feature, 나머지는 degree one-hot을 쓴다(§7).

공통 설정: GNN 5층(입력층 포함), 모든 MLP 2층, 전 은닉층 Batch Normalization, Adam(초기 lr 0.01, 50 epoch마다 0.5배 감쇠). 튜닝 대상은 hidden units(bio {16, 32}, social 64), batch size {32, 128}, dropout {0, 0.5}, epoch 수다. readout은 bio에서 sum, social에서 mean을 썼다("테스트 성능이 더 좋아서", §7). 비교 모델은 aggregator/perceptron 조합으로 명명되고, mean–1-layer와 max–1-layer는 사소한 수정을 제외하면 각각 GCN, GraphSAGE에 대응한다(§7). baseline은 WL subtree kernel(C-SVM, iteration 1–6 튜닝)과 DCNN·PATCHY-SAN·DGCNN·AWL인데, 딥러닝 baseline과 AWL의 수치는 원논문 보고값을 그대로 옮긴 것이다(§7).

평가는 10-fold cross-validation이고, 보고되는 것은 "10개 fold의 validation accuracy 평균과 표준편차"다(§7). epoch도 10-fold 평균 CV 정확도가 최고인 시점을 고른다. 별도 validation set 방식은 데이터가 작아 극도로 불안정하다는 이유에서다. MUTAG의 validation set은 18개뿐이다(§7). 이 프로토콜의 함의는 7.1절에서 다룬다.

6.2 훈련 정확도: 이론의 실증 (Figure 4)

그림 4. 동일 설정에서의 training accuracy. GIN-ε·GIN-0은 거의 완벽하게 적합하고, mean/max·1-layer 변형은 여러 데이터셋에서 심하게 과소적합한다. 어떤 GNN도 WL subtree kernel의 training accuracy를 넘지 못한다. — Xu et al. (2019), Figure 4에서 연구·학습 목적상 발췌.

표현력이 높을수록 훈련 데이터를 잘 적합해야 한다는 논리로, 이론 검증은 training accuracy로 이뤄진다(§7.1). 이 비교에서는 hyperparameter를 전 데이터셋 공통으로 고정한다(5층, hidden 64, batch 128, dropout 0.5; WL subtree kernel은 5층에 상응하는 iteration 4)(§7). 관찰 세 가지가 이론 예측과 맞아떨어진다.

1. GIN-ε·GIN-0은 모든 훈련셋을 거의 완벽하게 적합하고, ε 학습은 적합에 아무 이득이 없다.
2. mean/max·1-layer 변형은 여러 데이터셋에서 심하게 과소적합하며, 그 순서가 표현력 순위(MLP > 1-layer, sum > mean·max)와 일치한다.
3. 어떤 GNN도 WL subtree kernel의 training accuracy를 넘지 못한다. Lemma 2의 상한과 부합하는 패턴이다. 예컨대 IMDB-BINARY에서는 어떤 모델도 훈련셋을 완벽히 적합하지 못하고, GNN은 기껏해야 WL kernel과 같은 training accuracy에 도달한다(§7.1).

6.3 테스트 정확도 (Table 1)

Model	IMDB-B	IMDB-M	RDT-B	RDT-M5K	COLLAB	MUTAG	PROTEINS	PTC	NCI1
WL subtree	73.8±3.9	50.9±3.8	81.0±3.1	52.5±2.1	78.9±1.9	90.4±5.7	75.0±3.1	59.9±4.3	86.0±1.8*
DCNN	49.1	33.5	–	–	52.1	67.0	61.3	56.6	62.6
PATCHY-SAN	71.0±2.2	45.2±2.8	86.3±1.6	49.1±0.7	72.6±2.2	92.6±4.2*	75.9±2.8	60.0±4.8	78.6±1.9
DGCNN	70.0	47.8	–	–	73.7	85.8	75.5	58.6	74.4
AWL	74.5±5.9	51.5±3.6	87.9±2.5	54.7±2.9	73.9±1.9	87.9±9.8	–	–	–
Sum–MLP (GIN-0)	75.1±5.1	52.3±2.8	92.4±2.5	57.5±1.5	80.2±1.9	89.4±5.6	76.2±2.8	64.6±7.0	82.7±1.7
Sum–MLP (GIN-ε)	74.3±5.1	52.1±3.6	92.2±2.3	57.0±1.7	80.1±1.9	89.0±6.0	75.9±3.8	63.7±8.2	82.7±1.6
Sum–1-Layer	74.1±5.0	52.2±2.4	90.0±2.7	55.1±1.6	80.6±1.9	90.0±8.8	76.2±2.6	63.1±5.7	82.0±1.5
Mean–MLP	73.7±3.7	52.3±3.1	50.0±0.0	20.0±0.0	79.2±2.3	83.5±6.3	75.5±3.4	66.6±6.9	80.9±1.8
Mean–1-Layer (GCN)	74.0±3.4	51.9±3.8	50.0±0.0	20.0±0.0	79.0±1.8	85.6±5.8	76.0±3.2	64.2±4.3	80.2±2.0
Max–MLP	73.2±5.8	51.1±3.6	–	–	–	84.0±6.1	76.0±3.2	64.6±10.2	77.8±1.3
Max–1-Layer (GraphSAGE)	72.3±5.3	50.9±2.2	–	–	–	85.1±7.6	75.9±3.2	63.9±7.7	77.7±1.5

원논문 표의 강조 규칙: 최고 GNN은 굵게 표시되고, 유의수준 10%의 paired t-test가 GIN과 최고 GNN을 구별하지 못하면 GIN도 함께 굵게 표시된다. baseline이 모든 GNN보다 유의하게 높은 곳은 굵게 + 별표다. 위 표에는 별표 2곳(NCI1의 WL subtree, MUTAG의 PATCHY-SAN)만 재현했다. Reddit 계열과 COLLAB의 max-pooling 칸이 빈 것은 GPU 메모리 제약으로 실험하지 못해서다(§7 각주).

읽을 것 세 가지.

• Reddit은 이론이 예측한 실패가 그대로 나타난 사례다. 전 노드가 같은 feature를 갖는 조건에서 mean 계열(GCN 포함)은 RDT-B 50.0±0.0, RDT-M5K 20.0±0.0으로 정확히 random guessing 수준이다(§7.1, §5.2). degree를 feature로 주면 Mean–MLP가 71.2±4.6(RDT-B), 41.3±2.1(RDT-M5K)로 회복되지만 그래도 sum 기반보다 훨씬 낮다는 것이 논문의 서술이다(§7.1). 이 두 수치는 degree feature 조건이라, 상수 feature 조건인 Table 1 수치와 같은 행에서 비교할 수는 없다.
• GIN-0이 GIN-ε을 근소하게, 그러나 일관되게 이긴다. 두 모델의 훈련 적합은 같으므로, 논문은 GIN-0의 우위를 단순함(simplicity)으로 설명한다(§7.1). 이론상 서열(GIN-ε > GIN-0)이 실험에서 뒤집힌다(7.3절).
• bio 데이터셋에서는 GIN이 압도적이지 않다. PTC에서는 Mean–MLP(66.6±6.9)가 GIN-0(64.6±7.0)보다 높고, NCI1·MUTAG에서는 baseline이 유의하게 앞선다. GIN의 명확한 우위는 훈련 그래프가 많고 구조가 신호인 social 데이터셋에 집중된다(§7.1).

---

7. 주의해서 읽을 점

7.1 "test accuracy"의 실체

Table 1의 수치는 별도 test set 성능이 아니라 10-fold CV의 validation accuracy 평균이고, epoch 선택까지 같은 지표로 이뤄진다(§7). 모델 선택에 쓰인 데이터로 최종 성능을 보고하는 구조라 낙관 편향의 여지가 있다. 논문은 당시 관행(Yanardag & Vishwanathan, 2015; Niepert et al., 2016)을 따랐고 데이터가 작아 대안이 불안정하다는 이유를 명시했다. 그래도 이 소규모 그래프 분류 벤치마크군(6.1절의 9개 데이터셋이 속한, 이른바 TU 벤치마크)의 평가 프로토콜은 이후 재현성 문헌의 주요 검토 대상이 됐다(논문 외 지식). 통제된 재평가에서 모델 간 순위가 달라질 수 있다는 일반적 지적이 있으며, 구체 수치는 여기서 단정하지 않는다.

데이터 크기도 함께 봐야 한다. MUTAG는 188개, PTC는 344개 그래프이고 표준편차가 ±5~10%p에 이른다. 이 분산에서 몇 %p 차이로 순위를 매기는 것 자체의 신뢰도가 낮고, 굵게 표시 판정에 쓰인 t-test도 유의수준 10%라는 관대한 기준이다(Table 1 caption). 딥러닝 baseline 수치가 원논문 전재라는 점(§7)도 감안해야 한다. 전재된 수치와의 프로토콜 동일성은 별도로 보장되지 않는다.

7.2 social feature 설계의 방향

Reddit의 상수 feature는 §5.2에서 mean·max가 원리적으로 실패한다고 증명된 바로 그 조건이다. 따라서 Reddit에서 mean 계열이 random guessing 수준인 것은 이론 검증으로는 깔끔하지만, "실전에서의 우위" 증거로 읽으면 순환이 된다. 실패하도록 설계된 조건에서 실패를 확인한 것이기 때문이다. degree feature 하나로 격차의 상당 부분이 좁혀진다는 §7.1의 수치가 이 점을 보여주고, degree를 주면 mean이 sum을 복원할 수 있다는 §5.2의 이론적 언급과도 맞는다. 또 하나, 이론(Theorem 3(b))은 단사 readout을 요구하는데 social 실험은 성능을 이유로 mean readout을 썼다(§7). 이론이 제시한 조건과 실험 구성이 어긋난다(논문 외 비판).

7.3 존재 논증과 구현 사이 (논문 외 비판)

이론의 단사성 구성은 존재 논증이다. Lemma 5의 f(x) = N^{-Z(x)}는 feature universe가 크면 지수적으로 작아져 부동소수점으로는 구별할 수 없고, Corollary 9의 max 구성은 무한 차원 공간을 쓴다(Appendix D, H). Corollary 6의 증명은 ε이 무리수라는 조건에 의존하는데, gradient descent로 학습되는 ε은 부동소수점(유리수)이다. MLP가 f와 φ를 "표현할 수 있다"는 것도 universal approximation에 기댄 존재 진술이지 학습 보장이 아니다. 논문도 optimization landscape의 이해를 future work로 남긴다(§8).

이 간극은 GIN-ε 실험에서 그대로 드러난다. 이론상 GIN-ε이 더 강하지만(§7 각주) 훈련 적합에 이득이 없고 테스트에서는 GIN-0에 진다. sum vs mean/max 수준의 굵은 표현력 차이는 실증되지만, ε 수준의 미세한 차이는 벤치마크에서 확인되지 않는다.

7.4 표현력 ≠ 일반화

논문 스스로 이 구분을 명시한다: "우리의 이론적 결과는 GNN의 일반화 능력을 직접 말하지 않는다"(§7.1). 실제로 논문 데이터 안에 그 증거가 있다. 훈련 정확도가 가장 높은 것은 WL subtree kernel인데 테스트에서는 social 데이터셋에서 GIN에 크게 뒤진다(RDT-B 81.0 vs 92.4). 논문이 드는 이유는 WL kernel이 node feature를 결합하는 법을 학습하지 못하고 one-hot 라벨이라 subtree 유사도를 표현하지 못한다는 것이다(§7.1; 3.2절의 embedding 논의와 같은 이야기다). 이론상 더 강한 GIN-ε보다 약한 GIN-0이 더 잘 일반화하는 것(6.3절), 이른 층의 feature가 더 잘 일반화될 수 있다는 §4.2의 언급(Eq 4.2 concat readout의 동기)도 표현력과 일반화가 별개라는 같은 관찰이다. 판별력 최대화가 곧 좋은 모델이라는 뜻이 아니라는 점은 논문을 인용할 때 자주 뭉개지는 부분이다.

7.5 WL 상한 자체의 한계

GIN의 "maximally powerful"은 이웃 집계 클래스 안에서의 최대라는 뜻이다. 그 상한인 1-WL 자체가 regular graph 등에서 실패하고(§2, §4의 Cai et al. 1992 인용), 논문도 message passing 너머의 아키텍처 탐색을 future work로 남긴다(§8). regular graph처럼 국소 구조가 균질한 그래프에서는 GIN도 원리적으로 구별 불가라는 함의(논문 외 비판)가 이후 higher-order GNN 연구의 출발점이 됐다.

---

8. 방법적 한계와 확장

8.1 논문이 명시한 한계·제약

한계·제약	내용	출처	상세
일반화 미다룸	이론은 판별력에 관한 것, 일반화·최적화는 future work	§7.1, §8	7.4절
WL 상한	message passing 클래스 자체가 1-WL을 넘지 못함; 너머는 future work	Lemma 2, §8	7.5절
Countable 가정	연속 feature와 embedding 기하(가까움)는 미해결	§3, §4	2.3절
미분석 aggregator	attention(GAT)·LSTM pooling은 범위 밖	§5.5	5.2절
프로토콜 선택	validation set 방식이 불안정해 CV validation accuracy 보고 채택(한계 인정이 아니라 선택의 정당화)	§7	7.1절
실험 결측	Reddit·COLLAB의 max-pooling은 GPU 메모리 제약으로 미실행	§7 각주	6.3절

8.2 이후 연구 계보 (논문 외 지식)

• WL 계층 연구: "GNN 표현력 ≤ 1-WL" 등식 위에서 이후 표현력 연구가 전개됐다. k-WL에 대응하는 higher-order GNN, 서브그래프 카운팅 능력 분석, subgraph GNN 등이 이 프레임을 전제로 한다. 거의 같은 시기의 병행 연구인 Morris et al.(2019, k-GNN)도 독립적으로 같은 1-WL 상한을 보였고, 두 논문이 이 흐름의 공동 출발점으로 함께 인용된다(본 논문은 Morris et al.을 인용하지 않는다).
• 벤치마크 관행: GIN은 그래프 분류·표현학습 벤치마크에서 GCN과 함께 표준 baseline이 됐고, "sum aggregation + MLP"는 구조 판별이 필요한 과제의 기본 선택지가 됐다. 한편 이 논문의 평가 프로토콜은 이후 재현성 연구의 검토 대상이 됐다. 이론적 결론은 견고하게 수용된 반면, 소규모 TU 벤치마크 실험 관행은 커뮤니티가 보완해 갔다.

---

9. 결론

이 논문은 "어떤 GNN이 더 강한가"라는 경험적 질문을 "GNN이 multiset 위에서 어떤 함수를 표현할 수 있는가"라는 형식적 질문으로 바꿨다. 상한(WL test), 도달 조건(단사성), 도달하는 아키텍처(GIN), 그리고 기존 모델들이 상한에 못 미치는 정확한 이유(mean=분포, max=집합, 1-layer=합산 퇴화)까지 하나의 틀에서 정리된다.

이 논문을 읽을 때 잡아야 할 균형은 이렇다.

기여	읽는 법
GNN ≤ WL, 도달 조건	이웃 집계 클래스 안에서의 결과다. 1-WL 자체의 한계는 그대로 물려받는다.
GIN 아키텍처	단사성 구성은 존재 논증이고, ε 항의 이론적 우위는 실험에서 확인되지 않았다.
aggregator 특성화	mean·max의 실패 목록이 아니라 보존 범위의 특성화다. feature가 풍부한 node classification에서 mean이 잘 되는 이유도 같은 틀이 설명한다.
벤치마크 성능	CV validation accuracy 프로토콜과 소규모 데이터의 분산 안에서 읽어야 한다. 이론 검증의 무게는 test 표가 아니라 training 곡선(Figure 4)에 있다.

GIN 논문의 지속적인 가치는 벤치마크 수치보다 사고의 틀에 있다. aggregator를 고를 때 "무엇이 잘 되던가"가 아니라 "이 함수가 multiset의 무엇을 보존하는가"를 먼저 묻게 만든 것이다.

References

Atwood, J., & Towsley, D. (2016). Diffusion-convolutional neural networks. Advances in Neural Information Processing Systems, 29. https://arxiv.org/abs/1511.02136 (PDF 보기)

Hamilton, W. L., Ying, R., & Leskovec, J. (2017). Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 30. https://arxiv.org/abs/1706.02216 (PDF 보기)

Ivanov, S., & Burnaev, E. (2018). Anonymous walk embeddings. Proceedings of the 35th International Conference on Machine Learning, 2186–2195. https://arxiv.org/abs/1805.11921 (PDF 보기)

Kipf, T. N., & Welling, M. (2017). Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations. https://arxiv.org/abs/1609.02907 (PDF 보기)

Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., & Grohe, M. (2019). Weisfeiler and Leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33, 4602–4609. https://doi.org/10.1609/aaai.v33i01.33014602 (PDF 보기)

Niepert, M., Ahmed, M., & Kutzkov, K. (2016). Learning convolutional neural networks for graphs. Proceedings of the 33rd International Conference on Machine Learning, 2014–2023. https://arxiv.org/abs/1605.05273 (PDF 보기)

Qi, C. R., Su, H., Mo, K., & Guibas, L. J. (2017). PointNet: Deep learning on point sets for 3D classification and segmentation. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 77–85. https://doi.org/10.1109/CVPR.2017.16 (PDF 보기)

Shervashidze, N., Schweitzer, P., van Leeuwen, E. J., Mehlhorn, K., & Borgwardt, K. M. (2011). Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12, 2539–2561. (PDF 보기)

Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). How powerful are graph neural networks? International Conference on Learning Representations. https://arxiv.org/abs/1810.00826 (PDF 보기)

Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.-i., & Jegelka, S. (2018). Representation learning on graphs with jumping knowledge networks. Proceedings of the 35th International Conference on Machine Learning, 5453–5462. https://arxiv.org/abs/1806.03536 (PDF 보기)

Yanardag, P., & Vishwanathan, S. V. N. (2015). Deep graph kernels. Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1365–1374. https://doi.org/10.1145/2783258.2783417 (PDF 보기)

Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R., & Smola, A. (2017). Deep sets. Advances in Neural Information Processing Systems, 30. https://arxiv.org/abs/1703.06114 (PDF 보기)

Zhang, M., Cui, Z., Neumann, M., & Chen, Y. (2018). An end-to-end deep learning architecture for graph classification. Proceedings of the AAAI Conference on Artificial Intelligence, 32. https://doi.org/10.1609/aaai.v32i1.11782 (PDF 보기)