Large language models (LLMs) have recently been introduced to graph learning, aiming to extend their zero-shot generalization success to tasks where labeled graph data is scarce. Among these applications, inference over text-attributed graphs (TAGs) presents unique challenges: existing methods struggle with LLMs' limited context length for processing large node neighborhoods and the misalignment between node embeddings and the LLM token space. To address these issues, we establish two key principles for ensuring generalization and derive the framework LLM-BP accordingly: (1) Unifying the attribute space with task-adaptive embeddings, where we leverage LLM-based encoders and task-aware prompting to enhance generalization of the text attribute embeddings; (2) Developing a generalizable graph information aggregation mechanism, for which we adopt belief propagation with LLM-estimated parameters that adapt across graphs. Evaluations on 11 real-world TAG benchmarks demonstrate that LLM-BP significantly outperforms existing approaches, achieving 8.10\% improvement with task-conditional embeddings and an additional 1.71\% gain from adaptive aggregation. The code and task-adaptive embeddings are publicly available.

Large language models (LLMs), powerful AI systems known for their ability to understand text, have recently been applied to learning from graph data, particularly graphs whose nodes carry textual information. However, current methods face challenges: LLMs have limited memory for handling large networks of information. To address the issue, we introduced LLM-BP, an approach built around two key ideas. First, we designed specialized embeddings—ways of translating text into numbers—that adapt specifically to the tasks we want the model to perform. Second, we created a flexible method inspired by belief propagation, a common technique used to spread information efficiently across graphs, where the LLM itself decides how best to combine data from different nodes. When tested across multiple real-world datasets, LLM-BP showed substantial improvements over existing methods, making it much better at handling graphs with text-based data. This research could enhance applications like knowledge discovery, recommendation systems, and information retrieval, where efficiently interpreting large-scale text-rich data is essential.