본 문서에서는 데이터 마이닝 분야의 The Web Conference (WWW) 2022 학회에서 발표될 Model-Agnostic Augmentation for Accurate Graph Classification 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다.
- Title: Model-Agnostic Augmentation for Accurate Graph Classification
- Authors: Jaemin Yoo, Sooyeon Shim, and U Kang
- Conference: The Web Conference (WWW) 2022
Model-Agnostic Graph Augmentation
데이터 증강(data augmentation)은 기계학습 분야에서 모델의 성능을 향상시키기 위해 널리 사용되는 방법 중 하나입니다. 데이터를 통해 훈련하는 모델의 일반화 성능은 일반적으로 훈련 데이터의 양에 비례한다고 알려져 있습니다. 따라서, 주어진 데이터를 조금씩 변형하거나 여러 데이터를 조합하는 방식으로 훈련 데이터의 양을 늘리면 모델 구조의 수정 없이도 일반화 성능을 개선할 수 있습니다. 본 연구는 여러 데이터 도메인 중 그래프(graph) 분야에 집중합니다. 즉, 여러 개의 정점과 간선으로 구성된 그래프를 개별적인 데이터 단위로 취급하여, "데이터 증강을 위해 어떻게 하면 효율적으로 그래프 구조를 변형할 수 있을까?"라는 질문에 답하고자 합니다.
그래프 증강 기법은 크게 모델 독립적인(model-agnostic) 기법과 모델 종속적인(model-specific) 기법으로 나눌 수 있습니다. 모델 독립적인 기법은 목표 모델의 특성과 무관하게 잘 동작하는 증강 알고리즘을 만드는 것을 목표로 합니다. 따라서, 모델 독립적인 기법은 주어진 그래프가 가지고 있는 구조적 특성을 변경하는 데 집중합니다. 반면, 모델 종속적인 기법은 목표 모델이 정해져 있다고 가정하고 목표 모델의 약점을 보완하는 방향으로 증강 알고리즘을 설계합니다. 따라서, 모델 종속적인 기법은 각 모델이 만드는 매니폴드(manifold) 공간을 풍부하게 만들기 위해 노력합니다. 모델 독립적인 기법에 대한 연구는 모델 종속적인 기법에 비해 비교적 덜 이루어졌는데, 그 이유는 목표 모델이 정해지지 않은 상황에서 그래프 증강을 수행하는 것이 근본적으로 정답이 없는 문제이기 때문입니다.
본 연구는 모델 독립적인 그래프 증강 알고리즘 두 개를 제안합니다. 특히, 그래프 분야에서 연구되고 있는 다양한 문제 중 그래프 분류(graph classification) 문제에 집중하여 분류 모델의 성능을 최대화하는 것을 목표로 합니다. 그림 1은 모델 독립적인 그래프 증강 알고리즘의 동작 방식을 간단히 보여줍니다.
 |
| 그림 1. 모델 독립적인 그래프 증강 알고리즘의 동작 방식. |
Satisfying Desired Properties
그래프 증강 문제에서 가장 어려운 점 중 하나는 주어진 데이터의 의미 정보(semantic information)를 정의하기 어렵다는 것입니다. 데이터 증강 알고리즘은 주어진 데이터의 의미 정보를 훼손하지 않는다는 가정 하에서만 유효합니다. 예를 들어 주어진 그림을 개와 고양이로 분류하는 문제를 푼다고 할 때, 개 그림을 코끼리로 바꾸는 방식의 변형은 데이터 의미 정보를 변경한다는 점에서 유효한 증강 기법이 아닙니다. 이미지 분야에서는 이러한 의미 정보 변경이 쉽게 정의되는 한편, 그래프 분야에서는 그래프의 어떤 부분이 의미 정보를 생성하거나 결정하는지 알기 어렵습니다. 따라서, 의미 정보를 보존하는 그래프 증강 기법을 설계하는 것은 그 자체로 어려운 문제일 뿐 아니라, 의미 정보의 보존 여부를 판단하는 것조차 쉽지 않습니다.
본 연구에서는 의미 정보 보존을 통한 효과적인 그래프 증강 알고리즘을 설계하기 위해 그림 2와 같은 다섯 개의 목표 속성(desired properties)을 제안합니다. 이 다섯 개의 속성은 주어진 그래프의 의미 정보 변경을 최소화하면서 데이터 증강의 정도를 최대화하기 위해 설계되었습니다. 간단히 요약하자면 P1) 그래프 크기의 기댓값 보존, P2) 그래프의 연결성 보존, P3) 정점 피처 변형, P4) 간선 정보 변형, P5) 증강 알고리즘의 선형 복잡도 정도로 설명할 수 있습니다. P1와 P2는 그래프 속성 보존을 위해, P3과 P4는 그래프 증강 정도 최대화를 위해, 그리고 P5는 대용량 그래프에 적용하기 위해 제안되었습니다. 경쟁 알고리즘의 경우 대부분의 속성을 만족하지 못하는 반면, 본 연구에서 제안하는 두 개의 알고리즘은 모든 속성을 만족하는 것을 확인할 수 있습니다.
 |
