상삼각 기반 유전 알고리즘을 활용한 그래프 구조 데이터에서의 적대적 공격 = Adversarial Attacks in Graph Structured Data Using Genetic Algorithms with Upper Triangular

국문 초록 (Abstract)

그래프 신경망(Graph Neural Network, GNN)은 일반적인 트래픽 데이터 나 통계데이터가 아닌 비정형 데이터에 속해있는 지점들의 관계를 모델링 할 수 있는 중요 개념 중 하나이다. 하지만 최근 발간된 논문들에서 GNN 은 그래프 구조가 미세하게 변경될 경우 모델이 비정상적으로 취약해져 분류기에 쉽게 오분류를 일으킨다는 점을 보이고 있다. 이러한 취약성은 그래프 데이터를 공격자가 쉽게 조작이 가능하고 탐지를 우회할 경우 더 큰 위험으로 이어지기 때문에, GNN에 대한 적대적 공격은 중요한 연구 주제로 주목받고 있다. 그러나 그래프에 대한 적대적 공격은 공격 공간(search space)이 매우 커 무향 그래프의 대칭성 유지, 공격 예산(budget) 제약 등의 조건들을 동 시에 만족해야 하기 때문에 네트워크 트래픽이나 기타 데이터에 사용되는 탐지는 그래프 데이터에 대해 한계를 보인다. 본 연구는 이러한 문제를 해결하기 위해 그래프 인접행렬의 상삼각 영 역(upper-triangular matrix)을 유전 알고리즘(Genetic Algorithm, GA)의 염 색체로 인코딩하는 그래프 적대적 공격 프레임워크를 제안한다. 제안하는 방법은 그래프 구조 데이터를 상삼각 형태로 인코딩하여, 무향 그래프가 가지는 대칭성을 보존하면서, 유전 알고리즘이 불필요한 탐색을 수행하지 않고 최적의 해를 수행할 수 있도록 유도한다. 또한 본 연구에서는 그래프 도메인 구조에 적합한 유전 알고리즘 단계 를 구축하여 해당 과정에서 우수한 성능을 보이는 해를 최적화하는 방식 을 구축하였다. 교차(Crossover)단계에서는 부모 그래프의 상삼각 구조 유 전자를 기반으로 공격 대상 노드 주변을 교환하는 방식을 활용하였고 변 이(Mutation) 단계에서는 Degree-Preserving Rewiring을 활용하였다. 또한 유전 알고리즘에서 정의하는 해를 분류기 뿐만 아니라 은밀성도 고려하는 피트니스 함수를 구축하여 최적의 공격을 수행하도록 유도했다. 이와 별도로 유전 알고리즘과 유사하게 최적의 해를 추구하는 강화학습 에 대한 내용도 본 연구에 포함되어 있다. 본 연구에서 제안한 강화학습 방법은 계층적 Q-Learning으로 4단계에 걸쳐 그래프에 대한 적대적 공격 을 수행하는 프레임워크도 제시한다. 1단계에서는 공격할 지역 선택, 2단 계는 지역 속 타겟 선택, 3단계는 공격 수단 선택, 마지막으로 4단계는 타겟 노드와 연결하거나 연결을 끊을 노드 선택 총 4단계로 구성하였다. 실험에서는 Cora-ML, Citeseer 두 가지 데이터 셋을 활용하여 실험을 진행하였고 공격할 분류기는 2계층 Graph Convolutional Network(GCN)를 선택하였다. 공격 제한은 타겟 근처 2-hop거리 내로 제한했으며 간선 수 또한 공격 예산(budget)을 두어 공격 수 또한 제한하였다. 실험결과, 본 연구에서 제안한 상삼각 기반 유전 알고리즘 공격은 기 존 연구에서 제안한 모델들보다 일부 데이터 셋에서 더 좋은 성능을 보이 거나 비슷한 수준의 공격 수준을 보였다. 반면 계층적 강화학습 모델은 아직까지 본 논문에서 제안한 유전 알고리즘 모델에 비하면 다소 낮은 성 능을 보였다. 본 연구는 그래프 데이터에 대한 적대적 공격을 유전 알고리즘 기반 탐 색 문제로 정의하고, 상삼각 인코딩을 통해 그래프 구조에 대해 효율적으 로 유전자를 구축하여 최적의 공격을 수행할 수 있는 것을 보여주었다는 점에서 의의가 크다. 또한 유전 알고리즘 뿐만 아니라 계층적 강화학습에 서도 모델을 제안함으로써 그래프 구조 데이터에 대해 최적의 값을 수행 헐 수 있다는 가능성을 보여주었다. 해당 논문은 그래프 구조 데이터에서 최적의 값을 찾는 알고리즘인 유전알고리즘이나 강화학습 모델이 효율적 이라는 것을 보여주며, 해당 분야의 연구에 대해 기여할 것으로 보인다.

목차 (Table of Contents)

• 제1장 서 론 1
• 제2장 관련 연구 6
• 2.1 그래프 신경망(Graph Neural Network)의 개념 및 구조적 취약성 6
• 2.2 유전 알고리즘(Genetic Algorithm)의 개념 및 그래프 구조 최적화에서의 가능성 7
• 2.3 강화학습(Reinforcement Learning) 및 계층적 강화학습(HRL)의 개념 9
• 2.4 그래프 구조에 대한 적대적 공격 연구 동향 10
• 제3장 제안하는 유전 알고리즘 프레임워크 14
• 3.1 상삼각을 활용한 염색체 구현 15
• 3.2 피트니스 함수 구현 16
• 3.3 Selection: Stochastic Universal Sampling과 elitism 18
• 3.4 Crossover: Uniform Crossover 19
• 3.5 Mutation 19
• 제4장 유전 알고리즘과 비교하기 위한 계층적 강화학습 21
• 4.1 Q1 step-Region Selection 21
• 4.2 Q2 step-Node Selection 22
• 4.3 Q3 step-Attack Type Selection: Add/Delete 23
• 4.4 Q4 Counterpart Node Selection 23
• 제5장 실험결과 24
• 5.1 실험 환경 및 데이터셋 24
• 5.2 GCN 분류 성능 감소 24
• 5.3 실험 정리 29
• 제6장 결론 및 향후 연구 32
• 참고문헌 34