Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models

We thank reviewer gfhg’s time in reviewing our paper and their constructive comments. Below we try to address the concerns.

1. [Convergence of BP]

We acknowledge that there is no general convergence guarantee for BP on graphs with loops. However, LLM-BP does not require BP or its approximate variant (BP appr.) to converge. The purpose of incorporating BP (or BP appr.) is to demonstrate the principled use of neighbor information. Even without full convergence, each BP iteration corresponds to a single round of statistical inference based on neighbors and can still yield meaningful performance gains. As shown in our experiments, running BP to full convergence is not necessary to achieve strong predictive performance. A few iterations are often sufficient to realize the benefits of structured information propagation.

2. [Variance metric in Table. 2]

Below, we report the results of a significance test evaluating the improvements from LLM-BP. Each method was run 100 times per dataset with 100 different random seeds. The table presents the estimated lower/upper bounds of performance improvement under 90% confidence interval, along with the $p$-values for statistical significance. Comparisons are listed in the first column.

As highlighted in bolded texts, task-adaptive encoding yields statistically significant improvement over LLM2Vec on 9 out of 11 datasets, and outperforms Text-Embedding-3-Large on 8 out of 11. Furthermore, LLM-BP provides statistically significant gains over task-adaptive encoding on 10 out of 11 datasets, while LLM-BP (appr.) achieves improvement on all 11 datasets.

2. [Sensitivity Analysis]

Thanks for the advice in sensitivity analysis on the edge number in predicting homophily ratio. The results of prediction by GPT-4o-mini and ground truth are as follows, which exhibits a stable prediction with the sampled edge number from 40 to100:

3. [Computational Overhead Analysis]

It is unclear to us why querying two nodes simultaneously would introduce significant computational overhead. To clarify, the complexity of LLM-BP consists of two main components:

First, obtaining node or class embeddings using an encoder has the same order of complexity as the baseline methods.

Second, the BP (or appr.) step can be viewed as a non-parametric GNN. Therefore, its computational complexity is comparable to that of standard GNN-based baselines. Moreover, in contrast to methods involving graph adaptors coupled with LLM decoders, LLM-BP is more time-efficient, as it does not rely on the costly decoding process of LLMs.

If there are specific concerns regarding computational complexity that we may have overlooked, we would greatly appreciate further clarification.

---

We hope that we have addressed the concerns of reviewer gfhg, we would be happy to respond to any other questions.

We sincerely thank the time and efforts reviewer JRhf took to review our paper. Reviewer JRhf provides some insightful questions and constructive suggestions to further improve the paper’s quality. Below we try our best to address the concerns:

1. [Connections with other works]

We agree that in-context encoding has been shown in prior work (e.g., [1]) to improve text embedding quality, and we will revise our manuscript to strengthen the discussion of these connections. However, to the best of our knowledge, no existing work has explored or claimed that incorporating class information improves embedding quality in classification tasks, let alone in the graph domain. We therefore consider this a novel contribution of our work. That said, we would greatly appreciate it if the reviewer could point us to any relevant studies we may have missed, and we would be glad to further discuss and cite them in the revised paper.

2. [Zero-shot experiment setting with SBert]

The reviewer's understanding is correct. The evaluation of SBert is as follows: 1) Obtain the class embeddings and node embeddings with SBert 2) directly compare the cosine similarity between node embeddings and class embeddings, assign it to the class with highest similarity score. Note that this process does not involve any graph structure usage, and it still could achieve better zero-shot performance than the LLMs-with-Graph-Adaptor baselines that require alignment.

3. [LLM-BP’s advantages on heterophilic data]

Thank you for the comment. We offer two clarifications in response:

First, on certain heterophilic datasets such as Cornell, the quality of LLM-generated node embeddings is indeed high, which can yield strong performance even without leveraging graph structure. However, this is not always the case. For other heterophilic graphs (Texas and Washington) where the node embedding quality is comparatively lower, relying solely on LLM embeddings proves insufficient. In these cases, the BP algorithm significantly improves classification accuracy.

Second, we acknowledge that the performance of class embeddings on heterophilic graphs may have been somewhat overestimated in our original setup. Because heterophilic datasets typically have fewer nodes, sampling 20× the number of classes (as we did for larger homophilic graphs) to derive class embeddings, covers nearly a third of all nodes in heterophilic graphs. This made the class embeddings overly similar to the mean of node embeddings, thus obscuring the differences between baselines.

In updated experiments, we revised the sampling ratio to 3× and 5× the number of classes for these smaller graphs. Under this adjusted setup, the improvements provided by LLM-BP, through both task-adaptive encoding and the BP algorithm, become much more pronounced, reinforcing its advantage in heterophilic settings.

4. [Typo in Equation 5.]

Thanks for pointing out the typo, the $q^C_k$ here in Equation. (5) should be fixed with $h^C_k$.

