A Unified Pre-training and Adaptation Framework for Combinatorial Optimization on Graphs
원문 초록
Combinatorial optimization (CO) on graphs is a classic topic that has been extensively studied across many scientific and industrial fields. Recently, solving CO problems on graphs through learning methods has attracted great attention. Advanced deep learning methods, e.g., graph neural networks (GNNs), have been used to effectively assist the process of solving COs. However, current frameworks based on GNNs are mainly designed for certain CO problems, thereby failing to consider their transferable and generalizable abilities among different COs on graphs. Moreover, simply using original graphs to model COs only captures the direct correlations among objects, which does not consider the mathematical logicality and properties of COs. In this paper, we propose a unified pre-training and adaptation framework for COs on graphs with the help of the maximum satisfiability (Max-SAT) problem. We first use Max-SAT to bridge different COs on graphs since they can be converted to Max-SAT problems represented by standard formulas and clauses with logical information. Then, we further design a pre-training and domain adaptation framework to extract the transferable and generalizable features so that different COs can benefit from them. In the pre-training stage, Max-SAT instances are generated to initialize the parameters of the model. In the fine-tuning stage, instances from CO and Max-SAT problems are used for adaptation so that the transferable ability can be further improved. Numerical experiments on several datasets show that features extracted by our framework exhibit superior transferability and Max-SAT can boost the ability to solve COs on graphs.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
SplatQ: 2차 선택을 통한 3D 가우시안 스플래팅의 상호작용 인지 가지치기
SplatQ: Interaction-Aware Pruning of 3D Gaussian Splatting via Quadratic Selection
기존의 3D 가우시안 스플래팅(3DGS) 가지치기(pruning) 방법들은 주로 독립적인 중요도 점수에 기반한 전역 Top-K 선택에 의존하여, 영역별 예산 제어가 부족하고 공동 삭제 효과를 무시합니다. 결과적으로 전체 장면에 걸쳐 균형 잡힌 재구성 품질을 보장하지 못합니다. 본 논문에서는 고정된 예산 하에서 영역별 예산 할당과 공동 가우시안 선택을 조율하는 조합 가지치기 알고리즘인 SplatQ를 제안합니다. SplatQ는 공간적 근접성과 외형 유사성을 기준으로 가우시안을 크기가 제한된 블록으로 분할하여, 전역 선택 문제를 특정 크기의 하위 문제들로 분해합니다. 그런 다음 중요도 기반의 블록 유지 할당량을 평활화하여 과도한 예산 집중을 방지합니다. 마지막으로 가우시안 불투명도 변화에 대한 대표 픽셀 색상의 반응을 활용하여 공동 삭제 효과의 2차 근사를 구성합니다. 개별 반응, 쌍별 상호작용 및 할당량 페널티는 2차 비제약 이진 최적화(QUBO) 목적 함수에 통합되며, 모의 담금질(SA) 또는 코히런트 이징 머신(CIM)을 사용하여 이를 해결함으로써 가우시안을 공동으로 선택합니다. 5개 벤치마크에 대한 실험을 통해 SplatQ가 종합적인 재구성 품질, 공간적 품질 균형, 렌더링 속도 측면에서 최신 가지치기 방법들보다 우수한 성능을 보임을 입증합니다. 절제 연구(ablation)를 통해 예산 평활화가 국소적인 세부 표현 재구성을 향상시키는 한편, 상호작용 모델링이 고정된 예산 하에서 가우시안 선택 품질을 향상시킴을 확인합니다.
위에서 본 프롬프트 기반 개념 분할: 원격 탐사에서 SAM 3의 제로샷 텍스트 및 시각 프롬프팅 평가
Promptable Concept Segmentation from Above: Evaluating Zero-Shot Textual and Visual Prompting of SAM 3 in Remote Sensing
Segment Anything Model 3(SAM 3)와 같은 대규모 파운데이션 모델은 개방형 어휘와 무학습 컴퓨터 비전으로의 전환을 약속한다. 그러나 이러한 모델이 지구 관측 영상의 하향식 기하 구조라는 분포 외 영역으로 일반화하는 능력은 아직 거의 정량화되지 않았다. 우리는 미세 조정 없이 원격 탐사 장면 분류, 객체 탐지, 인스턴스 분할에 걸쳐 SAM 3를 다중 과제로 경험적으로 평가한다. 장면 분류에서는 분리된 이진 존재 헤드(binary presence head)를 독립적인 제로샷 분류기로 재활용한다. 탐지와 분할에서는 텍스트 프롬프트와 시각 프롬프트를 비교하며, 여기서 시각 프롬프트는 분할 대상 이미지 안에 있는 목표 클래스의 실제 인스턴스 하나를 제시한다. 텍스트만 사용하면 성능이 낮고, 시각 프롬프트를 추가하면 정확도가 크게 오르며, 둘을 결합하면 과제에 따라 정확도가 오르기도 하고 내리기도 한다. 또한 동일한 평가 프로토콜에서 SAM 3의 텍스트 전용 성능을 여러 일반 도메인 개방형 어휘 탐지 및 분할 모델과 비교한 결과, 두 벤치마크 모두에서 모든 모델을 앞선다. 그럼에도 시각 프롬프트가 없을 때의 정확도는 여전히 제한적이며, 이는 향후 연구 방향으로서 매개변수 효율적 미세 조정의 필요성을 시사한다.
지지 비지배점에 의한 다목적 네트워크 문제의 비지배 집합 표현
Representing the Non-dominated Set of Multi-objective Network Problems by Supported Non-dominated Points
다목적 조합 최적화에서 비지지 비지배점(unsupported non-dominated point)은 통상 지지점(supported point)보다 수가 많으며, 계산하기도 훨씬 어려운 경우가 많다. 최근 연구에 따르면 극단 지지 비지배점(extreme supported non-dominated point)은 특정 이진 문제의 비지배 집합에 대해 고품질 표현을 제공한다. 본 논문에서는 이 관찰이 용량 제한 네트워크 최적화 문제로 일반화되지 않음을 보인다. 즉, 호(arc) 용량이 증가할수록 표현 품질이 저하되는 반면, 지지 비지배점은 여러 품질 지표에서 지속적으로 고품질 표현을 제공한다. 그러나 지지점 집합도 실용적인 응용에서는 지나치게 클 수 있으며, 일반적으로 소수의 고정된 대안만이 요구된다. 비지배 집합에서 고정 크기 표현을 선택하려면 계산 비용이 높은 전체 집합 생성이 필요하므로, 표현이 제공하려는 계산 상의 이점이 감소한다. 따라서 본 논문은 부분집합 선택 문제에서 (극단) 지지점을 대안적 후보 집합으로 제안한다. 수치 실험 결과, 후보 집합을 지지 비지배점으로 제한하더라도 완전한 비지배 집합에서 선택한 것과 거의 동일한 품질의 고정 크기 표현을 얻을 수 있음을 보인다. 종합하면, 지지 비지배점은 고품질 표현이자 부분집합 선택을 위한 합리적인 후보 집합으로 모두 활용될 수 있다.
ODDR: 보상 가이던스를 통한 단일 단계 그림자 제거 확산 모델
ODDR: One-Step Deshadow Diffusion via Reward Guidance
그림자 제거를 위한 심층 학습(deep learning)의 최근 발전은 이미지 품질과 사실성을 크게 향상시켰습니다. 그러나 대부분의 접근 방식은 수집 비용이 많이 들고 장면 다양성이 제한적인 경우가 많은 실제 쌍(paired) 데이터셋에 의존하므로 일반화 성능이 제한됩니다. 이러한 한계를 해결하기 위해, 우리는 실제 쌍으로 구성된 지도학습(supervision)에 의존하지 않고도 효율적이고 충실도 높은 그림자 제거를 달성하는 새로운 프레임워크인 보상 가이던스를 통한 단일 단계 그림자 제거 확산 모델(One-step Deshadow Diffusion via Reward guidance, ODDR)을 제안합니다. 본 연구의 방법은 효율적인 단일 단계 무그림자 재구성을 위해 합성 그림자 데이터로 학습된 기준선(baseline) 모델인 One-step Deshadow Diffusion(ODD)에서 시작합니다. 나아가 우리는 ShadowReward를 사용하여 ODD를 ODDR로 발전시킵니다. 주석(annotation) 작업이 많이 필요한 기존 방식과 달리, ShadowReward는 인간의 주석 없이 전적으로 학습된 그림자 제거용 최초의 보상 모델(reward model)입니다. 이는 질감 왜곡 및 경계 아티팩트와 같이 통제된 품질 저하가 적용된 합성 생성 이미지를 순위화하여 인간의 지각적 판단을 모방하도록 학습합니다. 이러한 보상 기반 미세조정(fine-tuning)을 통해 ODDR은 합성-실제 간 도메인 간극을 좁힐 수 있습니다. 광범위한 실험을 통해 ODD는 실제 쌍 지도학습에 의존하지 않고도 강력한 성능을 달성하며, ODDR은 결과를 더욱 향상시켜 단일 단계 모델로서 더 높은 연산 효율성을 유지하면서도 실제 쌍 데이터로 학습된 완전 지도학습 방식과의 격차를 좁힘을 보여줍니다.
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큐비트 문제의 해결 가능성이 확인되었다.
도메인이 중요한 이유: 수중 객체 검출 및 어노테이션 품질의 도메인 인식 벤치마킹
Why Domain Matters: Domain-Aware Benchmarking of Underwater Object Detection and Annotation Quality
수중 물체 탐지는 도메인 변화의 영향을 크게 받으며, 성능은 위치, 서식지, 배치 조건에 따라 크게 달라질 수 있다. 그러나 탐지기 성능은 일반적으로 특정 환경에서의 실패를 가리는 종합 지표로 평가되며, 기존 도메인 일반화 벤치마크는 실제 조건을 반영하지 못하는 합성 변형에 의존하는 경우가 많다. 이러한 한계를 해결하기 위해 우리는 외관, 장면 구성, 획득 기하를 기준으로 수중 이미지를 특성화하여 도메인 레이블을 부여하는 프레임워크를 도입한다. 이 프레임워크를 사용하여, 도메인 요인이 수중 물체 탐지 데이터셋에서의 사람의 주석 품질과 딥러닝 기반 탐지기 성능에 어떻게 영향을 미치는지에 대한 최초의 체계적 연구를 수행했으며, 도메인에 따른 상당한 불일치를 밝혀냈다. 물리적으로 의미 있는 도메인 레이블을 도입함으로써, 도메인 변화는 우리가 특성화하고, 측정하고, 벤치마크하고, 대응할 수 있는 대상이 된다. 우리는 이 프레임워크가 데이터 수집과 주석 작업을 안내하고, 더 유익한 벤치마크를 설계하며, 다양한 수중 환경에서 탐지기의 견고성을 평가하는 데 어떻게 활용될 수 있는지 강조한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.