LLaTA: Unlocking Graph Structure Learning with Tree-Guided Large Language Models

The gist The emergence of large language models has popularized text-attributed graphs (TAGs), creating an urgent need for graph structure learning (GSL) methods that effectively leverage textual information.

How it works

LLaTA reformulates GSL as a tree optimization framework, shifting the focus from training edge predictors to designing a language-aware tree sampler. This approach constructs structural encoding trees via entropy minimization to capture topology, and then leverages tree-guided LLM in-context learning to integrate textual semantics without finetuning. The framework consists of three key components: (1) Topology-aware Incontext Construction, (2) Tree-prompted LLM Inference, and (3) Leaf-oriented Two-step Sampling.

Topology-aware Incontext Construction

This component involves quantifying the dynamic complexity of graph topology via structural entropy and applying a greedy algorithm to minimize this measure to construct a hierarchical structural encoding tree. The optimization objective is defined as T⋆= argmin T H T(G), where HT(G) = -Xϕ∈T,ϕ≠λ gϕ vol(G) log2 vol (phi) vol (phi+) and the algorithm uses Node Initializing, Node Combining, and Node Lifting operations. This process constructs a hierarchical encoding tree T⋆ with a predefined height K.

Tree-prompted LLM Inference

The tree serves as a high-quality prompt, enabling LLMs to perform in-context learning for a deeper understanding of both topology and text. Specifically, the method uses LLMs to uncover textual semantic relationships within the leaf community. Based on these insights, leaf dependencies are reallocated to refine the tree structure. This is achieved through Reception-aware Leaf Augmentation, which involves tree-guided text propagation and aggregation within each low-level community Cl to achieve leaf augmentation for ε-guaranteed t⋆. Furthermore, the Community of Thought (CoT) prompting mechanism allows the LLM to jointly exploit topological and semantic information for more reliable inference.

Leaf-oriented Two-step Sampling

The final step involves performing LLM-guided leaf selection to identify nodes for edge addition or removal, achieving training-free GSL. This two-step sampling strategy balances efficiency and performance by first selecting a small set of nodes that require optimization from a topological perspective, and second, sampling textually related candidate nodes for them. The selection is guided by two probability functions: Ptopo(α) = exp(HT(G, α)) and Pαsema(β) = exp(sim(yclsβ, yclsα)).

Key Findings and Contributions

LLaTA consistently outperforms prior LLM-based methods, improving accuracy by 1.3%–2.5% while reducing runtime by 2.5–9.2 hours. The method is training-free and decoupled, requiring no fine-tuning of LLMs or dependency on specific GNN backbones. LLaTA achieves SOTA performance across multiple benchmarks. The method's robustness against sparsity and moderate levels of noise is strong, with the tree-based optimization guiding the identification of uncertain regions. The optimal parameters are found by searching on validation performance only, suggesting a practical starting configuration is K ∈ 2, 3, ϵ = 0.5, θ = 10, and r = 5.

Limitations

Despite achieving promising results, LLaTA presents two main limitations: first, its robustness against extreme structural noise and adversarial topological perturbations could be further improved. Second, the current architecture inherently assumes homophily in graph topology, which limits its generalizability to heterophilic graphs where connected nodes typically belong to different classes.

Efficiency Analysis

LLaTA achieves superior efficiency by shifting complexity from the edge level to the node/community level, significantly reducing inference cost. The time complexity is O(n log 2 n + nC2 + ntLLM-i + n). This method requires substantially less inference time, particularly than LLM4RGNN, and eliminates training during structure learning, resulting in zero training time. The composite scoring mechanism Score(Cl) = λ1 · Hstruct(Cl) + λ2 · Hlabel(Cl) + λ3 · 1 − µtextsim(Cl) is used to prioritize optimization and sampling on top-ranked candidates.

Case Study

A case study on Citeseer reveals that Step 1 Topology-aware Incontext Construction and Step 3 Leaf-oriented Twostep Sampling have relatively fixed computation in which LLMs do not actively participate or play a secondary role. The focus is on Step 2: Tree-prompted LLM Inference, specifically analyzing Reception-aware Leaf Augmentation, Community of Thought, and Leaf Dependency Allocation. The final step involves reconstructing two new low-level communities to replace the original ones.

