[논문] Attacking Graph-based Classification via Manipulating the Graph Structure

Binghui Wang and Neil Zhenqiang Gong, "Attacking Graph-based Classification via Manipulating the Graph Structure", CCS '19

 

0. Abstract

 

본 논문에서는 그래프 기반의 classification 모델을 대상으로 공격을 한다. 그리고 제목에서 알 수 있듯이 공격은 그래프의 구조를 변경 (즉, edge의 연결구조를 변경) 함으로써 수행한다.

 

이전의 이미지 도메인에서 자주 활용되던 adversarial attack을 그래프 도메인에 적용시킨 초기 논문 중 하나로, 개인적으로 굉장히 좋아하는 논문이기도해서 간단하게 정리해보겠다...

 

 

1. Introduction

 

그래프 기반의 classification 모델은 malware detection, 소셜 네트워크에서의 fake (Sybil) user detection 등에 자주 사용된다. 그 중에서도 특히 일부 노드의 레이블 정보와 그래프 구조만을 가지고 classification을 수행하는 (1) collective classification, 딥러닝을 이용하는 (2) GNN 방식이 주로 사용되고 있다.

 

본 논문에서는 가장 유명한 collective classification 방식 중 하나인 LinLBP (Linearized Loopy Belief Propagation) 방식의 기법을 대상으로 공격을 진행하고, 공격된 그래프를 GNN 모델에도 transfer attack 하는식으로 진행한다.

 

 

2. Background

 

본 절에서는 앞서 말한 대표적인 collective classification 방식 중 하나인 LinLBP 기반의 classfication 모델에 대하여 설명하겠다.

 

우선 그래프의 구조가 주어져있다고 가정해보자 (node + edge).

 

그리고 방어자는 전체 노드 중 일부 노드의 레이블을 알고 있다고 가정해보자. 예를 들어 소셜 네트워크에서 정상 계정과 허위 계정을 분류하고자 할 때, 방어자가 전체 수많은 노드 중에서 확실한 정상 계정 100개와 확실한 허위 계정 100개를 알고 있다고 가정해보겠다.

 

그렇다면, 아래 [그림 1]과 같이 해당 노드에 prior score를 할당해준다. 일반적으로 theta 값은 0.5를 많이 할당하므로, 위의 예시에 따르게 되면, 확실히 알고있는 정상 노드에는 +0.5점을, 그리고 확실히 알고있는 허위 노드에는 -0.5점을, 나머지 대부분의 노드에는 0점을 부여하게 되는 것이다.

 

[그림 1] Prior score assignment

 

 

이제 부여한 prior score 를 기반으로 propagation을 진행한다. 아래 [그림 2] 와 같이 propagation을 진행하게 되는데, 저기서 q가 앞서 할당한 prior score 벡터이고, A가 그래프의 연결관계를 나타내는 adjacency matrix, W는 그냥 가중치 matrix인데 무시해도 된다.

 

[그림 2] Posterior score computation

 

수식은 복잡해보이지만, 결국 부여한 prior score 를 인접한 노드들이 나눠먹는 형식으로 돌아가게 된다. 예를들면, 확실히 알고있는 허위 노드 근처에 있는 노드들은 높은 양(+)의 점수를 얻게 되고, 정상 노드 근처에 있는 노드들은 낮은 음(-)의 점수를 얻게 된다.

 

이렇게 propagation을 여러번 반복하게 되고, 최종적으로 얻는 점수가 posterior score 이며, 이 값이 양수이면 최종적으로 허위노드, 음수이면 최종적으로 정상노드로 판단하는 것이다.

 

다양한 collective classification 방식들도 기본적으로 1) prior score 계산, 2) posterior score 계산 두 단계를 거친다. 이러한 collective classification 방식들이 유용한 이유는 기본적으로 허위 계정은 허위계정끼리, 정상 계정은 정상계정끼리 연결관계를 가진다는 가정에서 출발한 것이다.

 

 

3. Attack Design

 

그렇다면 지금부터 본격적으로 이 논문에서 어떻게 LinLBP 방식을 대상으로 공격했는지 알아보자.

 

우선, 공격자의 목표는 그래프에서 일부 노드의 classification 결과를 positive(허위계정) 에서 negative(정상계정)으로 바꾸는 것이다. 이렇게 함으로써 공격자는 방어자의 방어를 우회할 수 있다. 여기서 공격자가 목표로 삼는 노드를 target nodes라고 한다.

 

이제 공격자의 목표를 수식으로 나타내보면, 아래 [그림 3]과 같다. (참고로 v를 target nodes로 나타낸다.)

 

[그림 3] Attacker's objective function

 

우선 C 행렬은 임의의 노드 u, v 사이의 edge 를 조작할 때 드는 cost 이고, B 행렬은 original graph와 manipulate 하려는 graph 사이의 변화를 나타낸다.

 

