CS224W - (15) Advanced Topics in GNNs
GNN의 한계
완벽한 GNN이란 뭘까요? $k$개의 레이어로 이루어진 GNN은 $K$-홉 이웃의 구조에 기반한 노드를 임베딩합니다. 완벽한 GNN은 홉과 상관 없이 이웃 구조와 노드 임베딩 사이의 injective function을 가지는 것을 의미합니다.
완벽한 GNN이라면 두 노드가 같은 이웃 구조를 가진다면 반드시 같은 임베딩을 가져야 합니다. 반대로 두 노드가 다른 이웃 구조를 가진다면 다른 임베딩을 가져야 합니다. 하지만 이런 관측들도 완벽하지는 않습니다. 첫 번째 내용인 ‘두 노드가 같은 이웃 구조를 가진다면 반드시 같은 임베딩을 가진다’는 다음과 같은 문제가 발생할 수 있습니다.
두 노드의 이웃 구조가 동일하더라도 서로 다른 임베딩을 할당해야 하는 경우가 생깁니다. 각 노드가 그래프 내에서 다른 위치에서 등장하기 때문입니다. 이런 태스크를 위치 인식 태스크(position-aware task) 라고 부릅니다. 위 그림과 같이 격자 형태의 그래프나 뉴욕 도로 네트워크에서는 위치도 중요하게 됩니다. 다시 말해서 완벽한 GNN이라도 위 태스크에선 문제를 올바르게 풀지 못할 수 있습니다.
또한 매시지 전달 GNN의 경우 위와 같은 사이클의 길이를 셀 수 없습니다. 그럼에도 불구하고 노드 $v_1$과 노드 $v_2$에 대한 연산 그래프는 항상 같습니다. 이처럼 여러 예시를 통해 지금까지 배운 GNN은 완벽하지 않다는 것을 알 수 있습니다.
본 장에서는 보다 표현력 높은 GNN을 통해서 이런 문제를 해결하는 방법에 대해 알아볼 예정입니다. 하나는 그래프에서 노드의 위치에 기반한 노드 임베딩을 생성하는 위치 인식 GNN(position-aware GNNs) 이고, 다른 하나는 WL 테스트보다 더 표현력 높은 메시지 전달 GNN인 Identity-aware GNN 입니다.
앞으로의 내용은 이런 가정을 기저에 두고 전개됩니다. 서로 다른 입력값(노드, 엣지, 그래프)는 다르게 레이블링됩니다. 이 입력값에 대한 임베딩이 서로 같다면 실패한 모델이 되고, 서로 다르다면 성공적인 모델이 됩니다. 임베딩은 GNN의 연산 그래프에 의해 결정됩니다. 위 그림을 통해 이 가정을 풀어보자면 두 입력값으로 노드 $v_1$과 $v_2$가 있고 서로 다른 레이블 A와 B가 있습니다. 서로 다른 입력값이므로 이 두 노드에 대한 임베딩은 서로 달라야 합니다.
이 문제를 해결하기 위해 매우 나이브한 방법인 원 핫 인코딩은 고려하지 않습니다. 원 핫 인코딩을 활용하면 서로 다른 노드에 다른 ID를 부여할 수 있지만 확장성이 떨어집니다. 노드 개수 $N$에 비례하는 피처 차원이 필요하기 때문이죠. 뿐만 아니라 새로운 노드나 그래프에 대해서 확장하는 것도 불가능합니다.
위치 인식 GNN(Position-aware GNNs)
그래프는 두 종류의 태스크로 나눌 수 있습니다. 그래프의 구조적 역할로 레이블링하는 구조 인식 태스크(structure-aware task)와 그래프 내 노드의 위치로 레이블링하는 위치 인식 태스크(position-aware task)가 있습니다.
구조 인식 태스크는 기존 GNN에서도 잘 작동합니다. 위 그림에서 볼 수 있다시피 $v_1$과 $v_2$를 잘 구분합니다.
하지만 위치 인식 태스크에서는 기존 GNN이 작동하지 않습니다. $v_1$과 $v_2$는 구조적 대칭성 때문에 항상 같은 연산 그래프를 반환하기 때문입니다. 이런 문제를 해결하기 위해 앵커 노드(anchor node)를 활용합니다.
임의의 노드를 앵커 노드인 $s_1$으로 설정하고 $v_1$과 $v_2$ 까지의 상대적인 거리를 계산합니다. 앵커 노드는 좌표축으로써의 역할을 하고 이렇게 되면 각 노드의 위치를 지정하는 데에 사용할 수 있습니다. 앵커 노드가 많아지면 그래프에서 더 많은 좌표축이 생기게 되므로 다른 노드의 위치를 더 잘 나타낼 수 있게 됩니다.
이제 단일 노드에서 노드 집합까지 일반화를 시켜보겠습니다. 각 노드에서 앵커 집합까지의 거리를 앵커 세트의 각 집합까지의 최소 거리로 정의합니다. 큰 앵커 집합은 다른 노드의 위치를 더 정확하게 추정할 수 있습니다. 위 그림에서 $s_1$과 $s_2$ 만으로는 노드 $v_1$과 노드 $v_3$을 구분할 수 없지만 추가적인 앵커 노드 $s_3$이 있으면 두 노드를 구분할 수 있게 됩니다.
앵커 집합에 대한 이론
메트릭 공간 $(V, d)$을 기존 거리 메트릭을 보존한 채로 유클리드 공간 $\mathbb{R}^k$에 임베딩하는 것이 목표입니다. 조금 더 수학적으로 말하면 모든 순서쌍 $u, v \in V$에 대해서 유클리드 임베딩 거리 $\|\mathbf{z}_u - \mathbf{z}_v \|_2$ 기존 거리 메트릭 $d(u, v)$에 가깝게 만들어야 합니다.
이를 위해선 (완전하진 않지만) Bourgain’s Theorem을 사용할 수 있습니다. 노드 $v \in V$의 다음 임베딩 함수가 있습니다.
\[f(v) = \left( d_\min(v, S_{1, 1}), d_\min(v, S_{1, 2}), \cdots, d_\min(v, S_{\log n, c \log n}) \right) \in \mathbb{R}^{c \log^2 n}\]- $c$: 상수
- $S_{i, j} \subset V$ : 확률 $1/2^i$ 로 독립적으로 $V$에서 뽑힌 노드 집합
- $\displaystyle d_\min(v, S_{i, j}) \equiv \min_{u \in S_{i, j}} d(v, u)$
이를 통해 $f$를 통해 생성된 임베딩 거리가 기존 거리 메트릭 $(V, d)$에 가까워지는 것을 증명할 수 있습니다.
P-GNN 은 이 Bourgain’s Theorem을 따릅니다. 앵커 집합 $S_{i, j}$ 에서 $O(\log^2 n)$만큼 샘플링을 하고 다음을 통해서 노드 $v$를 임베딩합니다.
\[\left( d_\min(v, S_{1, 1}), d_\min(v, S_{1, 2}), \cdots, d_\min(v, S_{\log n, c \log n}) \right)\]P-GNN은 그래프의 유도 가능성(inductive capability)을 유지합니다. 학습 중에는 매번 앵커 집합을 다시 샘플링합니다. P-GNN은 매번 새로운 앵커 집합에 대해서 학습을 수행합니다. 테스트 시에는 새로운 그래프에 대해서 새로운 앵커 집합을 샘플링합니다.
그래프에 대한 포지션 인코딩(position encoding) 은 노드의 위치를 무작위로 선택된 앵커 집합과의 거리로 나타냅니다. 포지션 인코딩의 각 차원은 앵커 집합에 연결됩니다. 이렇게 노드의 위치 정보를 활용할 수 있는 간단한 방법은 포지션 인코딩을 노드의 피처로 활용하는 것입니다. 이 방법은 실제로도 잘 작동합니다. 물론 문제도 있는데 포지션 인코딩의 각 차원이 임의의 앵커 집합에 연결되므로 위치 인코딩의 차원은 의미의 변경 없이 순서가 임의로 바뀔 수도 있습니다.
그래서 위치 정보를 활용할 수 있는 엄밀한 방법은 포지션 인코딩의 순열 불변성 을 유지할 수 있는 특별한 뉴럴 네트워크를 사용하는 것입니다. 이 뉴럴 네트워크가 바로 위치 인식 GNN입니다. 위 그림처럼 입력 피처의 차원의 순서를 섞으면 아웃풋 차원의 순열만 발생하고 각 차원의 값은 변경되지 않습니다.
Identity-aware GNN
지금까지 GNN이 위치 인식 태스크에서 잘 작동하지 않는 경우를 보았지만 그렇다고 구조 인식 태스크에서 무조건 잘 작동하냐고 하면 그것도 아닙니다. 구조 인식 태스크에서 잘 작동하지 않는 경우를 노드 레벨, 엣지 레벨, 그래프 레벨로 나누어 살펴볼 수 있는데요.
노드 레벨에서 다른 입력 그래프를 사용하지만 같은 연산 그래프가 아웃풋으로 나오는 경우 GNN이 잘 작동하지 않을 수 있습니다.
엣지 레벨에서도 연산 그래프가 같아져 GNN이 작동하지 않을 수 있습니다. 엣지 A와 엣지 B는 같은 노드 $v_0$을 공유합니다. 결국 같은 연산 그래프를 얻게 되죠.
이는 그래프 레벨에서도 동일합니다.
이런 문제를 해결하기 위해 유도 노드 컬러링(inductive node coloring) 을 사용합니다. 연산 그래프에서 임베딩할 노드에 색을 칠하면 그래프 구조가 다를 때 연산 그래프에서 색이 칠해지는 부분이 달라집니다. 예를 들어 위 그림에서 $v_2$와 $v_3$ 그래프의 순서를 바꾸더라도 연산 그래프는 같습니다.
이 방법은 노드 분류 태스크, 그래프 분류, 링크 예측 등 다양한 태스크에 도움이 됩니다. 우선 노드 분류 태스크에서 기존 연산 그래프라면 위 그림의 두 그래프를 구분할 수 없지만 노드에 색을 칠하면 두 연산 그래프를 구분할 수 있게 됩니다.
그래프 분류에서도 처음에 구분을 할 수 없었던 두 그래프를 성공적으로 구분할 수 있습니다.
링크 예측에서도 비슷한 방법으로 두 노드 $v_1$과 $v_2$를 구분할 수 있습니다. 그러면 노드에 색은 어떻게 칠할 수 있을까요?
기본 아이디어는 이종 그래프에서의 메시지 전달 방법입니다. 이종 그래프에서는 다른 종류의 노드에 대해서 다른 종류의 메시지 전달 방법을 적용합니다. ID-GNN 역시 다른 색의 노드에 대해서 다른 메시지 전달 및 집계 방법을 사용합니다.
ID-GNN의 최종 아웃풋은 노드 $v \in V$에 대해 노드 임베딩 $\mathbf{h}_v^{(K)}$입니다. 우선 에고 네트워크(ego-network)를 추출합니다. $\mathcal{G}_v^{(K)}$를 노드 $v$의 $K$-홉 이웃이라고 할 때 노드 피처를 다음과 같이 초기화합니다.
\[\mathbf{h}_u^{(0)} \leftarrow \mathbf{x}_u \qquad \text{for } u \in \mathcal{G}_v^{(K)}\]그리고 $k = 1, \cdots, K$와 $u \in \mathcal{G}_v^{(K)}$에 대해 다음의 이종 그래프 메시지 전달 함수를 계산합니다.
\[\mathbf{h}_u^{(k)} \leftarrow \text{AGG}^{(k)} \left( \left\{ \text{MSG}^{(k)}_{\mathbf{1}[s=v]} \left( \mathbf{h}_s^{(k-1)} \right), s \in N(u) \right\}, \mathbf{h}_u^{(k-1)} \right)\]두 노드 $v_1$, $v_2$가 있을 때 같은 연산 그래프 구조를 가졌지만 서로 다른 노드 색을 갖고 있다고 가정할 때 다른 노드에 임베딩 연산을 위한 다른 뉴럴 네트워크를 적용했기 때문에 임베딩도 달라져 이런 경우에 이종 그래프의 메시지 전달 함수가 잘 작동하게 됩니다.
ID-GNN은 주어진 노드에 대해 사이클의 수를 셀 수 있기 때문에 아무래도 GNN보다 좋은 성능을 냅니다.
ID-GNN을 간소화한 ID-GNN-Fast를 제안해볼 수도 있습니다. 이종 그래프의 메시지 전달 함수 없이 식별 정보를 노드 피처로 사용하고 각 레이어에서의 사이클 수를 추가 노드 피처로 사용하는 것입니다.
GNN의 강건함
딥러닝은 여러 분야에서 두각을 드러냈지만 항상 문제가 없었던 것은 아닙니다. 컨볼루션 네트워크의 경우 위 그림처럼 적대적 공격(adversarial attacks)에 취약한 모습을 보였습니다. 뿐만 아니라 자연어 처리나 오디오 프로세싱에서도 비슷한 문제가 발생한 바 있습니다. 이런 사례는 딥러닝 모델을 실제 시나리오에 배포하는 것을 방해합니다. 이처럼 딥러닝 모델은 항상 강건하진 않습니다.
GNN은 추천 시스템, 소셜 네트워크, 검색 엔진 등 다양한 플랫폼에서 활용됩니다. 그러다보니 입력 그래프를 조작하여 GNN의 예측을 망가뜨리려는 시도는 꾸준히 있을 수 있습니다. GNN의 강건함에 대해 알아보기 위해서 GCN을 사용하는 준지도 노드 분류 태스크를 가정하겠습니다.
실제 공격(attack)의 종류는 어태커(attacker) 직접 타겟 노드를 조작하는 직접 공격(direct attack) 과 간접적으로 노드와 엣지를 조작하는 간접 공격(indirect attack) 이 있습니다. 여기서 타겟 노드를 $t \in V$, 어태커 노드(attacker node)를 $S \subset V$로 두겠습니다.
직접 공격(Direct attack)
직접 공격은 타겟 노드를 직접 공격하기 때문에 $S = \{t \}$로 둘 수 있습니다. 직접 공격의 종류는 다음과 같습니다.
- 타겟의 노드 피처를 수정
- ex) 웹사이트 콘텐츠 수정
- 타겟 노드에 링크 추가
- ex) 좋아요 또는 팔로워 추가
- 타겟 노드에 연결된 엣지 제거
- ex) 사용자 언팔로우
간접 공격 (Indirect attack)
간접 공격은 타겟 노드를 직접 공격하지 않기 때문에 $t \not\in S$로 둘 수 있습니다. 간접 공격의 종류는 다음과 같습니다.
- 어태커 노드의 피처 수정
- 어태커 노드에 링크 추가
- 어태커 노드에 연결된 엣지 제거
적대적 공격에 대해 깊게 알아보기
어태커의 목적은 그래프를 가능한 최소한으로 조작하여 영향을 받는 타겟 노드에 대한 레이블 예측의 변화를 최대화하는 것입니다. 만약 그래프에 대한 조작의 규모가 크면 쉽게 들키게 됩니다. 따라서 성공적인 공격은 알아차리기 어려운 정도의 변화를 주어 결과를 망가뜨리는 것입니다.
기존 그래프의 인접 행렬을 $A$, 피처 행렬을 $X$라고 할 때 조작된 그래프의 인접 행렬을 $A^\prime$, 피처 행렬을 $X^\prime$으로 두겠습니다. 그래프에 대한 조작은 눈치채기 어려울 정도로 적으므로 $(A^\prime, X^\prime) \approx (A, X)$로 가정하겠습니다. 이때 그래프에 대한 조작은 직접적이거나 간접적일 수 있습니다. 노드의 레이블 $Y$가 있을 때 모델 파라미터 $\theta^\ast$ 는 $A, X, Y$ 에 의해 학습됩니다. 이 파라미터를 가지는 GCN에 의해 예측된 노드 $v$의 레이블을 $c_v^\ast$ 라고 두겠습니다. 어태커는 $A, X, Y$와 학습 알고리즘에 접근할 수 있습니다. 어태커는 위에서 말한 것 처럼 $(A, X)$를 $(A^\prime, X^\prime)$으로 수정할 것입니다. 그러면 $A^\prime, X^\prime, Y$로 학습된 모델 파라미터 $\theta^{\ast\prime}$ 이 있을 것이고 이를 통해 얻은 클래스 레이블 $c_v^{\ast\prime}$과 $c_v^\ast$를 다르게 만드는 것이 어태커의 목적입니다.
타겟 노드 $v \in V$에 대해서 GCN은 기존 그래프에 대해 파라미터를 다음 식으로 학습합니다.
\[\theta^\ast = \arg\min_\theta \mathcal{L}_\text{train} (\theta; A, X)\]그리고 타겟 노드에 대한 예측은 다음 식을 통해 얻어집니다.
\[c_v^\ast = \arg\max_c f_{\theta^\ast} (A, X)_{v, c}\]조작된 그래프에 대해서는 첫 번째 식으로 학습하고 두 번째 식으로 예측을 생성합니다.
\[\theta^{\ast\prime} = \arg\min_\theta \mathcal{L}_\text{train}(\theta; A^\prime, X^\prime)\] \[c_v^{\ast\prime} = \arg\max_c f_{\theta^{\ast\prime}} (A^\prime, X^\prime)_{v, c}\]그러면 조작된 그래프로 인해 얻어지는 예측과 실제 예측의 차이는 다음과 같습니다.
\[\Delta(v; A^\prime, X^\prime) = \log f_{\theta^{\ast\prime}} (A^\prime, X^\prime)_{v, c_v^{\ast\prime}} - \log f_{\theta^{\ast\prime}} (A^\prime, X^\prime)_{v, c_v^\ast}\]어태커는 위 식에서 첫 항을 크게 만들고 두 번째 항을 최소로 만드는 것이 목적이죠. 실제 최적화를 위한 목적함수는 다음과 같습니다.
\[\arg\max_{A^\prime, X^\prime} \Delta(v; A^\prime, X^\prime) \quad \text{subject to } (A^\prime, X^\prime) \approx (A, X)\]이 목적 함수를 최적화하기 위해서는 국소적인 최적화 전략을 반복적으로 적용해야 합니다. 인접 행렬로부터 가장 의심이 되는 원소부터 순서대로 조작을 가합니다. 스코어링 함수로 나타난 로그 확률값에서 가장 큰 차이를 보이는 원소를 골라서 최적화합니다.
실제 실험 결과에 따르면 GNN은 직접적인 적대적 공격에는 약하지만 임의적인 공격이나 간접적인 공격에는 어느 정도 강건합니다.