| 그림 2. 본 연구에서 목표로 하는 다섯 개의 목표 속성. |
Proposed Methods: NodeSam & SubMix
본 연구에서는 위에서 제안한 목표 속성을 모두 만족하는 두 개의 그래프 증강 알고리즘인 NodeSam(Node Split and Merge)과 SubMix(Subgraph Mix)를 제안합니다. NodeSam은 주어진 그래프에 Split과 Merge라는 정반대의 변형 함수를 동시에 적용함으로써 안정된 그래프 구조 변형을 수행합니다. 반면, SubMix는 서로 다른 라벨을 갖는 여러 그래프의 세부 구조를 결합함으로써 보다 큰 규모의 그래프 변형을 수행합니다. 따라서, 그래프 크기가 비교적 작으면서 세부적인 구조를 보존해야 하는 상황에서는 NodeSam이, 비교적 큰 그래프에 대해 규모 있는 증강을 수행하는 상황에서는 SubMix가 적합하다고 볼 수 있습니다.
NodeSam의 동작 방식은 그림 3으로 요약할 수 있습니다. 먼저, 하나의 정점을 두 개의 연결된 정점으로 치환하는 Split 연산을 수행한 뒤, 이 결과를 바탕으로 추가 간선을 삽입하는 Adjust 연산, 그리고 그래프에서 임의의 연결된 두 정점을 골라 하나의 정점으로 치환하는 Merge 연산을 적용합니다. Split 연산은 항상 하나의 간선을 추가하는 한편, Merge 연산은 선택된 두 정점이 삼각형을 이룰 경우 많은 수의 간선을 제거할 수 있다는 불균형을 가지고 있습니다. 따라서, Adjust 연산은 Merge 연산이 제거할 것으로 기대되는 간선의 수를 미리 계산한 뒤 이와 같은 수의 간선을 미리 삽입함으로써 NodeSam 알고리즘이 편항되지 않은(unbiased) 데이터 변형을 수행하도록 합니다.
 |
| 그림 3. NodeSam 알고리즘의 동작 방식. |
SubMix 알고리즘의 동작 방식은 그림 4로 요약할 수 있습니다. 그림 4의 위쪽에 묘사된 CutMix 알고리즘은 이미지 분야에서 널리 쓰이는 데이터 증강 기법으로, 주어진 이미지의 일부분을 다른 이미지로 완전히 치환하는 방식으로 동작합니다. 생성된 이미지는 어색하게 느껴지지만 모델의 훈련 관점에서는 효과적인 데이터 증강 기능을 수행합니다. SubMix 알고리즘은 이를 그래프 분야로 확장한 알고리즘으로서 먼저 두 개의 그래프에서 각각 시드(seed) 정점을 선택한 뒤 이를 바탕으로 랜덤 워크(random walk) 기반 알고리즘을 통해 서브그래프를 선택하고, 선택된 서브그래프를 서로 교체하는 방식으로 동작합니다. NodeSam 알고리즘과 비교했을 때 가장 큰 장점은 그래프 증강의 정도가 훨씬 더 크다는 것입니다.
 |
