조합 최적화를 위한 그래프 신경망과 에너지적 캐비티 방법
Graph neural networks and the energetic cavity method for combinatorial optimization
한국어 초록
본 연구는 이징 모델의 근사 바닥 상태를 찾기 위한 그래프 신경망(GNN)의 활용을 연구한다. 많은 조합 최적화 문제가 결합 상수와 장을 적절히 선택하면 이징 모델로 정식화될 수 있으므로, 이러한 바닥 상태를 효율적으로 찾는 것은 폭넓은 중요성을 지닌다. 이러한 문제를 정확히 푸는 것은 어렵지만 좋은 휴리스틱 방법이 많이 존재한다. 이러한 휴리스틱의 한 계보는 평균장 근사에서 출발한다. 한 접근법은 적절히 정의된 행렬의 최대 고유벡터를 사용하고, 다른 하나는 에너지적 캐비티 방법으로도 알려진 min-sum 알고리즘이다. 수정하지 않은 GNN은 이 두 방법보다 성능이 나쁘다. 본 연구는 이러한 휴리스틱을 통합하도록 GNN에 작은 수정을 가하는 것을 고려하였고, 이것이 성능을 상당히 향상시킴을 확인하였다. 수정된 접근법은 다른 딥러닝 접근법보다 훨씬 강력하지만, 동일한 계산 비용에서는 시뮬레이티드 어닐링이 대체로 그만큼 우수함을 여전히 발견하였다.
원문 초록
We study the use of graph neural networks (GNNs) for finding approximate ground states of Ising models. Efficiently finding these ground states is of broad significance because many combinatorial optimization problems can be formulated as an Ising model with the appropriate choice of couplings and fields. Exactly solving these problems is hard but there are many good heuristic methods. A lineage of these heuristics build from mean-field approximations: one approach uses the leading eigenvector of an appropriately defined matrix, another is the min-sum algorithm, also known as the energetic cavity method. Without modification, GNNs perform worse than both of these methods. We consider small modifications to the GNN to incorporate these heuristics and find that this considerably improves performance. While the modified approach is much stronger than other deep learning approaches, we still find that simulated annealing is generally as good for the same computational cost.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.07456v2제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.