본 연구는 그래프의 지배수(최소 지배 집합의 크기)를 근사하기 위한 기계 학습 접근 방식을 조사한다. 지배수의 정확한 계산은 NP-hard 문제이므로, 기존 방법은 작은 규모의 문제에만 적용 가능하다. 인접 행렬 표현을 사용하는 컨볼루션 신경망(CNN)과 메시지 전달을 통해 그래프 구조에서 직접 학습하는 그래프 신경망(GNN)의 두 가지 신경망 패러다임을 비교했다. 최대 64개의 정점을 가진 2,000개의 임의 그래프에 대해 GNN은 CNN보다 훨씬 높은 정확도($R^2=0.987$, MAE $=0.372$)를 달성했다($R^2=0.955$, MAE $=0.500$). 두 모델 모두 정확한 해결책보다 상당한 속도 향상을 보였으며, GNN은 거의 완벽한 충실도를 유지하면서 $200\times$ 이상의 가속도를 제공했다. 본 연구 결과는 GNN이 조합 그래프 불변량의 실용적인 대용물임을 보여주며, 확장 가능한 그래프 최적화 및 수학적 발견에 시사점을 가진다.