| 그림 4. SubMix 알고리즘의 동작 방식. |
Experiments
본 논문은 아홉 개의 실제 데이터에 대한 실험을 통해 제안하는 방법인 NodeSam 및 SubMix와 그래프 증강을 위한 기존 방법을 비교합니다. 그림 5는 Graph Isomorphism Network (GIN) 분류기를 사용했을 때의 분류 정확도 비교 결과를 나타냅니다. 각 데이터셋에서의 순위는 조금씩 다르지만, 평균 정확도 및 평균 랭크를 기반으로 했을 때 제안하는 두 개의 알고리즘이 경쟁 상대와 비교했을 때 가장 뛰어난 결과를 보여주고 있습니다. NodeSam 알고리즘의 경우 높은 안정성으로 인해 평균 정확도가 가장 높은 반면, SubMix 알고리즘의 경우 풍부한 증강을 통해 가장 높은 평균 랭크를 달성한다는 것이 차이점입니다.
 |
| 그림 5. 제안 알고리즘과 기존 그래프 증강 기법과의 비교. |
그림 6은 NodeSam 및 SubMix 알고리즘의 동작 결과 주어진 그래프에 포함된 간선 수가 얼마나 변하는지를 상자 그림(box plot)을 통해 보여줍니다. 두 알고리즘 모두 훈련 데이터의 양을 늘리는 측면에서 충분한 구조 변경을 수행하는 한편, 모든 경우에 중간값이 가운데에 위치함으로써 편향되지 않은 구조 변형을 수행한다는 것을 보여주고 있습니다. 이는 두 알고리즘 모두 본 연구에서 제시하는 속성 중 P1과 P4를 동시에 만족한다는 것을 의미합니다. 동시에, Submix 알고리즘의 변형 정도가 NodeSam 알고리즘의 구조 변형 정도보다 크다는 점에서 NodeSam 알고리즘에 비한 SubMix 알고리즘의 상대적인 특성을 잘 보여줍니다.
 |
| 그림 6. 제안하는 알고리즘의 그래프 간선 수 변화 정도. |
Conclusion
본 문서에서는 The Web Conference (WWW) 2022에서 발표될 예정인 Model-Agnostic Augmentation for Accurate Graph Classification 논문을 소개하였습니다. 해당 논문은 효과적인 그래프 증강을 위한 다섯 개의 목표 속성을 제시한 뒤, 이를 모두 만족하는 두 가지 알고리즘인 NodeSam과 SubMix를 제시하였습니다. 두 알고리즘은 모델 독립적인 방식으로 동작하는 기법으로서 목표 모델 및 문제에 상관없이 그래프 증강을 수행할 수 있다는 장점을 갖습니다. 아홉 개의 실제 데이터셋에 대한 그래프 분류 실험 결과 두 알고리즘 모두 기존의 증강 기법에 비해 일관성 있게 더 높은 분류 정확도를 보여주었습니다.
그래프 데이터는 소셜 네트워크, 리뷰 그래프, 화합물 그래프 등 다양한 형태로 실세계에 존재합니다. 그래프 증강 문제는 훈련 데이터의 양을 늘려 그래프 신경망 모델의 일반화 성능을 향상시킨다는 측면에서 다양한 그래프 기반 문제에 적용될 수 있습니다. 본 논문에서 다룬 그래프 분류 문제의 경우 소셜 네트워크 내에 존재하는 그룹의 특성을 분류하는 상황이나 여러 분자로 이루어진 화합물의 특성을 예측하는 등의 문제에 널리 적용될 수 있습니다. 또한, 그래프 내 각 정점의 클래스를 분류하는 정점 분류 문제나 그래프에 생성될 새로운 간선을 예측하는 링크 예측 등의 문제에도 본 연구에서 제시하는 증강 알고리즘이 사용될 수 있습니다. 자세한 내용은 논문에서 확인하실 수 있습니다.