[ICML 2022] Part 3: 신경 조합 최적화(Neural Combinatorial Optimization) 연구 - LG AI Research 블로그

조합 최적화(Combinatorial Optimization, CO)는 이산 공간에서 가능한 해를 찾는 문제로, 대표적으로 **외판원 문제(TSP)**가 있다. 하지만 많은 CO 문제가 NP-hard 특성을 가져 다항 시간 내에 해를 찾는 것이 어렵다.

최근에는 이를 해결하기 위해 딥러닝을 활용한 신경 조합 최적화(NCO) 연구가 활발히 진행되고 있다. 기존 연구들은 주로 노드 수가 100개 미만인 작은 규모의 그래프를 대상으로 했으나, 실제 환경에서는 10만 개 이상의 노드를 가진 대규모 데이터 처리가 필요하다.

LeNSE는 이러한 확장성 문제를 해결하기 위해 제안된 모델이다. 특정 문제에 국한된 휴리스틱 알고리즘 대신, 전체 그래프보다 작은 **서브그래프(Subgraph)**를 효율적으로 찾아내어 탐색 공간을 줄이는 방식을 사용한다.

LeNSE는 크게 두 가지 핵심 단계로 구성된다:

• 차별적 서브그래프 표현 학습(Learning a discriminative subgraph representation): 최적해를 포함할 가능성이 높은 서브그래프를 식별한다.
• 서브그래프 탐색(Subgraph navigation): 예측된 가능성을 바탕으로 더 나은 서브그래프를 찾도록 수정한다.