[Study]Chapter 16. Advanced Topics on GNNs

해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.

I. Limitations of GNNs

GNN을 완벽히 정의하면 이웃 구조와 노드 임베딩 사이를 단사하는 함수라고 할 있다.

따라서, 완벽한 GNN은 아래와 같이 두가지 관점에서 설명이 가능하다.

1. 두 노드가 같은 이웃 구조를 가지면 그들은 같은 임베딩을 가짐
2. 다른 이웃 구조를 가지면 다른 임베딩을 가짐

그러나 존재하는 GNN에서는 완벽하지 않아 위의 두 가지 관점에서 문제가 있습니다.

첫번째는 Position-aware¹ task라고 부르는 문제로 해당 노드가 그래프에서 다른 위치에 나타나기 때문에 같은 이웃 구조를 가지더라도 그들에게 다른 임베딩을 배정하고 싶을 수 있습니다.

두번째는 WL-test의 상한선을 얘기한 것처럼 GNN에서는 사이클의 길이를 측정하지 못하는 경우가 있습니다.

Figure 1 : Position-aware Task가 필요한 경우

이러한 두가지 문제는 더 표현력 있는 GNN을 구성함으로써 해결할 수 있습니다.

• Position-aware : 관점 1은 그래프에서 노드의 위치에 기반하여 노드 임베딩을 만든다.
• Identity-aware : 관점 2는 WL test보다 더 잘나타내는 메시지 패싱 GNN을 만든다.

두개의 다른 입력을 분류하여 실패한 모델은 항상 같은 임베딩을 배정하고, 성공한 모델은 다른 임베딩을 임베딩하도록 만드는 방식으로 해결합니다.

여기서 나이브한 해결책은 바람직하지 않습니다. 원핫인코딩 같이 각 노드에 다른 ID를 부여하는 것은 O(N) 크기의 특성 차원이 필요하고 새로운 노드와 그래프를 일반화하지 못하는 문제가 있습니다.

II. Position-aware GNNs

그래프에는 두가지 타입의 작업이 있다.

Figure 2 : (좌) 구조 인식 작업 (우) 위치 인식 작업

• Structure-aware task : 그래프에서 구조적인 역할에 따라 라벨링 됨.
• Position-aware task : 그래프에서 위치에 따라 노드가 라벨링 됨.

GNN은 구조 인식 task는 잘 수행하지만 Position-aware task에서는 구조적인 균형으로 계산그래프가 같아져 실패한다.

1. Anchor

Anchor 노드라는 특정 노드를 더 선택하여 이러한 Position-Aware task를 해결할 수 있다. 이러한 anchor를 많이 사용하면, 노드 위치를 특징화하는 좌표축 역할이 되어 특징화할 수 있다.

Anchor 노드는 단일 노드를 노드들의 집합으로 일반화하는 역할을 맡고 있는데, 모든 노드에서 앵커 집합과의 최단 거리를 계산하여 그래프 상의 노드들 간의 정밀한 위치를 나타낼 수 있습니다.

Figure 3 : Anchor-set distance

2. Position Encoding

이렇게 노드의 위치를 앵커 집합과의 거리로 표현하면 앵커 집합의 차원을 가지는 포지션 인코딩이 만들어집니다.

이렇게 만들어진 위치 정보를 간단하게 노드 특징을 종합할 수 있습니다. 이때 포지션 인코딩의 각 차원은 무작위로 배치된 앵커 집단과의 거리를 나타내는데, 이러한 설계는 각 차원의 배치가 바뀌어도 의미가 변하지 않는다는 뜻입니다.

따라서, 포지션 인코딩을 재배치해도 의미 변환이 없는 permutation-invariant 속성을 유지하도록 특별한 신경망을 사용해야합니다. 이러한 내용의 자세한 부분은 Position-aware GNN¹ 논문에서 더 자세히 언급됩니다.

III. Identity-Aware GNNs

GNN은 구조 인식 작업에서 Node, Edge, Graph의 각 3가지 level에서 다른 입력이지만 같은 계산그래프로 인하여 GNN이 실패하는 케이스가 존재합니다.

