본 논문은 대규모 그래프 및 하이퍼그래프에서 $k$-그룹화 문제(예: 컬러링, 파티셔닝)를 해결하는 데 어려움을 겪는 기존의 비지도 학습 기반 신경망 솔버의 한계를 극복하기 위해, 새로운 비지도 학습 기반 조합 최적화 프레임워크인 Deep $k$-grouping을 제안한다. 이를 위해 그래프 및 하이퍼그래프 상의 $k$-그룹화 문제를 모델링하는 새로운 one-hot 인코딩 다항식 비제약 이진 최적화(OH-PUBO) 공식을 제시하고, 대규모 $k$-그룹화 조합 최적화 문제를 위한 GPU 가속 알고리즘을 개발했다. Deep $k$-grouping은 대규모 OH-PUBO 목표 함수의 완화를 미분 가능한 손실 함수로 사용하여 비지도 방식으로 학습하며, GPU 가속 알고리즘을 활용하여 학습 파이프라인을 통합하고, Gini 계수 기반 연속 완화 어닐링 전략을 통해 해의 이산성을 보장하고 지역적 최적값으로의 수렴을 방지한다. 실험 결과, Deep $k$-grouping은 기존 신경망 솔버 및 SCIP, Tabu와 같은 고전적 휴리스틱 알고리즘보다 우수한 성능을 보였다.
