LG AI Research 253: 신경 조합 최적화 연구 동향

조합 최적화(Combinatorial Optimization, CO)는 실행 가능한 해의 집합이 이산적으로 정의되는 수학적 최적화 분야다. 대표적인 예로 외판원 문제(TSP)가 있으며, 많은 문제가 다항 시간 내에 해를 보장할 수 없는 NP-hard에 해당한다.

최근에는 이러한 문제를 효과적으로 풀기 위해 딥러닝을 활용하는 Neural Combinatorial Optimization (NCO) 분야가 활발히 연구되고 있다. 기존 연구들은 주로 100개 이하의 노드를 가진 작은 그래프에서 실험했으나, 현실 세계의 대규모 데이터를 처리하기 위한 Scalability 개선이 필수적이다.

LeNSE는 대규모 그래프에서 효율적으로 조합 최적화 문제를 풀기 위한 방법론이다. 이 모델은 기존의 휴리스틱 알고리즘을 그대로 사용하되, 솔버가 빠른 속도로 결과를 낼 수 있는 효율적인 Subgraph를 찾는 것을 목표로 한다.

LeNSE의 핵심 메커니즘은 다음과 같다:

• Discriminative Subgraph Representation: GraphSAGE와 k-pooling layer를 사용하여 optimal solution을 포함할 가능성이 높은 subgraph의 표현을 학습한다. 이때 InfoNCE loss를 활용해 샘플 간의 상호 정보를 최대화한다.
• Subgraph Navigation: 강화 학습(Reinforcement Learning)을 활용하여 임의로 초기화된 subgraph를 더 나은 subgraph로 수정하며 최적의 해를 찾아간다.