Figure 4 : 같은 계산 그래프로 인하여 실패하는 3가지 케이스

1. inductive node coloring

이러한 실패를 해결하기 위해 원하는 노드에 색상을 배정하여 임베딩을 합니다.

Figure 5 : v1에서 파생된 v2와 v3의 위치를 재배치해도 계산 그래프는 같게 유지

위와 같이 각 단계에서는 다른 계산 그래프를 얻게 되므로 성공적으로 해결이 가능하고, Edge-level에서는 노드의 쌍을 구별하는 작업(연결된 노드들의 정보)이 추가하여 해결이 가능합니다. 을 부여한 노드 또는 edge0level 예측을 만들지 않은 노드를 조건부로 다른 노드들의 노드 임베딩을 사용한다

이렇게 노드 색상을 이용한 임베딩 계산에 GNN을 활용하는 방법으로 Heterogenous message passing이 있습니다. 일반적으로 GNN은 같은 메시지와 집계를 모든 노드에 적용하는데, 이러한 방법은 노드 타입에 따른 계산을 적용합니다. 예를들어 ID-GNN은 다른 메시지와 집계 함수를 다른 색상의 노드들에 적용합니다.

Figure 6 : (좌) GNN 주어진 레이어에서 같은 메시지/aggregation을 각 노드에 적용. (우) 주어진 레이어에서 다른 메시지/aggregation을 다른 색상을 가진 노드에 적용

이러한 Heterogenous한 메시지 패싱이 성공한 이유로 두 노드가 같은 계산 그래프 구조를 가지지만 다른 노드 색상을 가지고 있을때, 임베딩 계산을 할때 각 색상에 따른 신경망을 적용하기 때문에 임베딩이 달라지게 되어서 입니다.

또한, ID-GNN이 일반 GNN에서는 불가능한 주어진 노드에서 사이클을 count하는 문제를 해결하기 위해 고안되어서 일반적인 GNN보다 성능이 좋다고 합니다.

ID-GNN-Fast라는 간단한 버전으로 추가된 노드 특성으로 구별되는 정보를 포함(헤테로지니어스한 메시지 패싱이 필요 없다)시키는 것입니다. 각 레이어에서 cycle count를 노드 특성에 추가하여 사용한다. 이러한 방법은 어느 GNN에서도 사용가능하다.

이처럼 ID-GNN은 node, edge, graph level의 task에서의 문제를 해결해 성능 향상을 제공하고, cycle count 부분에서 이러한 성능이 더 잘나타나 WL test보다 더 좋고, 확장성이 뛰어난 방법입니다.

IV. Robustness of GNNs

앞서 GNN의 효과적인 성능을 확인했으나 실세계에 적용하기 충분할까?

Figure 7 : CNN은 적대적인 공격에 취약\(_{vulnerable}\)하다.

Figure 7의 이미지 분야 말고도 이러한 문제는 NLP와 음성처리 분야 등에서도 발생합니다.

위같은 예가 존재하면 적극적인 해킹으로 시도되어 성능이 예상보다 떨어져 실세계에 딥러닝 모델을 안정적으로 배포할 수 없습니다. 따라서, 이에 대항하여 모델을 견고하게 만드는 연구 영역이 필요합니다.

1. Robustness of GNN²

GNN은 공공 플랫폼이나 금전적인 분야(추천 시스템이나 소셜 네트워크, 검색 엔진 등)에서 일반적으로 적용이 됩니다. 따라서, 입력 그래프를 조작하고 GNN의 예측을 해킹하는 사람들이 존재할 수 있습니다.

GNN의 경우에는 이미지, NLP 등과 다르게 위와 같은 예에서 견고할까요?

이에 대한 연구로 준지도 학습으로 노드 분류를 진행하는 GCN 모델을 가정해 적대적인 공격 가능성을 묘사하고, 공격할 GCN 모델(opponent;상대)을 돌아볼 것이며 수학적으로 공격 문제를 최적화문제로 형식화할 것입니다.

