arXiv:2302.04035

Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networks

Ya Song, Laurens Bliek, Yingqian Zhang

제출 2023-02-08

원문 초록

Algorithm selection is a well-known problem where researchers investigate how to construct useful features representing the problem instances and then apply feature-based machine learning models to predict which algorithm works best with the given instance. However, even for simple optimization problems such as Euclidean Traveling Salesman Problem (TSP), there lacks a general and effective feature representation for problem instances. The important features of TSP are relatively well understood in the literature, based on extensive domain knowledge and post-analysis of the solutions. In recent years, Convolutional Neural Network (CNN) has become a popular approach to select algorithms for TSP. Compared to traditional feature-based machine learning models, CNN has an automatic feature-learning ability and demands less domain expertise. However, it is still required to generate intermediate representations, i.e., multiple images to represent TSP instances first. In this paper, we revisit the algorithm selection problem for TSP, and propose a novel Graph Neural Network (GNN), called GINES. GINES takes the coordinates of cities and distances between cities as input. It is composed of a new message-passing mechanism and a local neighborhood feature extractor to learn spatial information of TSP instances. We evaluate GINES on two benchmark datasets. The results show that GINES outperforms CNN and the original GINE models. It is better than the traditional handcrafted feature-based approach on one dataset. The code and dataset will be released in the final version of this paper.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.09708v1cs.AI공통 태그 Graph Neural Network, Traveling Salesman Problem

GES-TSP: TSP를 위한 그래프 엣지 희소화

GES-TSP: Graph Edge Sparsification for TSP

외판원 문제(TSP)의 대규모 인스턴스를 정확하게 푸는 것은 계산 비용이 많이 든다. 연구자들은 계산 효율성을 높이기 위해 그래프 희소화(sparsification) 방법을 자주 활용한다. 전통적인 희소화 방법은 주로 고정된 휴리스틱에 의존하며 인스턴스별 구조적 정보를 충분히 활용하지 못한다. 본 논문에서는 유클리드 TSP를 위한 학습 기반 희소화 접근법인 그래프 엣지 희소화(GES, Graph Edge Sparsification)를 제안한다. 기하학적 구조 정보와 조합 최적화 기술을 결합하여, 제안된 방법은 서로 다른 인스턴스에 대해 희소화 그래프를 적응적으로 생성하며, 그래프 크기를 크게 줄이고 풀이 과정을 가속화한다. 실험 결과, 본 희소화 방법은 MATILDA 데이터셋에서 엣지의 최대 95%를 가지치기하면서도 솔루션 갭을 최적값의 1% 이내로 유지함을 보여준다. 또한, 본 접근법은 TSPLIB 벤치마크에서 강력한 일반화 능력을 나타낸다. 일부 대규모 인스턴스에서는 가지치기 비율이 99%를 초과하면서도 최적성 갭이 1% 미만으로 유지된다.

arXiv:2606.27539v2cs.SI공통 태그 Graph Neural Network

멀티모달 그래프 기반 소셜 미디어 인기 예측 벤치마킹

Benchmarking Multi-Modal Graph-based Social Media Popularity Prediction

