그래프 라플라시안: 그래프 위의 열 방정식
격자에서는 이웃 평균이 열 방정식이 되고, 촘촘한 무늬부터 지웠다. 그런데 GCN(그래프 합성곱 신경망)의 전파, 곧 자기 자신과 이웃들의 특징을 평균 내는 일을 가라테 클럽 그래프(회원 34명, 친구 관계 78개)에서 되풀이하면, 서로 다른 두 회원 특징의 코사인 유사도 평균이 처음 0.01에서 32층 뒤 0.999가 될 만큼 회원들이 서로 닮아 갔다. 격자가 아닌 그래프 위에서도 같은 일이 일어나는 것일까?
역사: 둘로 갈라진 가라테 동호회
그런데 왜 하필 가라테 동호회일까? 이 그래프는 한 인류학자의 현장 기록에서 왔다. 웨인 자카리는 1970년부터 1972년까지 한 대학의 가라테 동호회를 지켜보며, 회원들 가운데 누가 누구와 동호회 밖에서도 어울리는지를 적었다. 그 회원 34명과 어울리는 짝 78개가 이 장에서 쓰는 그래프다. 관찰하던 사이 강사(논문의 가명 「하이 사범」)와 운영을 맡은 회장(가명 「존 A」) 사이에 다툼이 벌어졌고, 동호회는 결국 둘로 갈라졌다. 자카리는 1977년 논문에서 친구 관계를 따라 정보가 흐른다고 보고, 그 흐름이 가장 약한 곳을 끊는 계산(최대 흐름 최소 절단)으로 누가 어느 편으로 갈지를 예측했는데, 한 사람만 빼고 모두 맞혔다. 실제로 어떻게 갈렸는지가 기록으로 남은 작고 공개된 그래프라, 이 자료는 그 뒤로 그래프를 다루는 방법을 시험하는 단골 표본이 되었다.
GCN의 전파 단계
먼저 작은 그래프에서 숫자로 한 번 평균을 내 보자. 회원 다섯 가운데 가는 나·다·라와 친하고, 라는 마와도 친하다. 회원마다 숫자 하나를 특징으로 주어 가 = 3, 나 = 0, 다 = 6, 라 = 9, 마 = 0이라 하자. 모두가 동시에 자기 자신과 친구들의 평균으로 바꾸면 가는 (3 + 0 + 6 + 9)/4 = 4.5, 나는 (0 + 3)/2 = 1.5, 다는 (6 + 3)/2 = 4.5, 라는 (9 + 3 + 0)/3 = 4, 마는 (0 + 9)/2 = 4.5가 된다. 가장 큰 값과 가장 작은 값의 차이가 9에서 3으로 줄었다. 자기 값에서 평균을 뺀 차이는 가 −1.5, 나 −1.5, 다 +1.5, 라 +5, 마 −4.5이고, 한 번 평균을 내면 값은 꼭 이 차이만큼 줄어든다. 둘레보다 높던 라와 다는 내려가고 낮던 마, 나, 가는 올라간다. 격자에서 「이웃 넷의 평균 − 자기 값」이 값이 바뀌는 빠르기를 정했듯, 그래프에서도 자기 값과 이웃 평균의 차이가 그 일을 한다.
GCN(킵프·웰링 2017)의 한 층은 노드 특징에 전파 행렬 Â(에이 햇으로 읽는다)를 곱하고 가중치 행렬을 곱한 뒤 비선형 함수를 쓴다. 가중치와 비선형 함수를 떼어 내면 남는 전파 단계가 바로 이 평균이다. 다만 킵프와 웰링은 (이웃 수 + 1)로 한 번 나누는 대신, 값을 받는 쪽과 보내는 쪽의 √(이웃 수 + 1)로 한 번씩 나눈다.
degᵢ는 d, e, g의 곱이 아니라 한 덩어리 이름이다. 논문은 이웃 수를 모은 대각 행렬을 D̃로 적지만, 이 장에서 D는 확산 계수이므로 글자만 바꿔 deg로 적었다. I − Â는 자기 값과 이웃 평균의 차이를 재는 행렬이다. 이것을 그래프 라플라시안 (그래프 위에서 자기 값과 이웃 평균의 차이를 재는 행렬, graph Laplacian)이라 한다. 그러니 한 층은 그래프 위에서 열 방정식을 한 걸음 가는 것이다. Â를 곱해도 모양은 그대로이고 크기만 몇 배가 되는 무늬가 있는데, 그 배율을 고윳값(eigenvalue)이라 한다. 층을 쌓으면 Â의 고윳값 λ에 해당하는 무늬가 λ^ℓ로 줄고, 고윳값이 1인 무늬 하나만 남는다. 그 무늬는 노드마다 √(이웃 수 + 1)에 비례하는 벡터라서, 깊은 층의 특징은 모든 노드가 같은 방향을 향하고 길이만 이웃 수에 따라 다르다. 코사인 유사도가 1로 가는 까닭이다. 가라테 클럽 그래프에서 두 번째로 큰 고윳값은 0.896이어서, 32층이면 그 무늬도 0.896의 32제곱, 약 0.03배로 줄어든다.
코드: GCN의 과평활화
가라테 클럽 그래프에서 가중치와 비선형 함수 없이 GCN의 전파만 되풀이하고, 매 층 처음 특징을 되먹이는 경우와 비교한다. 그래프는 networkx에 들어 있는 것을 쓴다.
import numpy as np, networkx as nx
G = nx.karate_club_graph(); n = G.number_of_nodes() # 자카리의 가라테 동호회: 회원 34명, 친구 관계 78개
A = nx.to_numpy_array(G, weight=None)
A_self = A + np.eye(n); d = A_self.sum(1) # d = 이웃 수 + 1
A_hat = A_self / np.sqrt(np.outer(d, d)) # GCN의 전파 행렬: A + I를 양쪽에서 √(이웃 수 + 1)로 나눔
A_plain = A / np.sqrt(np.outer(A.sum(1), A.sum(1))) # 자기 연결 없이 이웃 수로 나눈 것
def mean_cos(X): # 서로 다른 두 노드 특징의 코사인 유사도 평균
Xn = X / np.linalg.norm(X, axis=1, keepdims=True); C = Xn @ Xn.T
return C[~np.eye(n, dtype=bool)].mean()
X0 = np.random.default_rng(0).standard_normal((n, 16)) # 노드마다 16차원 무작위 특징
X, Y = X0.copy(), X0.copy()
for layer in range(1, 65):
X = A_hat @ X # 가중치·비선형 없이 전파만: 그래프 위의 열 방정식 한 걸음
Y = 0.9 * (A_hat @ Y) + 0.1 * X0 # 매 층 처음 특징을 10% 되먹임 (APPNP)
if layer in (2, 8, 32, 64):
print(f"{layer:2d}층: 전파만 {mean_cos(X):.4f} | 되먹임 {mean_cos(Y):.4f}")
ev = np.sort(np.linalg.eigvalsh(A_hat))[::-1]
print(f"A_hat 고윳값: 가장 큰 둘 {ev[0]:.4f}, {ev[1]:.4f}, 가장 작은 것 {ev[-1]:.4f}")
print(f"자기 연결이 없으면 가장 작은 고윳값 {np.linalg.eigvalsh(A_plain).min():.4f}")
v1 = np.linalg.eigh(A_hat)[1][:, -1]
print(f"고윳값 1의 벡터가 √(이웃 수 + 1)에 비례하는가: {np.allclose(np.abs(v1), np.sqrt(d) / np.linalg.norm(np.sqrt(d)))}")
# 2층: 전파만 0.4051 | 되먹임 0.2833
# 8층: 전파만 0.8487 | 되먹임 0.4797
# 32층: 전파만 0.9992 | 되먹임 0.5087
# 64층: 전파만 1.0000 | 되먹임 0.5088
# A_hat 고윳값: 가장 큰 둘 1.0000, 0.8961, 가장 작은 것 -0.4201
# 자기 연결이 없으면 가장 작은 고윳값 -0.7146
# 고윳값 1의 벡터가 √(이웃 수 + 1)에 비례하는가: True
전파만 하면 32층에서 코사인 유사도 평균이 0.999가 되고, 살아남는 무늬는 √(이웃 수 + 1)에 비례하는 고윳값 1의 벡터다. 자기 연결은 가장 작은 고윳값을 −0.715에서 −0.420으로 끌어올린다. 처음 특징을 10% 되먹이면 유사도가 0.509에서 멈춘다.
ML에서: 과평활화와 그 처방
리와 동료들이 쓴 「라플라시안 평활화」라는 말을, 이 장을 마친 독자는 「GCN 한 층은 그래프 위 열 방정식의 한 걸음이다. 층을 쌓는 것은 시간을 흘려 보내는 것이고, 시간이 흐르면 모든 무늬가 줄어 고윳값 1인 무늬 하나만 남는다」로 읽게 된다.
A + I의 자기 연결은 격자의 게으른 평균과 같은 역할을 한다. 자기 연결이 없으면 가라테 클럽 그래프의 가장 작은 고윳값이 −0.715라서 층을 지날 때마다 부호를 바꾸며 천천히 줄어드는 무늬가 생기는데, 자기 연결을 넣으면 가장 작은 고윳값이 −0.420으로 올라간다. 우와 동료들(2019)은 가중치 사이의 비선형 함수를 모두 뺀 GCN이 「고정된 저역 통과 필터 뒤에 선형 분류기를 붙인 것」에 해당함을 보였는데, 촘촘한 무늬부터 지우고 완만한 무늬를 남기는 저역 통과 필터는 열 방정식의 다른 이름이다. 과평활화를 막는 방법들은 대개 열 방정식에 무언가를 더한다. APPNP(approximate personalized propagation of neural predictions, 가스타이거 외 2019)처럼 매 층 처음 특징을 일정 비율 되먹이면 노드 특징이 끝까지 평평해지지 않고 서로 다른 채로 머문다.
문제 6. 친구 넷의 여행 예산
친구 넷 가, 나, 다, 라가 한 줄로 친하다(가–나, 나–다, 다–라). 여행 예산으로 가, 나, 다는 10만 원, 라는 50만 원을 생각한다. 매일 저녁 모두가 동시에 자기와 친한 친구들의 예산 평균으로 생각을 바꾼다(가는 가·나의 평균, 나는 가·나·다의 평균). (가) 예산은 어디로 모이고, 얼마나 빨리 모이는가? (나) 모두가 매일 자기 처음 생각을 10% 섞으면(0.9 × 평균 + 0.1 × 처음 생각) 어떻게 되는가?
결국 다 같은 금액이 되겠죠. 넷의 평균인 20만 원이요.
돌려 보면 5일 뒤 14.9, 16.6, 19.4, 21.1이고 20일 뒤엔 넷 모두 18.0이야. 20이 아닌데?
20이 아니라 18이네요. 처음 예산 가운데 누구 생각이 결론에 더 많이 섞였을까요? 매일 저녁 각자의 생각이 몇 사람의 평균에 들어가는지 세어 봐요.
가의 생각은 가·나 두 사람의 평균에, 나의 생각은 가·나·다 세 사람의 평균에 들어가요. 들어가는 횟수가 (친구 수 + 1)이네요. 그럼 사람마다 새 예산에 (친구 수 + 1)을 곱하면 자기 모임 사람들의 예산을 더한 값이 되고, 이걸 넷 모두 더하면 사람마다 자기가 들어간 모임 수, 곧 (친구 수 + 1)번씩 세어지니까 어제와 같은 합이 남아요. 실제로 2, 3, 3, 2를 곱해 더하면 처음에도 180, 하루 뒤에도 180이에요. 친구가 많은 나와 다는 여러 사람의 평균에 들어가니까 몫이 커서, 모이는 곳은 180 ÷ 10 = 18만 원이고요. 가장 먼 사람과의 차이는 하루에 약 0.73배씩 줄어서 5일 뒤 3.1, 10일 뒤 0.64예요.
여러 모임에 걸친 친구 의견이 결론에 더 많이 섞이는 거네요. (나)는 14.6, 15.6, 18.5, 24.2에서 멈춰요. 끝까지 한 금액이 되지 않아요.
문제 7. 벤젠 고리에서 한꺼번에 평균 내기
탄소 원자 여섯 개가 고리를 이룬 그래프에서 원자 0에만 1을 두고 나머지는 0으로 둔다. (가) 모든 원자를 동시에 양옆 두 이웃의 평균으로 바꾸기를 되풀이하면 어떻게 되는가? (나) GCN처럼 자기 자신을 넣어 셋의 평균으로 바꾸면? (다) 두 규칙의 차이를 푸리에 모드로 설명하라.
돌려 볼게요. 한 번 뒤 (0, 0.5, 0, 0, 0, 0.5), 두 번 뒤 (0.5, 0, 0.25, 0, 0.25, 0)… 10번 뒤 (0.334, 0, 0.333, 0, 0.333, 0), 11번 뒤는 (0, 0.3335, 0, 0.333, 0, 0.3335)예요. 스무 번 뒤에도 짝수 번 원자에 1/3씩이고 홀수 번 원자는 0이에요. 모두 1/6이 돼야 하는데 안 멈춰요.
이거 평균장 방정식에서 두 스핀을 한꺼번에 바꿨을 때랑 똑같아. 그때도 부호가 번갈아 바뀌면서 안 멈췄잖아.
왜 번갈아 가는지 볼까요? 원자에 번호를 붙이면 이웃은 늘 홀짝이 반대예요.
아, 한 번 평균 낼 때마다 값이 짝수 번 원자에서 홀수 번 원자로 통째로 건너가네요. 고리가 짝수 개라 바둑판처럼 두 색으로 칠해져요. 푸리에로 보면 원자마다 부호가 바뀌는 무늬 (+1, −1, +1, −1, +1, −1)에 양옆 평균을 쓰면 정확히 −1배가 되고요. 이 무늬는 크기가 줄지 않으니까 끝까지 남아서, 1/6 위에 ±1/6이 번갈아 얹혀요.
(나)는 (A + I)/3이니까… 한 번 뒤 (0.333, 0.333, 0, 0, 0, 0.333), 스무 번 뒤 (0.1668, 0.1667, 0.1666, …)으로 1/6에 가요. 킵프·웰링 GCN에서 A에 I를 더한 게 이거였구나.
같은 바둑판 무늬에 셋의 평균을 쓰면 몇 배일까요?
(1 − 1 − 1)/3 = −1/3배요. 다른 무늬들도 계산하면 (1 + 2cos k)/3이라서 1, 2/3, 0, −1/3이 나와요. 1 말고 가장 큰 게 2/3니까, 여덟 번이면 1/6과의 차이가 0.013까지 줄어요.
자기 값을 남기면 배율이 1 쪽으로 당겨져서 −1이 사라지는 거네. 게으른 평균이랑 같은 원리야.
그래요. 한꺼번에 바꾸는 속도는 그대로 얻으면서 진동만 없앤 거예요. 고리가 홀수 개면 정확히 −1인 무늬는 없지만, 원자 다섯 개짜리 고리의 −0.809처럼 −1에 가까운 배율이 남아서 부호를 바꾸며 천천히 줄어요.
문제 8. 자기 연결을 빼면
자카리의 가라테 클럽 그래프(회원 34명)에서 회원마다 16차원 무작위 특징(본문 코드와 같은 seed 0)을 준다. 자기 연결이 있는 전파 Â만 되풀이하면 서로 다른 두 회원 특징의 코사인 유사도 평균이 2, 8, 32층 뒤 0.41, 0.85, 0.999가 된다. 이번에는 자기 연결을 빼고 이웃들만 평균 내는 전파 행렬 Aᵢⱼ/√(degᵢdegⱼ)을 되풀이해 곱한다. (가) 2, 8, 32층 뒤 코사인 유사도 평균은 자기 연결이 있을 때보다 높은가 낮은가? (나) 특징은 무엇으로 수렴하며, 얼마나 빨리 가는가? (다) 자기 연결을 되살리고 매 층 처음 특징을 20% 되먹이면(x ← 0.8Âx + 0.2x₀) 유사도는 어디서 멈추는가? (풀어 본 뒤 위젯 3의 「문제 8 불러오기」로 확인해 보자.)
자기 연결이 없으면 가장 작은 고윳값이 −0.715라서 부호를 바꾸며 천천히 줄어드는 무늬가 생긴다고 했잖아. 그 무늬가 오래 버티면 회원들이 덜 닮을 테니까, 유사도가 자기 연결이 있을 때보다 낮을 것 같아.
돌려 볼게. 0.45, 0.90, 0.9999예요. 더 높은데요? 32층이면 자기 연결이 있을 때보다도 더 한 방향이에요.
32층 뒤에 무늬마다 얼마나 남는지 세어 봐요. 어떤 고윳값들을 봐야 하죠?
1 말고 절댓값이 큰 것들이요. 가장 작은 −0.715는 32제곱하면 2 × 10⁻⁵라 금방 사라져요. 오래 남는 건 두 번째로 큰 0.868인데, 32제곱하면 0.011이에요. 자기 연결이 있을 때 두 번째 고윳값 0.896의 32제곱은 0.030이었으니까, 자기 연결이 없을 때 오히려 더 빨리 줄어요.
그럼 자기 연결은 과평활화를 막는 장치가 아니었네요?
자기 연결을 넣으면 고윳값이 어디로 옮겨 가는지 떠올려 봐요. 여섯 원자 고리에서 셋의 평균으로 바꿨을 때처럼요.
배율이 1 쪽으로 당겨졌어요. −1에 가까운 건 0 쪽으로 올라와서 진동이 사라지지만, 0.868 같은 것도 1 쪽으로 당겨져서 0.896이 되니까 더 천천히 줄어요. 자기 연결은 진동을 없애는 장치지, 평평해지는 걸 막는 장치가 아니었어요.
그럼 (나)는 고윳값 1인 벡터를 보면 되는데… 이번엔 √(이웃 수 + 1)이 아니라 √(이웃 수)에 비례해요. 34명이 그 벡터를 따라 한 방향으로 눕는 건 같고요. CNN 필터는 가중치를 배워서 무늬를 골라내는데, 이 전파는 자기 연결이 있든 없든 무조건 저역 통과 필터라서 층마다 가는 무늬를 지우기만 하네요.
열 방정식으로 말하면 층 하나가 시간 한 걸음이고, 그래프는 닫혀 있으니 끝내 평평해지면서 멈춰요. 그럼 평평해지는 걸 막으려면 무엇을 더해야 할까요? 마지막 물음으로 확인해 봐요.
20% 되먹이면 0.19, 0.26, 0.263에서 멈춰요. 64층에서도 0.263이에요. 여행 예산에서 매일 처음 생각을 10% 섞었을 때 끝까지 한 금액이 되지 않았던 거랑 같네요.
처음 특징이 계속 들어오니까 평평해질 수가 없어. 멈춘 모양은 x = 0.8Âx + 0.2x₀을 풀면 되니까 x = 0.2(I − 0.8Â)⁻¹x₀이고. 되먹임이 클수록 처음 특징 쪽으로 더 끌려가니까 덜 닮은 채로 멈추는 거지.
그래요. 열 방정식에 열을 계속 넣는 난로를 더한 거예요. 평평해지는 대신 난로가 넣는 것과 퍼짐이 비기는 모양에서 멈춰요. 과평활화를 막는 방법들은 대개 이렇게 열 방정식에 무언가를 더하거나, 흘려 보내는 시간을 짧게 두는 거예요.
난로를 켜 둔 방 같네요. 난로 곁은 계속 따뜻하고 창가는 계속 서늘하니까, 방 전체가 한 온도가 되지 않아요.