[1] Making text embedders few-shot learners. Chaofan Li, MingHao Qin, Shitao Xiao, Jianlyu Chen, Kun Luo, Yingxia Shao, Defu Lian, Zheng Liu. ICLR 2025.

We thank reviewer ppW1’s time and effort for reviewing the manuscript and their constructive comments. Below, we respond to the three concerns raised by the reviewer:

1. [Average Ranking]

We respectfully offer a different perspective on this comment. First, it seems that one of our key contributions may have been overlooked: to the best of our knowledge, LLM-BP is the first approach to design zero-shot graph algorithms that generalize effectively across both homophilic and heterophilic graphs. We emphasize that strong zero-shot performance on heterophilic graphs is equally important, particularly since prior works have not demonstrated this capability.

To further address the reviewer’s concern, we provide detailed average rankings (based on accuracy and F1 score) across three sub-categories: Citation and E-Commerce (homophilic), and School Webpage (heterophilic). LLM-BP consistently achieves the highest ranking across all three. For clarity and fairness, we will include these sub-category rankings in the revised version of the manuscript.

2. [Empirical gain of LLM-BP over GPT-4o on homophily data]

We respectfully disagree with this comment. As noted in our paper, strong zero-shot performance on heterophilic graphs is equally important, particularly because prior works have not demonstrated such capability. Even on homophilic graphs, LLM-BP still significantly outperforms GPT-4o on 5 out of 7 datasets.

More importantly, LLM-BP introduces a generalizable graph information aggregation mechanism, which GPT-4o fundamentally lacks. This is a core contribution of our work that goes beyond empirical results. Specifically, GPT-4o relies heavily on high-quality node text and cannot leverage graph structure. In contrast, LLM-BP is designed to incorporate structures, which is critical in many real-world scenarios where node text may be noisy or sparse.

To highlight this point, we conducted follow-up experiments on three large citation datasets using the same graph structures but with degraded text inputs: only paper titles were used as node attributes. Under this low-text-quality setting, LLM-BP and its variants significantly outperform GPT-4o, underscoring the value of structural information and the effectiveness of our approach.

3. [Pre-training Free Claim]

Thank you for pointing this out. To ensure rigor and avoid any misunderstanding, we will revise the claim in our manuscript to clarify that “no additional fine-tuning of LLMs is required compared to existing baselines.”

Our main argument is that LLM-BP does not require further fine-tuning, which leads to significantly improved computational efficiency relative to most baselines that rely on fine-tuning, even if they also leverage LLMs.

---

We hope this response addresses the reviewer’s concerns, and we would be happy to provide further clarification if needed.

We sincerely thank reviewer JW3s’s time and effort in reviewing the paper. We are also thankful for the constructive suggestions. Below we try to address the concerns from reviewer JW3s:

1. [New Class with limited data]

LLM-BP does not require abundant data from new classes and can generalize to novel classes even when data is limited. Consider an extreme cold-start scenario with only a single node from a new class:

Due to the scarcity of nodes in the new class, it is unlikely that edge probability estimation will involve edges connected to this new node. As a result, the estimated edge probabilities between the new class and known classes will be extremely low. According to the BP rule, this leads to an aggregation that minimizes the influence of neighboring nodes on the new node’s label. This behavior aligns well with standard practice in cold-start settings, where predictions for new classes should rely more on the node’s own attributes than on potentially misleading signals from sparse or noisy connections.

Regarding class embeddings, one could directly use text descriptions of the classes. However, we chose not to adopt this approach in the current work, as the resulting embeddings can vary depending on the phrasing of the description. Instead, we propose a more robust strategy: sampling a few nodes from each class and aggregating their embeddings to form a stable class-level representation. That said, for cold-start scenarios, using text-description-based class embeddings remains a viable and potentially effective alternative.

2. [Applying LLM-BP to Graph-level Tasks]

This issue is precisely the focus of our planned future research. The current LLM-BP algorithm cannot be directly applied to graph-level tasks, as both the task-adaptive embedding and the BP mechanism are specifically designed for node-level settings.

That said, this limitation does not undermine the core message of our work: when resources are insufficient to train complex adaptors that align graph data with LLMs, strong generalization requires algorithmic designs that (1) adhere to two high-level principles (attribute unification and unified information aggregation) and (2) are tailored to the structure of the downstream task. In this work, we focus on node-level tasks as a proof of concept to illustrate these principles, demonstrating that they can lead to strong generalization performance even under resource constraints.

3. [Limitation in QA tasks]

We agree with the reviewer’s point. Flexible QA should further involve LLM decoders, while how to combine graph structure with LLM decoders in a practically generalizable way remains an unsolved question and we are eager to research with.

4. [zero-shot link prediction]

For zero-shot link prediction tasks, our explanation is as follows: For the baseline, as mentioned in the paper, the LLM-with-adaptor baselines are not trained on link prediction tasks and are only trained on node-level tasks, while the strong performance of ours comes from the high-quality node embedding via BP.