Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~\cite{schuetz2022combinatorial},\cite{angelini2023modern},\cite{schuetz2023reply}
원문 초록
Recently graph neural network (GNN) based algorithms were proposed to solve a variety of combinatorial optimization problems, including Maximum Cut problem, Maximum Independent Set problem and similar other problems~\cite{schuetz2022combinatorial},\cite{schuetz2022graph}. The publication~\cite{schuetz2022combinatorial} stirred a debate whether GNN based method was adequately benchmarked against best prior methods. In particular, critical commentaries~\cite{angelini2023modern} and~\cite{boettcher2023inability} point out that simple greedy algorithm performs better than GNN in the setting of random graphs, and in fact stronger algorithmic performance can be reached with more sophisticated methods. A response from the authors~\cite{schuetz2023reply} pointed out that GNN performance can be improved further by tuning up the parameters better. We do not intend to discuss the merits of arguments and counter-arguments in~\cite{schuetz2022combinatorial},\cite{angelini2023modern},\cite{boettcher2023inability},\cite{schuetz2023reply}. Rather in this note we establish a fundamental limitation for running GNN on random graphs considered in these references, for a broad range of choices of GNN architecture. These limitations arise from the presence of the Overlap Gap Property (OGP) phase transition, which is a barrier for many algorithms, both classical and quantum. As we demonstrate in this paper, it is also a barrier to GNN due to its local structure. We note that at the same time known algorithms ranging from simple greedy algorithms to more sophisticated algorithms based on message passing, provide best results for these problems \emph{up to} the OGP phase transition. This leaves very little space for GNN to outperform the known algorithms, and based on this we side with the conclusions made in~\cite{angelini2023modern} and~\cite{boettcher2023inability}.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Q-Score: 분자 도킹을 위한 양자 네이티브 스코어링 함수
Q-Score: A Quantum-Native Scoring Function for Molecular Docking
분자 도킹은 소분자가 단백질에 결합하는 방식을 예측하며, 신약 개발의 핵심 병목 단계이다. 고전적인 스코어링 함수는 경험적 쌍별 접촉을 합산하는 방식으로, 결합 특이성을 결정하는 궤도 전하 이동과 같은 양자역학적 효과를 반영하지 못한다. 본 연구에서는 Q-Score를 제안한다. Q-Score는 GNN으로 예측된 궤도 전자 공여-수용 에너지를 가중 그래프로 인코딩하고, Digitized-Counterdiabatic QAOA를 통해 최대 가중치 정점 클리크 문제를 풀어 결합을 스코어링한다. 각 상호작용 앵커는 하나의 큐비트에 대응되며, 호환성 제약 조건은 에지로 표현된다. 11개의 단백질 타겟에 대해 DC-QAOA는 10큐비트에서 8개의 타겟에서 정확한 최적해를 복원한다. AI 생성 분자 1,000개에 대해 Q-Score는 Spearman rho 0.05로 고전적 스코어링과 직교하며, rho 0.90으로 궤도 품질에 의해 주도되고, 분자량 바이어스가 없으며, 무작위 대비 두 배의 비율로 강한 궤도 상호작용을 농축시킨다. DC-QAOA는 52%의 정확률과 함께 평균 근사 비율 0.94를 달성한다. IBM Eagle에서 1,000개의 회로 실행을 통해 NISQ 하드웨어상 6큐비트 문제의 해결 가능성이 확인되었다.
최대 독립 집합을 위한 Dual-GNN 다중 수준 조 정
Dual-GNN Multilevel Coarsening for Maximum Independent Set
최대 독립 집합(maximum independent set, MIS) 문제는 스케줄링, 자원 할당, 네트워크 분석 등에 응용되는 기본적인 NP-hard 조합 최적화(combinatorial optimization) 문제이다. 정확 솔버(exact solver)는 고품질 해 또는 최적성 증명(optimality certificate)을 제공할 수 있으나, 계산 비용은 그래프 크기에 따라 급격히 증가한다. 반면 수작업 휴리스틱(hand-crafted heuristic)은 보장을 희생하는 대신 확장성(scalability)을 개선한다. 학습 기반 방법은 그래프 인스턴스 간 구조적 패턴을 활용하는 대안을 제공하지만, 독립 집합을 직접 예측하면 대규모 그래프에서 전역 조율(global coordination)이 어려워질 수 있다. 우리는 대신 학습을 이용해 다중 수준 그래프 조 정(multilevel graph coarsening)을 안내하고, 최종 의사 결정에는 조합 탐색(combinatorial search)을 유지한다. Dual-GNN 다중 수준 조 정 프레임워크는 Partition GNN으로 후보 수축(contraction)을 점수화하고, Representative GNN으로 각 최종 클러스터에 대해 상위 k개의 지역 독립 집합 상태를 선택한다. 최대 2,000개 정점(vertex)을 갖는 Erdős–Rényi 그래프 실험에서 유리한 품질–실행 시간 트레이드오프(quality–runtime trade-off)를 보여준다. 인증된 최적해가 있는 500정점 인스턴스에서, 본 방법은 평균 독립 집합 크기 19.20을 달성하며 이는 최적값 19.30의 99.5%에 해당한다. 정확 해법의 평균 벽시계 시간(wall-clock time) 643.57초를 3.41초로 줄여 약 189배 속도 향상(speedup)을 얻는다. 1,000 및 2,000 정점의 더 큰 그래프에서는 평가된 모든 방법 중 최고의 평균 해 품질을 달성한다. 또한 가장자리 확률(edge probability) $p=0.35$인 Erdős–Rényi 그래프에서만 학습했음에도, 학습된 조 정 정책은 보지 못한 그래프 밀도와 구조적으로 다른 그래프 계열 모두에 효과적으로 일반화(generalize)된다.
잡 샵 스케줄링을 위한 GNN 기반 강화학습에서의 커리큘럼 러닝
Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling
잡 샵 스케줄링 문제(job shop scheduling problem)는 까다로운 조합 최적화(combinatorial optimization) 문제이며, 최근 그래프 신경망(GNN)을 활용한 강화학습(RL) 접근법은 문제 인스턴스로부터 스케줄링 정책을 직접 학습하는 데 유망함을 보여주었다. 그러나 대규모 인스턴스에 대한 학습은 여전히 연산 비용이 많이 들고, 다양한 인스턴스 크기에 걸친 일반화는 여전히 어려운 과제로 남아 있다. 본 논문에서는 잡 샵 스케줄링 문제에서 그래프 신경망 기반 강화학습을 위한 커리큘럼 러닝(curriculum learning)을 연구하며, 세 가지 타깃 크기인 20 x 20, 25 x 25, 30 x 30에 대해 단일 크기 학습(single-size training)과 비교한다. 커리큘럼 환경에서는 정책을 먼저 더 작은 인스턴스에서 학습시킨 후 점진적으로 더 큰 타깃 크기에 적응시켜, 초기 단계에서 학습된 스케줄링 동작이 더 큰 인스턴스에서의 학습을 뒷받침하도록 한다. 모델은 모든 평가 크기에 걸친 일반화와 타깃 크기에 대한 특화(specialization)를 모두 고려하여, 최적성 갭(optimality gap)을 사용해 8 x 8부터 30 x 30까지의 미확인(unseen) 인스턴스에서 평가된다. 실험 결과에 따르면 커리큘럼 러닝은 실제 학습 소요 시간(wall-clock training time)을 일관되게 단축하며, 타깃 크기가 커질수록 그 이점이 더 커지는 것으로 나타났다. 가장 강력한 이점은 30 x 30에서 관찰되었는데, 커리큘럼 러닝은 모든 평가 크기에 걸친 평균 최적성 갭을 약 8.1%포인트 줄이고, 타깃 크기의 평균 최적성 갭을 약 8.6%포인트 줄였으며, 학습 시간을 약 50시간 절약했다.
심층 강화학습을 활용한 라스트마일 픽업 통합 주문 배차 및 경로 최적화
Integrated Order Dispatching and Routing for Last-Mile Pickup via Deep Reinforcement Learning
최근 몇 년간 라스트마일 픽업 운영의 복잡성이 증가하면서 물류 플랫폼에서 빠르고 정확한 의사결정에 대한 필요성이 커졌다. 이 과제는 근본적으로 두 가지 핵심적이고 긴밀히 결합된 의사결정 과정, 즉 주문 배차와 경로 최적화에 의해 촉발된다. 이들을 개별적으로 해결하면 상호 의존성을 간과하게 되며, 완전한 end-to-end 학습은 희소 보상(sparse reward)으로 인해 대규모이고 가변적인 규모의 인스턴스에서 불안정하고 비용이 많이 든다. 이 문제를 해결하기 위해, 학습된 경로 오라클(routing oracle)과 실시간 배차 휴리스틱을 결합하는 통합 최적화 프레임워크를 제안한다. 경로 최적화 하위 문제에 대해서는 Look-Ahead Courier-Personalized 디코더를 갖춘 Dynamic-Residual Graph Attention Network 인코더를 개발한다. 배차 하위 문제에 대해서는 경로 오라클이 지도하는 국소 탐색(local search) 기반 배차 휴리스틱을 개발하며, 오라클은 실시간 확장성을 유지하면서 후보 배송 기사를 선택하기 위한 근최적 해를 제공한다. Cainiao Logistics의 실제 데이터셋을 활용한 광범위한 실험을 통해 오프라인 평가와 온라인 롤링 호라이즌(rolling-horizon) 시뮬레이션을 포함하여 접근법의 성능을 검증했다. 실험 결과, 제안 방법은 해 품질과 해결 시간 측면에서 다른 벤치마크를 능가하며, 실시간 대규모 라스트마일 픽업 문제 해결에 물류 기업을 효과적으로 지원할 수 있음을 보여준다.
Learning-to-Optimize 그래프 신경망을 통한 스마트 도시 NR-V2X 네트워크 AI 기반 다중 홉 릴레이 선택
AI-Driven Multi-Hop Relay Selection for Smart Urban NR-V2X Networks via Learning-to-Optimize Graph Neural Networks
밀집된 도시 환경에서 스마트 모빌리티를 위해 신뢰성 높고 저지연 NR-V2X 통신이 필수적이다. 그러나 제한된 도로변 유닛(RSU) 밀도, 빈번한 비시선(non-line-of-sight) 조건, 그리고 고도로 동적인 차량 토폴로지로 인해 많은 연결·자율주행 차량(CAV)이 안정적인 단일 홉 연결을 유지하지 못하는 경우가 많다. 다중 홉 릴레이 보조 통신이 인프라 커버리지를 확장할 수 있지만, 실질적인 흐름(flow), 용량, 연결성 제약 하에서 릴레이 링크를 실시간으로 선택하는 것은 여전히 어렵다. 혼합 정수 선형 계획(MILP)은 최적의 다중 홉 릴레이 결정을 제공하지만, 계산 복잡도가 네트워크 밀도에 따라 급격히 증가하여 실시간 적용이 제한된다. 이를 해결하기 위해, 실시간 NR-V2X 릴레이 선택을 위한 그래프 신경망(GNN) 기반 Learning-to-Optimise(L2O) 프레임워크를 제안한다. 차량 통신 상태를 속성 그래프(attributed graph)로 모델링하며, CAV와 RSU를 노드로, 후보 무선 링크에는 전파 인식(propagation-aware) 특성을 부여한다. 오프라인 MILP 오라클이 최적의 지도(supervision)를 제공하고, 엣지 인식(edge-aware) Graph Isomorphism Network(GINE)가 오라클 결정을 거의 일정한 추론 지연으로 근사한다. 통합 SUMO--GEMV2 시뮬레이션 파이프라인으로 생성된 대규모 도시 데이터셋에 대한 실험 결과, 제안 방법은 MILP 오라클과 유사한 연결성을 달성하면서 실행 시간을 수 자릿수만큼 단축한다. 이 프레임워크는 기존 차량 자산을 활용하고 스마트 시티 환경에서 확장 가능한 실시간 NR-V2X 운용을 지원함으로써, 도시 V2X 연결성을 비용 효율적으로 향상시킨다.
머신러닝을 활용한 단일 상수 곱셈의 효율적 SAT 인코딩을 위한 우수 규칙 식별
Identifying Good Rules for Efficient SAT Encodings of Single-Constant Multiplication Using Machine Learning
단일 상수 곱셈(Single Constant Multiplication, SCM) 문제는 하드웨어 설계에서 기본적인 NP-hard 최적화 작업으로, 고정 상수를 덧셈, 뺄셈, 비트 시프트만을 사용하여 분해하는 것을 목표로 한다. 동적 프로그래밍 방법은 SCM에 대해 근최적 SAT 인코딩을 생성할 수 있지만, 큰 상수에 대해서는 인코딩 비용이 여전히 높다. 우리는 분해 과정에서 연산자 선택을 안내하는 우수 규칙을 식별함으로써 SCM SAT 인코딩을 가속화하는 신경-기호(neuro-symbolic) 프레임워크를 제안한다. 우리 접근법은 상수 분해로부터 유망한 연산자 유형을 예측하기 위해 그래프 신경망(graph neural network) 모델을 사용하고, 그 결과 신뢰도 점수를 활용하여 기호적 탐색에서 no-good 선택을 가지치기(prune)한다. 보지 못한 17–32비트 상수에 대한 실험 결과는 인코딩 시간이 1~2자릿수 감소하고, 메모리 사용량이 97% 이상 감소하며, 분기(branching)가 한 자릿수 감소함을 보여주면서, 덧셈 측면에서 근최적 인코딩 품질을 유지한다. 이 결과는 학습 기반 기호적 전략이 SCM 인코딩의 확장성과 효율성을 크게 개선할 수 있음을 보여준다. 우리의 코드와 데이터는 https://github.com/Chufeng-Jiang/SCM_MLDP 에서 공개적으로 이용 가능하다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.