소셜 미디어 인기도 예측은 초기 단계의 관측으로부터 온라인 콘텐츠의 향후 도달 범위나 영향력을 예측하는 것을 목표로 한다. 정확한 예측은 광고 최적화나 사용자, 크리에이터, 플랫폼의 전략적 콘텐츠 기획과 같은 주요 하위 응용을 가능하게 한다. 상당한 진전에도 불구하고, 기존의 인기도 예측 연구는 멀티모달 콘텐츠와 시간적 소셜 상호작용 신호를 함께 고려하지 못하는 경우가 많다. 더욱이 관련 문헌은 데이터셋, 모달리티, 관측 윈도우, 예측 대상, 평가 프로토콜에 걸쳐 매우 파편화되어 있다. 이러한 파편화는 공정한 비교를 방해하고, 텍스트, 시각, 시간, 상호작용 기반 신호가 인기도 역학을 어떻게 함께 형성하는지에 대한 체계적인 이해를 가린다. 이러한 문제를 해결하기 위해, 본 논문은 데이터셋, 모달리티, 시간적 상호작용 신호, 대표적인 베이스라인을 표준화된 평가 프로토콜 아래 통합하는 멀티모달 그래프 기반 인기도 예측 벤치마크인 MMG-Pop을 제안한다. 나아가 앞서 언급한 멀티모달 신호와 그래프 구조의 소셜 상호작용을 함께 모델링하는 통합 멀티모달 그래프 기반 네트워크인 MMG-PopNet을 제안한다. Bluesky와 Reddit 플랫폼에 걸친 MMG-Pop에서의 폭넓은 실험은 MMG-PopNet의 우수한 성능을 보여 주며, 플랫폼 간 학습 일반화, 멀티태스크 예측의 이점, 멀티모달리티의 기여, LLM 예측의 한계에 대한 새로운 통찰을 제공한다. 이러한 발견은 이질적인 모달리티와 사회 인식 에이전트 생태계 패러다임 하에서의 사회적 역학 모델링 및 개입에 관한 향후 연구의 토대를 마련한다.

arXiv:2609.25722v3cs.LG공통 태그 Graph Neural Network

부호 그래프 사전학습 및 프롬프트 학습

Signed Graph Pre-Training and Prompt Learning

부호 그래프(signed graph)는 엣지가 양수이거나 음수일 수 있으며 방향성을 가질 수도 있는 신뢰-불신 네트워크, 금융 상관관계 시스템, 생물학적 상호작용 그래프 및 기타 여러 도메인에서 발생합니다. 부호 그래프 신경망이 특정 태스크에 특화된 학습(training)을 향상시켰지만, 부호 그래프에서의 그래프 전이학습(transfer learning)은 여전히 미진한 상태입니다. 본 논문에서는 부호 그래프를 위한 선구적인 위상학 기반 그래프 사전학습(pre-training) 및 프롬프트(prompt) 학습 프레임워크인 TopoSIGN을 소개합니다. TopoSIGN은 자기 부호 라플라시안(magnetic signed Laplacian)을 기반으로 구축된 구조적 인코더와 Dowker 복합체 지속성 이미지(Dowker-complex persistence images)를 통해 부호 위상을 요약하는 새로운 지속성 호몰로지(persistent-homology) 브랜치를 결합합니다. 융합된 임베딩(embedding)은 이후 프롬프트 학습 함수로 전달됩니다. 합성 및 실제 데이터셋(dataset)에 대한 실험 결과는 부호 그래프에서 유용한 구조적 정보를 추출하는 TopoSIGN의 효능뿐만 아니라, 제안된 일반 프레임워크의 적응성과 유연성을 입증합니다.

arXiv:2609.27710v3cs.CV공통 태그 Graph Neural Network

FFM-CP: 퓨샷 계산병리학을 위한 비전-언어 기반 모델의 교차 백본 융합

FFM-CP: Cross-Backbone Fusion of Vision-Language Foundation Models for Few-Shot Computational Pathology

