최소 제로 포싱 집합(Minimum Zero-Forcing Sets)을 위한 심층 강화학습 (Deep Reinforcement Learning)

본 논문은 무방향 그래프(undirected graphs)에서 최소 제로 포싱 집합(minimum zero-forcing set)을 찾는 문제를 탐구하며, 이 문제를 해결하기 위해 조정된 머신러닝 (machine-learning) 프레임워크를 제안합니다. 최소 제로 포싱 집합 문제는 초기 노드 집합의 색상이 네트워크 전체로 전파되는 그래프 채색 (graph coloring) 문제입니다. 노드 집합이 색상 변경 규칙 (color-change rule)의 제약 조건 하에서 색상이 지정되지 않은 모든 노드의 색상을 변경하도록 강제한다면, 해당 노드 집합은 제로 포싱 (zero-forcing)된다고 합니다. 이 문제에는 네트워크 과학 (network science), 네트워크 제어 (network control), 논리 회로 설계 (designing logical circuits)와 같은 다양한 도메인에 걸친 여러 응용 분야가 있습니다. 최소 제로 포싱 집합을 찾는 것은 NP-hard임이 입증되었습니다. 우리는 S2V-DQN 아키텍처를 ZFS 문제에 맞게 조정한 강화학습 (reinforcement learning) 프레임워크인 SD-ZFS를 제안합니다. 우리는 이 조정된 프레임워크를 통해 여러 모델을 학습시키고, 다양한 구조를 가진 그래프 데이터셋 전반에 걸쳐 성능을 분석합니다. 또한 프레임워크에서 학습된 모델들이 어떻게 일반화 (generalize), 확장 (scale) 및 서로 다른 네트워크 유형으로 전이 (transfer)되는지 평가합니다. 결과는 최적해 (optimal solution) 및 탐욕적 휴리스틱 (greedy heuristic)과 비교했을 때 이 프레임워크의 효과성을 입증합니다. 우리는 머신러닝을 통해 ZFS 문제를 어떻게 해결할 수 있는지와 네트워크 구조가 문제에 미치는 영향에 대한 추가적인 통찰을 제공합니다.