예를들어, original graph에서 노드 u와 v 사이에 엣지가 존재하고 B_u,v 의 값이 1이라면, 공격자는 해당 엣지를 제거하려고 한다. 반대로 original graph에서 노드 u와 v 사이에 엣지가 존재하지 않고 B_u,v 의 값이 1이라면, 공격자는 해당 엣지를 새로 연결하려고 하는 것이다.

 

결국 행렬 B와 C를 element-wise 곱하게 되면, 공격하는데 드는 총 cost 를 나타내고, 공격자는 이를 최소화 하려고 하므로 objective function에서 min 을 적용한 것이다.

 

추가로, 공격이 성공하려면 target nodes들에 대해서 positive -> negative 로 변해야 하므로, FNR = 1이라는 제한조건 이 붙는다. 

마지막으로, 공격자는 target node당 공격에 필요한 edge 조작개수를 K로 제한시켰고, 이를 마지막 제한조건으로 붙여놓았다.

 

[그림 3]의 수식에서 볼 수 있듯이 여러가지 제한 조건이 있으므로, 해당 수식을 바로 푸는 것은 불가능하다. 따라서 [그림 3]의 수식을 [그림 4]의 수식으로 풀어쓸 수 있다.

 

[그림 4] Attacker's objective function2

 

이렇게 함으로써 FNR=1 의 제한조건을 주번째 항에 lagrangian multiplier 를 추가하여 붙여주었고, collective classification 의 propagation에 활용되는 iteration을 변수 t를 활용하여 나타낼 수 있다.

 

전체적으로 [그림 4]의 수식을 해석해보면, 공격자는 공격에 필요한 총 cost 를 최소화하려고 하고 (첫번째 항) 동시에 공격 성공률을 최대로 높히려고 한다 (두번째 항).

따라서 만약 lambda의 값이 커지만, 공격성공률에 집중을 하게 되므로 공격에 필요한 총 cost가 늘어나고, lambda 의 값이 작아지만, 공격에 필요한 총 cost는 최소화되지만, 공격 성공률은 조금 낮아지게 될 것이다.

 

이제 해당 [그림 4]의 수식을 PGD 기반의 공격으로 풀어내면 최종적으로 그래프 구조의 변화를 나타내는 B 행렬을 구할 수 있다.

조금 더 자세한 풀이는 논문을 참조하길 바란다..

 

 

4. Evaluation

 

이제 해당 공격이 실제로 통하는지 알아보자. 저자들은 [그림 5]와 같이 총 4개의 데이터셋에 대해서 공격을 수행했다.

 

[그림 6] Attack Result

 

공격 결과는 [그림 6]과 같다. 표에 있는 RAND, CC, CLOSE 는 target node를 선택하는 방법이고, Equal, Uniform, Categorical은 cost matrix에 값을 할당시키는 방법을 의미한다. (그닥 중요한건 아니므로 설명하지 않고 넘어가겠다.)

 

전체적인 공격 성공률을 보면 (FNR column), 대부분의 경우에서 공격 성공률 90% 내외를 달성하였고, 유일하게 Facebook dataset에서 RAND 일 경우에만 공격성공률이 60%대를 나타내었다.

 

이는 실제로 앞서 소개한 공격이 효과적이었음을 나타낸다.

 

또 한가지 특징은 # Add / # Del column에서 볼 수 있듯이, 공격자는 대부분 공격할 때 엣지를 추가하는 경향이 있고, 공격에 엣지를 제거하는 경향은 비교적 낮다는 것이다.

 

 

앞서 Intro에서 설명했듯이 graph classification에는 1) collective classification과 2) GNN 방식이 있다. 지금까지 설명한 공격은 collective classification을 가정하고 한 공격이다.

공격 과정에서 optimization problem을 풀 떄, GNN을 대상으로 풀면 너무 연산이 복잡해 거의 불가능하므로, 저자들은 우선 collective classification 을 대상으로 한 공격된 그래프를 가지고 GNN으로 classification을 적용하는, 일명 transfer attack을 수행해보았다.

 

[그림 7] Attack Transferability

 

그 결과 [그림 7]에서 볼 수 있듯이 GCN을 포함한 다양한 GNN classification 모델에서 대부분 50%를 넘는 비교적 높은 공격 성공률을 보인 것을 확인할 수 있다.

 

게다가, [그림 8]에서 볼 수 있듯이 대표적인 GNN 대상 공격인 Nettack에 비해서도 높은 공격 성공률과, 압도적으로 짧은 공격 시간을 달성하였다.

 

[그림 8] Comparing with Nettack

 

 

5. 마치며

 

논문에서는 오늘 내가 소개한 내용보다 훨씬 많은 내용들이 들어있다. 개인적으로 좋아하는 연구자들이고, 좋아하는 논문이라서 다들 꼭 읽어보는걸 추천한다.