  Task planning is emerging as an important research topic alongside the
development of large language models (LLMs). It aims to break down complex user
requests into solvable sub-tasks, thereby fulfilling the original requests. In
this context, the sub-tasks can be naturally viewed as a graph, where the nodes
represent the sub-tasks, and the edges denote the dependencies among them.
Consequently, task planning is a decision-making problem that involves
selecting a connected path or subgraph within the corresponding graph and
invoking it. In this paper, we explore graph learning-based methods for task
planning, a direction that is orthogonal to the prevalent focus on prompt
design. Our interest in graph learning stems from a theoretical discovery: the
biases of attention and auto-regressive loss impede LLMs' ability to
effectively navigate decision-making on graphs, which is adeptly addressed by
graph neural networks (GNNs). This theoretical insight led us to integrate GNNs
with LLMs to enhance overall performance. Extensive experiments demonstrate
that GNN-based methods surpass existing solutions even without training, and
minimal training can further enhance their performance. Additionally, our
approach complements prompt engineering and fine-tuning techniques, with
performance further enhanced by improved prompts or a fine-tuned model.
