높은 실현 개수를 갖는 최소 강성 그래프 학습

요약

본 논문은 여러 개의 실현체를 가질 수 있는 높은 실현 개수를 갖는 최소 강성 그래프를 찾는 문제를 다룹니다. 기존의 전수 탐색 방식은 후보 그래프가 초지수적으로 증가하고 평가 비용이 높아 비실용적입니다. 이에 저자들은 헤네베르그 이동을 통해 최소 강성 그래프를 구성하는 강화학습(RL) 접근 방식을 제안하며, Graph Isomorphism Network와 Deep Cross-Entropy Method를 사용하여 실현 개수 불변량을 최적화함으로써 새로운 기록 경계의 그래프를 성공적으로 도출했습니다.

핵심 포인트

• 최소 강성 그래프는 동일한 엣지 길이 데이터로 여러 개의 기하학적 실현체를 가질 수 있다.
• 높은 실현 개수를 갖는 그래프 탐색은 전수 탐색으로는 비실용적이다.
• 강화학습(RL)을 사용하여 헤네베르그 이동 기반으로 최소 강성 그래프를 구성하는 접근 방식을 제안했다.
• Graph Isomorphism Network와 Deep Cross-Entropy Method를 활용하여 실현 개수 불변량을 최적화한다.