Aligning LLMs with Graph Neural Solvers for Combinatorial Optimization

• URL: http://arxiv.org/abs/2603.27169v1
• Date: Sat, 28 Mar 2026 07:07:56 GMT
• Title: Aligning LLMs with Graph Neural Solvers for Combinatorial Optimization
• Abstract summary: We propose AlignOPT, a novel approach that aligns language models with graph neural solvers to learn a more generalizable neural COP.<n>Our approach facilitates a robust integration and alignment between linguistic semantics and structural representations, enabling more accurate and scalable COP solutions.
• Score: 23.53424889758332
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent research has demonstrated the effectiveness of large language models (LLMs) in solving combinatorial optimization problems (COPs) by representing tasks and instances in natural language. However, purely language-based approaches struggle to accurately capture complex relational structures inherent in many COPs, rendering them less effective at addressing medium-sized or larger instances. To address these limitations, we propose AlignOPT, a novel approach that aligns LLMs with graph neural solvers to learn a more generalizable neural COP heuristic. Specifically, AlignOPT leverages the semantic understanding capabilities of LLMs to encode textual descriptions of COPs and their instances, while concurrently exploiting graph neural solvers to explicitly model the underlying graph structures of COP instances. Our approach facilitates a robust integration and alignment between linguistic semantics and structural representations, enabling more accurate and scalable COP solutions. Experimental results demonstrate that AlignOPT achieves state-of-the-art results across diverse COPs, underscoring its effectiveness in aligning semantic and structural representations. In particular, AlignOPT demonstrates strong generalization, effectively extending to previously unseen COP instances.

Related papers

• GRIL: Knowledge Graph Retrieval-Integrated Learning with Large Language Models [59.72897499248909]
  We propose a novel graph retriever trained end-to-end with Large Language Models (LLMs)<n>Within the extracted subgraph, structural knowledge and semantic features are encoded via soft tokens and the verbalized graph, respectively, which are infused into the LLM together.<n>Our approach consistently achieves state-of-the-art performance, validating the strength of joint graph-LLM optimization for complex reasoning tasks.
  arXiv  Detail & Related papers  (2025-09-20T02:38:00Z)
• Enhancing Large Language Models through Structured Reasoning [15.472375478049823]
  We introduce a novel approach to enhance Large Language Models (LLMs) through explicit structured reasoning.<n>First, we convert unstructured data into structured formats by explicitly annotating reasoning steps.<n>We then employ this structured dataset to train LLMs through Supervised Fine-Tuning (SFT)
  arXiv  Detail & Related papers  (2025-06-25T08:36:12Z)
• Integrating Visual Interpretation and Linguistic Reasoning for Math Problem Solving [61.992824291296444]
  Current large vision-language models (LVLMs) typically employ a connector module to link visual features with text embeddings of large language models (LLMs)<n>This paper proposes a paradigm shift: instead of training end-to-end vision-language reasoning models, we advocate for developing a decoupled reasoning framework.
  arXiv  Detail & Related papers  (2025-05-23T08:18:00Z)
• Bridging Visualization and Optimization: Multimodal Large Language Models on Graph-Structured Combinatorial Optimization [56.17811386955609]
  Graph-structured challenges are inherently difficult due to their nonlinear and intricate nature.<n>In this study, we propose transforming graphs into images to preserve their higher-order structural features accurately.<n>By combining the innovative paradigm powered by multimodal large language models with simple search techniques, we aim to develop a novel and effective framework.
  arXiv  Detail & Related papers  (2025-01-21T08:28:10Z)
• LLM2CLIP: Powerful Language Model Unlocks Richer Visual Representation [72.02635550088546]
  This work explores how large language models (LLMs) can enhance CLIP's capability, especially for processing longer and more complex image captions.<n>We introduce a caption-to-caption contrastive fine-tuning framework, significantly enhancing the discriminative quality of LLM outputs.<n>Our approach outperforms LoRA-based methods, achieving nearly fourfold faster training with superior performance.
  arXiv  Detail & Related papers  (2024-11-07T18:59:16Z)
• From Anchors to Answers: A Novel Node Tokenizer for Integrating Graph Structure into Large Language Models [27.353083085394008]
  We present NT-LLM, a novel framework with an anchor-based positional encoding scheme for graph representation.<n>Our approach strategically selects reference nodes as anchors and encodes each node's position relative to these anchors, capturing essential topological information without the computational burden of existing methods.<n>By implementing a rank-preserving objective for positional encoding pretraining, NT-LLM achieves superior performance across diverse graph tasks ranging from basic structural analysis to complex reasoning scenarios.
  arXiv  Detail & Related papers  (2024-10-14T17:21:57Z)
• In-context Demonstration Matters: On Prompt Optimization for Pseudo-Supervision Refinement [71.60563181678323]
  Large language models (LLMs) have achieved great success across diverse tasks, and fine-tuning is sometimes needed to further enhance generation quality.<n>To handle these challenges, a direct solution is to generate high-confidence'' data from unsupervised downstream tasks.<n>We propose a novel approach, pseudo-supervised demonstrations aligned prompt optimization (PAPO) algorithm, which jointly refines both the prompt and the overall pseudo-supervision.
  arXiv  Detail & Related papers  (2024-10-04T03:39:28Z)
• Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimization [21.232626415696267]
  The Language-based Neural COP solver (LNCS) is a novel framework that is unified for the end-to-end resolution of diverse text-attributed COPs.<n>Extensive experiments validate the effectiveness and generalizability of the LNCS, highlighting its potential as a unified and practical framework for real-world COP applications.
  arXiv  Detail & Related papers  (2024-08-22T08:42:44Z)
• Multi-View Empowered Structural Graph Wordification for Language Models [12.22063024099311]
  We introduce an end-to-end modality-aligning framework for LLM-graph alignment: Dual-Residual Vector Quantized-Variational AutoEncoder, namely Dr.E.<n>Our approach is purposefully designed to facilitate token-level alignment with LLMs, enabling an effective translation of the intrinsic'of graphs into comprehensible natural language.<n>Our framework ensures certain visual interpretability, efficiency, and robustness, marking the promising successful endeavor to achieve token-level alignment between LLMs and GNNs.
  arXiv  Detail & Related papers  (2024-06-19T16:43:56Z)
• Disentangled Representation Learning with Large Language Models for Text-Attributed Graphs [57.052160123387104]
  We present the Disentangled Graph-Text Learner (DGTL) model, which is able to enhance the reasoning and predicting capabilities of LLMs for TAGs. Our proposed DGTL model incorporates graph structure information through tailored disentangled graph neural network (GNN) layers. Experimental evaluations demonstrate the effectiveness of the proposed DGTL model on achieving superior or comparable performance over state-of-the-art baselines.
  arXiv  Detail & Related papers  (2023-10-27T14:00:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.