병리학 비전-언어 기반 모델은 질환과 과제에 따라 성능이 달라지며, 어떤 단일 모델도 일관되게 최고 성능을 내지 못한다. 전문가 병리 주석의 높은 비용은 과제별 적응에 사용할 수 있는 라벨 데이터를 제한하기도 한다. 상호 보완적인 사전학습 표현을 결합하는 것은 이러한 한계에 대한 잠재적 접근이지만, 소수의 라벨 예시로부터 효과적인 융합을 학습하는 것은 여전히 어렵다. 본 연구는 퓨샷 학습 설정에서 여러 병리학 비전-언어 모델을 결합하는 프레임워크인 Few-shot Fusion Foundation Models of Computational Pathology(FFM-CP)를 제안한다. 이 프레임워크는 먼저 대응하는 서포트 이미지로부터 추정한 폐형식(closed-form) 직교 프로크루스테스(Orthogonal Procrustes) 변환을 사용하여 이질적인 표현을 정렬한다. 이 정렬은 추가 정렬 네트워크를 학습하지 않고도 모델 내부 특징 기하를 보존한다. 정렬된 공간 안에서 통합 그래프는 서포트 이미지 특징과 시각·텍스트 클래스 프로토타입을 공동으로 정제함으로써 백본 간 정보 교환을 가능하게 한다. 이렇게 정제된 표현은 의미적 클래스 지식과 클래스 내 시각적 변이를 각각 포착하는 상호 보완적인 텍스트-프로토타입 분기와 케이스 검색(case-retrieval) 분기를 지원한다. 각 분기는 모든 순서화된 백본 쌍의 예측을 결합하는 방법을 학습하여, 한 모델로 인코딩된 쿼리가 다른 모델이 표현한 증거를 활용할 수 있게 한다. 우리는 6개의 조직병리학 데이터셋에서 클래스당 4, 8, 16샷 조건으로 3가지 백본 조합을 평가했다. FFM-CP는 54번 비교 중 50번에서 각 융합 집합의 개별 적응 멤버 중 가장 강한 모델보다 더 높은 평균 macro-F1을 달성했다. 이러한 결과는 주석이 제한될 때 상호 보완적인 사전학습 표현의 결합이 조직병리학 분류를 개선할 수 있음을 시사한다.

arXiv:2607.05017v2cs.LG공통 태그 Graph Neural Network

그래프 신경망에서의 하이퍼파라미터 전이

Hyperparameter Transfer in Graph Neural Networks

심층 학습(deep learning) 모델의 성능은 학습률, 초기화 스케일, 가중치 감쇠와 같은 하이퍼파라미터 설정에 크게 의존한다. 하이퍼파라미터 전이(hyperparameter transfer)는 모델 규모에 걸쳐 최적에 가까운 하이퍼파라미터 설정을 일관되게 유지하는 것을 목표로 하며, 이를 통해 대형 모델을 더 작고 최적화 비용이 저렴한 대리 모델을 프록시 튜닝하여 최적화할 수 있다. 전이 원칙은 언어 및 비전 태스크에서의 밀집 신경망(dense neural network) 맥락에서 잘 연구되어 있지만, 그래프 신경망(GNN)에 대해서는 상대적으로 탐구가 미흡한 상태이다. 우리는 SGD, Adam, AdamW로 학습된 GNN을 위한 전이 파라미터화를 개발하고 검증한다. 이론적 스케일링 분석과 제어된 실험을 통해, 제안된 파라미터화가 안정적인 특징 업데이트, 학습률 전이, 그리고 너비와 깊이가 증가함에 따른 성능 향상을 달성함을 보인다. SGD의 경우, 그래프에 의존하는 첫 번째 층 보정 인수를 식별하고, 이를 활용하면 희소 bag-of-words 입력을 가진 그래프에서 초기 학습을 가속화할 수 있음을 보인다. Adam의 경우, 서로 다른 메시지 패싱 정규화 방식이 초기 및 후기 학습 전이 동작에 미치는 영향을 탐구하며, 메시지 패싱 정규화의 중요성을 설명하고 이에 연관된 하이퍼파라미터의 사용을 권장한다. AdamW의 경우, 가중치 감쇠와 학습률의 공동 전이를 가능하게 하는 파라미터화를 적용한다. 이러한 결과들은 다양한 학습 태스크와 학습 시나리오에 걸쳐 GNN을 스케일링하기 위한 실용적인 방법론을 제공한다.

arXiv:2607.09737v2physics.chem-ph공통 태그 Graph Neural Network

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큐비트 문제의 해결 가능성이 확인되었다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.