조합 최적화(Combinatorial Optimization)를 위한 알고리즘 정렬(Algorithmic Alignment) 하에서의

요약

본 연구는 조합 최적화(Combinatorial Optimization) 작업에서 지식 증류(Distillation)가 성공하기 위한 조건을 알고리즘 정렬(Algorithmic Alignment) 관점에서 분석합니다. 특히 타겟 모델인 그래프 신경망(GNN)의 아키텍처가 해당 문제의 동적 계획법(DP) 알고리즘과 정렬될 때, 증류가 효율적으로 이루어질 수 있음을 이론적으로 입증합니다.

핵심 포인트

• 조합 최적화 작업에서 타겟 모델의 아키텍처와 문제 해결 알고리즘 간의 정렬(Alignment)이 증류 성능의 핵심임
• 타겟 모델이 동적 계획법(DP) 알고리즘과 정렬된 GNN일 경우 증류의 성공 가능성이 높음
• 선형 표현 가설(LRH)을 바탕으로 소스 모델의 풍부함이 증류 효율에 미치는 영향을 분석함
• DP 전이 함수를 의사결정 트리(DT)로 표현하여 증류 문제의 복잡도 파라미터를 공식화함