그래프 채색을 위한 대조적 신경 알고리즘 추론 (Contrastive Neural Algorithmic Reasoning for Graph

그래프 채색 (Graph coloring)은 가능한 한 적은 수의 색상을 사용하여 인접한 노드들이 서로 다른 색을 갖도록 그래프의 노드에 색을 할당하는 것을 목표로 합니다. 본 연구에서는 단색 에지 (monochromatic edges)의 수를 최소화하면서 최대 $k$개의 색상을 사용하는 근사 $k$-채색 (approximate $k$-coloring)을 연구합니다. 이 문제는 그래프 이론의 핵심이며 스케줄링 (scheduling) 및 자원 할당 (resource allocation)과 같은 분야에서 응용됩니다. 최근의 비지도 학습 기반 GNN (Graph Neural Network) 접근 방식은 각 인스턴스를 직접 최적화하므로, 그래프의 크기와 분포에 따른 일반화 (generalization)가 불가능합니다. 대신, 우리는 동일한 색상의 노드 임베딩 (embeddings)은 정렬되고 인접한 노드의 표현 (representations)은 서로 다른 방향으로 밀려나도록 하여, 전이 가능한 채색 기하학 (transferable coloring geometry)을 학습하는 대조 학습 (contrastive learning) 프레임워크를 제안합니다. 우리는 유계 크기 (bounded-size) 그래프에 대한 결과적인 모집단 목적 함수 (population objective)를 분석합니다. 단위 노름 (unit-norm) 임베딩의 경우, 그 최적해 (optima)가 선형 프로토타입 (line-prototype) 구조를 가짐을 보여줍니다. 즉, 동일한 색상의 노드 표현은 공유된 1차원 부분 공간 (subspace)으로 붕괴되며, 에지는 직교하는 (orthogonal) 부분 공간들을 연결합니다. 이러한 기하학적 구조는 지도 학습 (supervised setting) 환경에서 정지 조건 (stationarity conditions)을 생성하며, 균형 잡힌 채색 (balanced-coloring) 가정하에 투영된 하강법 (projected subgradient dynamics)에 의해 보존됩니다. 정규화되지 않은 변형 (unnormalized variant)에서는 경사 하강법 (gradient descent)이 몫 그래프 (quotient-graph) 하드 마진 (hard-margin) 문제에 의해 지배되는 최대 마진 편향 (max-margin bias)을 가집니다. 합성 (synthetic) 및 실제 세계 그래프에 대한 실험 결과, 대조적 GNN 인코더가 효과적으로 일반화되고 충돌이 적은 채색을 생성하며, 탐욕적 (greedy) 접근 방식과 대등하거나 때로는 이를 능가함을 보여줍니다.