LLM Backbone Analysis

Table 7 shows that LLaTA performs effectively with different LLM backbones, highlighting the versatility of our method. Gemma-3-27B achieves the best overall performance across the four datasets, indicating that stronger contextual reasoning can improve the semantic distributions used for structure optimization. Llama-4-9B remains the strongest among the original four backbones, particularly on WikiCS and Instagram.

Hyperparameter Analysis

The optimal K varies across datasets, with moderate depths (K = 2 or 3) generally achieving the best performance. The threshold ϵ is sensitive but empirically stable within the range [0.45, 0.55] across these datasets. The sampling frequency r should be prioritized during tuning, especially for heterophilic graphs where improper calibration may lead to over-homogenization of node neighborhoods. The semantic sampling parameter θ exhibits remarkable stability across all datasets within the range [5, 15].

Conclusion

In this paper, we propose a tree-based optimization framework for GSL that explicitly integrates LLMs and textual information. LLaTA achieves SOTA performance across multiple benchmarks by leveraging a structural encoding tree for efficient LLM in-context learning, enabling joint understanding of topology and text without fine-tuning. The framework is training-free and decoupled, replacing costly fine-tuning with topology-aware prompting and efficient inference. LLaTA introduces several innovations that distinguish it from prior work, including reformulating GSL as a tree optimization task, being training-free and decoupled, achieving higher efficiency by shifting complexity to the node/community level, and ensuring structural updates respect the original community divisions.

References

Wendong Bi et al. 2024. Make heterophilic graphs better fit gnn: A graph rewiring approach. Yu Chen et al. 2020. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Zhikai Chen et al. 2024.

1. Bold header: Topology-aware In-context Construction

The improved system can construct high-quality, topology-aware in-context for LLM inference by leveraging a structural encoding tree constructed via minimizing structural entropy, enabling the LLM to understand both topology and text.

2. Bold header: Tree-prompted LLM Inference

The system can perform structure refinement through a process that involves Reception-aware Leaf Augmentation, where text is enriched within communities, followed by a Community of Thought (CoT) prompting mechanism to allow the LLM to jointly exploit topological and semantic information for more reliable inference.

3. Bold header: Leaf-oriented Two-step Sampling

The system can achieve training-free graph structure learning by using a strategy where it first identifies nodes requiring optimization based on their topological properties and then selects candidate nodes based on semantic similarity to enhance connectivity, enabling edge modifications without costly fine-tuning.

4. Bold header: Training-free and Decoupled Paradigm

The system can be designed as a fully decoupled and training-free paradigm, replacing costly fine-tuning with topology-aware prompting and efficient inference by reformulating GSL as an encoding tree optimization task rather than relying on iterative retraining or direct edge prediction.

5. Bold header: Scalability and Efficiency

The improved system can achieve superior efficiency by shifting complexity from the edge level to the node/community level, reducing inference cost, and using a composite scoring mechanism for large-scale graphs to prioritize optimization and sampling on top-ranked candidates.

The emergence of large language models (LLMs) has popularized text-attributed graphs (TAGs), creating an urgent need for graph structure learning (GSL) methods that effectively leverage textual information. However, existing GSL approaches are designed for traditional graphs without text, and adapting them to LLMs faces two challenges: defining a suitable optimization objective given LLMs' massive parameters, and designing an efficient architecture without costly fine-tuning. To address these, we propose LLaTA (Large Language and Tree Assistant), which reformulates GSL as a tree optimization framework---shifting from training edge predictors to designing a language-aware tree sampler. LLaTA constructs structural encoding trees via entropy minimization to capture topology, then leverages tree-guided LLM in-context learning to integrate textual semantics without fine-tuning. Extensive experiments on 11 datasets demonstrate LLaTA's flexibility with any backbone, superior scalability over LLM-based GSL methods, and state-of-the-art effectiveness across diverse domains.