이러한 연구를 통해 실증적으로\(_{empirically}\) GCN 예측이 얼마나 취약한\(_{vulnerable}\)지 볼 것입니다.

Figure 8 : Target node : \(t\in V\) 우리가 바꾸고 싶은 label 예측 노드, Attacker node : \(S \subin V\)

• 직접적인 공격

  공격자 노드가 목표 노드 S = {t}가 되는 공격 방식으로 목표 노드의 특성을 수정(웹사이트 내용을 변경), 목표로의 연결을 추가(좋아요 또는 팔로우를 증가시킴), 목표에서 연결을 제거(유저 언팔로우)하는 등의 공격을 포함합니다.

• 간접적인 공격

  목표노드가 공격자 노드에 없을때 $t \notin S$하는 방식으로 공격자 노드 특성을 수정(Hijack 목표의 친구를), 공격자의 연결을 추가(link 생성 ,link farm), 공격자에서 연결을 제거(바람직하지 않은 링크 제거)하는 등의 공격을 의미합니다.

Figure 9 : (좌) 직접적인 공격으로 위에서 아래로 특성 수정, 연결 추가, 연결 제거 (우) : 간접적인 공격 위에서 아래로 수정, 추가, 제거

2. Formulation

그래프 조작이 너무 크면 탐지하기 쉽기 때문에 성공적인 공격은 알아채지 못하게 작게끔 그래프를 조작하는 것입니다. 따라서 공격자의 목적은 조작하는 그래프를 기본적인 그래프와 특징 통계량을 보존하도록 작게하고, 목표 노드의 라벨 예측의 변화를 최대화하는 것입니다.

이러한 목적을 아래와 같이 정의합니다.

\[(A',X') \approx (A,X)\]

실제 그래프는 아래와 같이 학습됩니다.

\[\begin{array}{ll} \theta^* = argmin_{\theta}\mathbb{L}_{train}(\theta;A,X)\\ c^*_v = argmax_cf_{\theta^*}(A,X)_{v,c}\\ \end{array}\]

아래의 GCN은 조작된 그래프에서 학습된다.

\[\begin{array}{ll} \theta^{*'} = argmin_{\theta}\mathbb{L}_{train}(\theta;A',X')\\ c^{*'}_v = argmax_cf_{\theta^{*'}}(A',X')_{v,c}\\ \end{array}\]

이러한 조작 이후의 예측 결과가 아래와 같이 변하기를 원합니다.

\[c^{*'}_v \neq c^*_v\]

Figure 10 : 목표 노드 v의 예측 변화량으로 좌측항에서 새롭게 예측된 클래스의 예측된 로그 확률을 최대화하고,원래의 예측된 클래스의 예측된 확률을 최소화 해야함

최종적으로 목적함수는 아래와 같습니다.

\[\arg\max\limits_{A',X'}\Delta(v;A',X')\]

그러나 위의 목적함수를 최적화하기 위해서 인접 행렬 A’는 이산 개체\(_{discrete object}\)로 경사 기반의 최적화는 사용할 수 없습니다. 따라서, 각 수정된 그래프 A’와 X’에 대하여 GCN을 재학습 해야하고 이는 계산 비용이 매우 높습니다.

Figure 11 : 준지도 학습 노드 분류 GCN을 사용한 paper citation network에서의 적대적인 공격 예제, 목표노드에 5개의 edge를 붙이는 조작을 수행한 이후의 GCN 예측은(직접적인 적대적인 공격) 5번의 재학습 이후의 예측 확률

Figure 12 : direct attack은 가장 강력한 공격이다, 특히 GCN의 성능을 악화하는데 공격안한것과 비교해서 무작위 공격은 적대적인 공격보다 약하다. 간접적인 공격은 direct attack보다 더 어렵다.

1. J. You. Postion-aware Graph Neural Networks, ICML 2019 ↩ ↩²

2. Zügner et al. Adversarial Attacks on Neural Networks for Graph Data, KDD 2018 ↩