GAP: 일반화 가능한 근사 그래프 분할 프레임워크

그래프 분할은 그래프의 노드를 균형 잡힌 파티션으로 나누면서 파티션 간의 엣지 절단을 최소화하는 문제입니다. 이 문제의 조합적 특성 때문에 많은 근사해법이 개발되었으며, 다중 수준 방법과 스펙트럼 클러스터링의 변형 등이 포함됩니다. 우리는 딥 러닝 접근 방식을 사용하여 그래프 분할에 적용할 수 있는 일반화 가능한 근사 분할 프레임워크인 GAP를 제안합니다. 우리는 분할 목적을 나타내는 미분 가능한 손실 함수를 정의하고 역전파를 사용하여 네트워크 매개변수를 최적화합니다. 그래프마다 최적화를 다시 수행하는 기존 방법들과 달리, GAP는 일반화 능력을 갖추고 있어 추론 시에도 미처 보지 못한 그래프에서 효과적인 파티션을 생성하는 모델을 학습할 수 있습니다. 또한, 그래프 표현을 학습하면서 분할 손실 함수와 함께 공동으로 최적화하기 때문에 GAP는 다양한 그래프 구조에 쉽게 조정될 수 있습니다. 우리는 GAP의 성능을 다양한 크기와 구조의 그래프, 예를 들어 널리 사용되는 머신 러닝 모델(예: ResNet, VGG, Inception-V3)의 그래프, 무척도 그래프(scale-free graphs), 그리고 임의 그래프(random graphs)에서 평가하였습니다. 실험 결과, GAP는 기존 방법과 경쟁력 있는 파티션을 생성하면서 최대 100배 더 빠른 속도를 보였으며, 미처 보지 못한 그래프에도 일반화되는 것으로 확인되었습니다.