Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update
원문 초록
Combinatorial optimization (CO) problems are crucial in various scientific and industrial applications. Recently, researchers have proposed using unsupervised Graph Neural Networks (GNNs) to address NP-hard combinatorial optimization problems, which can be reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. GNNs have demonstrated high performance with nearly linear scalability and significantly outperformed classic heuristic-based algorithms in terms of computational efficiency on large-scale problems. However, when utilizing standard node features, GNNs tend to get trapped to suboptimal local minima of the energy landscape, resulting in low quality solutions. We introduce a novel algorithm, denoted hereafter as QRF-GNN, leveraging the power of GNNs to efficiently solve CO problems with QUBO formulation. It relies on unsupervised learning by minimizing the loss function derived from QUBO relaxation. The proposed key components of the architecture include the recurrent use of intermediate GNN predictions, parallel convolutional layers and combination of static node features as input. Altogether, it helps to adapt the intermediate solution candidate to minimize QUBO-based loss function, taking into account not only static graph features, but also intermediate predictions treated as dynamic, i.e. iteratively changing recurrent features. The performance of the proposed algorithm has been evaluated on the canonical benchmark datasets for maximum cut, graph coloring and maximum independent set problems. Results of experiments show that QRF-GNN drastically surpasses existing learning-based approaches and is comparable to the state-of-the-art conventional heuristics, improving their scalability on large instances.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
분류 성능의 지표로서 라이프-유사 네트워크 오토마타 규칙의 형태 불규칙성
Shape irregularity of Life-Like Network Automaton rules as an indicator of classification performance
복잡 네트워크(Complex Network, CN) 분류는 스케일 불변(scale-invariant)이면서도 계산적으로 효율적인 고수준의 구조적 특성화를 필요로 합니다. 라이프-유사 네트워크 오토마타(Life-Like Network Automata, LLNA) 기반 방법은 사전에 제공된 특징 없이도 창발적 시간 패턴을 활용하여 네트워크 기술자(descriptor)를 추출하는 흥미로운 방식을 제공하지만, 그 효과는 오토마타 전이 규칙의 선택이라는 높은 비용의 조합 최적화 문제로 인해 병목 현상을 겪습니다. 기존 연구들은 대규모 응용에 실현 불가능한 전수 탐색(exhaustive search)에 의존하는 반면, 본 연구는 규칙 공간이 LLNA 전이 함수와 톱니 형태의 유사성을 정량화하는 '들쭉날쭉함(jaggedness)'이라는 특성으로 근본적으로 구조화되어 있음을 밝힙니다. 우리는 이 지표가 혼돈성(chaoticity)과 민감도(sensitivity)에 대한 이론적 대리 지표로 작용함을 입증하며, 이러한 특성은 네트워크 범주 간의 식별력 있는 동적 동작을 생성하는 데 필수적입니다. 나아가, 우리는 들쭉날쭉함을 활용하여 규칙 선택을 유도하는 휴리스틱 탐색 전략을 도입합니다. 실험 결과에 따르면 본 접근법은 전수 탐색 방식에 비해 계산 오버헤드를 90% 줄이면서도 전역 최적값 대비 5% 이내의 분류 정확도를 달성합니다. 우리의 발견은 패턴 인식을 위한 오토마타 기반 방법을 최적화하는 새롭고 효율적인 프레임워크를 제공합니다.
JOVE: 자원 인지형 LLM 태스크 그래프를 위한 공동 실행 및 검증
JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs
복잡한 추론 질의는 방향성 비순환 그래프(DAG) 형태의 태스크 그래프로 분해되어 이종 대규모 언어 모델(LLM)에 분산될 수 있으며, 이를 통해 병렬 처리를 통한 지연 시간을 줄이고 더 작은 모델이 복잡한 태스크를 해결하도록 지원할 수 있습니다. 그러나 실제로는 주어진 서브태스크에 대한 특정 LLM의 적합성을 사전에 알 수 없을 수 있으며, 단순 실행만으로는 출력의 정확성을 파악할 수 없습니다. 본 논문에서는 실행기 LLM을 할당하는 동시에 유료 검증을 거칠 중간 출력을 함께 선택하는 온라인 프레임워크인 JOVE를 제안합니다. 검증은 비동기식으로 실행되며 향후 할당 결정을 개선하는 데 사용되므로, 시스템은 현재 실행에 드는 비용과 향후 학습을 위한 지출 사이의 균형을 유지해야 합니다. 본 연구에서는 확률적이며 초기에는 알려지지 않은 LLM 서비스 품질, 호출 비용 및 실행 시간 환경에서 장기 예산과 질의별 지연 시간 제약 조건 하에 이러한 트레이드오프를 최적화하는 방법을 연구합니다. JOVE는 질의별 일련의 혼합 정수 선형 계획법(MILP) 문제를 해결하여 실행 및 검증 결정을 내립니다. 온라인 학습은 검증 피드백을 기반으로 LLM 품질에 대한 태스크 의존적 추정치를 업데이트하며, 정보 이득 보너스를 통해 학습의 가치를 할당 결정에 반영합니다. 자연스러운 일련의 가정 하에 본 연구는 JOVE의 준선형(sublinear) 품질 학습 후회(regret)를 입증합니다. 4가지 추론 벤치마크 전반에서 JOVE는 표준 추론(inference) 베이스라인 대비 경쟁력 있는 정확도를 달성하는 동시에 평균 비용과 지연 시간을 최소 3.17배 단축합니다.
최대 독립 집합을 위한 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시간 절약했다.
재해결 없이 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법
Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving
대규모 언어 모델(LLM) 추론과 검색 서비스의 확대는 온라인 선형 계획 문제의 규모를 키우며, 계산적으로 효율적인 알고리즘을 요구한다. 본 연구는 확률적 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법(RASGD)을 제안한다. 이 알고리즘은 요청 하나와 현재 재고(inventory)만으로 자원 가격을 갱신하며, 자원 m개에 대해 도착(arrival)마다 O(m) 연산과 메모리만 필요하고 LP나 표본 평균 최적화(sample-average optimization)는 사용하지 않는다. 핵심은 재해결(re-solving)에서 쓰이는 현재 자원 가격 책정 로직을 1차 SGD 갱신으로 표현하는 것이다. 각 도착마다 이중 목적(dual objective)의 잔여 재고 허용량(allowance)을 갱신하고, 스텝 크기(stepsize)는 초기에는 학습을 위해 작아지다가 이후에는 재고 조정 속도에 맞추어 커진다. 표준 비퇴화(non-degeneracy) 조건 하에서 알고리즘은 모든 표본 경로(sample path)에서 실행 가능(feasible)하며, 실현된 분수적 후견 최적(realized fractional hindsight optimum) 대비 O(\log T) 기대 후회(expected regret)를 달성한다. 이는 분포를 알고 계산 제약이 없는 정책에 대한 하한과 일치한다. 분석은 변화하는 자원 수준에서 최적 가격을 추적하지 않고, 고정 참조 가격 주변의 곡률(curvature)을 재고 안정성(inventory stability)으로 전환한다. 수치 실험에서 RASGD는 도착마다 LP 재해결과 견줄 만한 후회를 달성하고, 시험한 1차 기준선(first-order baselines)보다 나으면서 1차 방법의 계산 효율은 유지한다. 이 결과는 RASGD가 대규모 OLP에서 높은 할당 품질을 계산 효율적으로 달성하는 접근임을 보여준다.
마지막 고원(Final Plateau)에서 표준 A* 타이 브레이킹 전략에 따른 확장 횟수
Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau
A* 탐색 알고리즘에서 동일한 $f$-값을 갖는 노드에 대한 타이 브레이킹(tie-breaking, 동점 처리) 전략은 A*가 마지막 $f$-층(layer)에서 어떤 상태들을 확장할지 결정합니다. 9가지 표준 타이 브레이킹 전략에 대해, 일관적인 휴리스틱(consistent heuristic) 하에서 모든 전략 쌍마다 임의로 큰 가산적 확장 차이(additive expansion gap)로 상대 전략보다 특정 전략을 선호하게 만드는 양의 비용 인스턴스가 존재함을 보입니다. 매개변수화된 단위 비용 격자 예시 또한 FIFO 및 LIFO를 사용하는 low-$h$ 간에 무한한 확장 횟수 비율을 발생시킵니다. 목표가 아닌 상태에서 $h > 0$인 단위 비용 탐색에서, 목표 근처의 정확한 휴리스틱 값은 상호보완적인 극단적 결과로 이어집니다. 완벽 영역(perfect region) 내의 공통 형상(configuration)으로부터 남은 확장 횟수는 low-$h$가 최소화하는 반면, $h=1$인 모든 마지막 고원 상태가 목표 직전 상태(goal predecessor)일 때 전체 확장 횟수는 high-$h$가 최대화합니다. 마지막으로, 평가 함수 $f_{\alpha} = g + \alpha h$를 사용할 때 목표가 아닌 상태에서 $h>0$이면, 모든 휴리스틱 가중치(weight) $0 \leq \alpha<1$은 타이 브레이킹 민감도를 제거하며 모든 타이 브레이킹 전략이 동일한 상태 집합을 확장합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.