Generalization Principles for Inference over Text-Attributed Graphs  with Large Language Models
Authors: Haoyu Peter Wang
Shikun Liu
Rongzhe Wei
Pan Li
Venue: ICML 2025 poster (2025)
Keywords: text-attributed graphs
zero-shot learning
large language model
Primary area: applications

Abstract: 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.

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
Haoyu Wang' Shikun Liu'
Rongzhe Wei
Pan Li
Abstract
1. Introduction
Inspired by the remarkable generalization capabilities of foundation models for text and image data (Achiam et al., 2023; Liu et al., 2021; Radford et al., 2021), researchers have recently explored extending these successes to graph data (Liu et al., 2023b; Mao et al., 2024; Zhao et al., 2023a; Fan et al., 2024; He et al., 2024), aiming to develop models that generalize to new or unseen graphs and thereby reduce reliance on costly human annotation (Li et al., 2024f; Chen et al., 2024d; Feng et al., 2024; Li et al., 2024g). Among various types of graph data, text-attributed graphs (TAGs) have found wide range of applications. These graphs com- bine both topological relationships and textual attributes associated with each node, which naturally arises in recom- mendation systems (where user and item nodes may have textual descriptions or reviews) (Bobadilla et al., 2013), aca- demic graphs (where publications include extensive textual metadata) (McCallum et al., 2000; Giles et al., 1998), and financial networks (where transactions and accounts come with textual records) (Kumar et al., 2016; 2018). Given the labeling challenges posed by cold-start problems in recom- mendation systems or fraud detection in financial networks, methods that can operate with limited labeled data are eru- cial. In particular, robust zero-shot node labeling across unseen TAGs has become area of great interest.
Large language models (LLMs) have recently been introduced to graph learning, aiming to ex- tend 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 meth- ods 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 gener- alization and derive the framework LLM-BP ac- cordingly: (1) Unifying the attribute space with task lask-ade embeddings, where we leverage LLM-based encoders and task-aware prompting to enhance generalization of the text attribute em- beddings; (2) Developing a generalizable graph information aggregation mechanism, for which we adopt belief propagation with LLM-estimated parameters that adapt across graphs. Evaluations 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 code2 and adsk-ade embeddings' are publicly avail- able.
Numerous studies have been dedicated to inference tasks on TAGs. Early efforts have primarily focused on adapt- ing pre-trained language model (LM) encoders (Li et al., 2024e; Fang et al., 2024), sometimes in combination with graph neural networks (GNNs) (Hou et al., 2022; Veličković et al., 2018), to incorporate structural information. How- ever, these approaches often struggle to achieve strong gen- eralization performance, largely due to the limited capac- ity of the underlying models. With the advent of large language models (LLMs) (Kaplan et al., 2020; Huang & Chang, 2022), researchers have proposed two main strate- gies for integrating I.LMs into TAG inference: 1) Direct Node-Text Input. Here, raw node texts are directly fed into LLMs. This method demonstrates reasonably good zero-shot performance on TAGs when text attributes are highly informative for node labels (Chen et al., 2024c; Li et al., 2024d). However, when the textual attributes are in-
'Deaarmment Electrical and Computer Engineering, Geor- gia Institute of Technology, Atlanta, GA, USA. Correspon- dence to: Haoyu Wang <haoyu.wang gatech.edu>>, Pan Li opanli@gatech.ede
Proceedings of the ndnd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Paltpe:/ /allpe://qāte www.hhub..o//aaaaaaoaaaaa COM/LIM
attpa: http://ttggggg....e////// co//aattasets//aapp-coa Text Text-Artribstedd-ee Grahd

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
Attt-Attribtte Graph
Princinle Unifvina the Text Space and Choaining Tacb-Achptive Fitheldings
Principle Dt: Developing Ginerniizable Adartive
Oruch Infermation Apreztion Mechanien
a It condidess hoood at II Universie, specializing in theoretical plysies He Secuses quastum Seid theory and the fundamennal petteiples paniele interactions (stuslont, plunios)
-isinee We heve noo anpeasee fowe
-leeee inleas
Aung- Sehreing 8
Stonee Giee douns ass the Johoriig duunr
de folloring 8 catiggrien Stalen matill fecalty For luctr fallows:
Step (1)
Hazaplably Ruis
Pleose wletbrr follog
cirquess
7 & [c] edgy pains
entogory
No reanosing step.
Hanoopaly
Edge Potential desermne by
Du. professe B Universit spectalizing condensed mattr sias Her rosearch explares cuztium muterial emergent eloctroric phenomeros (Jucsly, plystoo)
Faally
Strp(3)
denks
Stop (4) Inference
Codae Santacly
Inittll Sal-Potential
Stup() Reliof Progugation
studeutt
Task-Adaptive Embbolding
Figure 1: The two generalization principles and the framework of LLM-BP.
sufficient, it becomes necessary to aggregate information from larger neighborhood in the graph, while this is con- strained by the limited context length LLMSs can digest and reason over. 2) Embedding- approach, node texts and their neighboring structural in- formation are first encoded into compressed embeddings, which are then processed by LLMs (Chen et al., 2024b; Tang et al., 2024a; Luo et al., 2024; Wang et al., 2024; Zhang et al., 2024a). Because LLMs are not inherently trained on arbitrary embedding spaces, aligning these em- beddings with the LLM's s token space is essential an idea partly inspired by how modal data (Radford et al., 2021; Zhai et al., 2023). How- ever, unlike the vision-language domain, where large-scale text-image pairs (Schuhmann et al., 2022) are abundant, the graph domain typically lacks comparable datasets. This scarcity reduces the model's generalization in practice.
task-adaptive prompting (Kong et al., 2024). However, to handle the large-scale graph aggregation discussed later, we require these capabilities to extend beyond raw text to an embedding space. Hence, we propose to adopt LLM- based encoder models such as LLM2Vec (BehnamGhader et al., 2024; Li et al., 2024a) for text embedding. Al- though this approach might appear to be naive extension of smaller LM-based embedding methods (e.g.. those relying SBERT (Reimers, 2019) or RoBERTa (Liu, 2019)), we ar- gue that leveraging the decoder-induced encoder structure of LLMs is essential for achieving task-adaptive embeddings. In particular, we introduce a novel prompting strategy that encodes text attributes conditioned on inference-task de- scriptions, enabling significantly improved zero-shot infer- ence an ability not readily achieved by smaller LM-based embeddings.
Integration. In this
models align multi-
Principle II: Developing generalizable adaptive graph information aggregation mechanism. Graph structure de- termines the node neighboring relationships and thus the information aggregation from which nodes may benefit the inference. Inspired by the belief propagation (BP) algo- rithm (Murphy et al., 2013) that gives the optimal statistical inference over pairwise correlated random variables, we pro- pose to regard the graph each node as random variable, and mimic BP to aggregate information for node label inference. Because BP is rooted in basic mathematical principles, this approach is widely generalizable. Algorithmic adaptivity across different TAGs hinges on estimating the coupling coefficients in the graphs, which can be done by having LLMs analyze the attributes of sampled pairs of connected nodes. Moreover, this BP- inspired approach naturally adapts to varying levels of text attribute quality: nodes with higher-quality text attributes present greater influence on their neighbors, and vice versa.
In contrast to prior heuristic approaches, this work aims to design a method from first principles for robust zero- shot generalization on TAGs. Because TAGs are inher- ently multimodal, the proposed method must simultane- ously address potential distribution shifts in both textual attributes and graph structure. Specifically, text attributes can vary widely, for example from scientific papers (Mc- Callum et al., 2000) to e-commerce product reviews (Ni et al., 2019). Edge connection patterns can range from ho- mophilic graphs such as citation networks, where papers on similar themes are linked (Giles al., 1998), to heterophilic graphs such as webpages. which connect nodes with dis- tinct topics (Memyei & Cangea, 2020). Moreover, the la- beling task itself can shift which requires a task-adaptive approach to process both textual features and network struc- ture. Consequently, the core insight behind our model de- sign is grounded in the following two key principles.
Markov Random Field (MRF),
Principle I: Unifying the text space and obtaining task-adaptive embeddings. LLMS offer powerful text- understanding capabilities that naturally unify the textual feature space, and have recently been shown to benefit from
By applying the two principles outlined above, we pro- pose our new strategy, LLM-BP, for zero-shot inference over TAGs. LLM-BP -P does not require any training or fine- tuning. We evaluate LLM-BP on 1l real-world TAG datasets
2

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
from various domains, including citation networks (McCal- lum et al., 2000; Giles al., 1998; Sen et al., 2008), e- commerce (Ni et al., 2019), knowledge graphs (Mernyei & Cangea, 2020), and webpage networks (Craven et al., 1998), covering both homophilic and heterophilic graph structures.
In contrast to the above effort that adopts smaller LM en- coders, works that involve the use of LLMS are reviewed in the following and may achieve better generalization. More related works including LLM-based data augmentations for GNN training for generalization and L.MSs for other graph reasoning tasks can be found in Appendix. A.
Experimental results demonstrate the effectiveness of LLM- BP. Notably, our cond-conditional embeddings (Principle 1) improve performance by 8.10% on average compared to the best LM- L.M-aased encoders. In addition, our BP-inspired aggregation mechanism (Principle II) provides an extra 1.71% performance gain with our embeddings, demonstrat- ing strong generalization across both homophilic and het- erophilic TAGs. Our experiments also reveal that current methods aligning graph-aggregated embeddings to L.LM token spaces significantly underperform approaches that simply use smaller LM encoders without even incorporating graph structures. This outcome indicates that the primary source of generalization in these methods is the smaller LM's text embeddings, rather than LLM-based reasoning on embeddings. It reinforces our earlier argument that lim- ited training data hinders effective alignment in this context, urging caution for future work considering this strategy.
LLMs with Node-Text Input. LLMs being directly fed with raw node texts demonstrates strong zero-shot ability TAGs (Chen et al., 2024c; Huang et al., 2024; Li et al., 2024d). However, they suffer from the limitation of not being able to incorporate graph structural information.
LLMs with Graph-Embeddingg Input. With smaller LMMencoded node embeddings, various strategies integrate graph structure by aggregating these embeddings, such as neighborhood-tree traversal or concatenating the aver- aged embeddings from different hops (Chen et al., 2024b; Tang et al., 2024a; Luo et al., 2024), or via pre-trained GNNs (Zhang et al., 2024a; Wang et al., 2024). As men- tioned earlier, these methods rely on aligning embeddings with the LLMs' token space. For instance, LLaGA (Chen et al., 2024b) trains a simple MLP on citation networks and (Wang et al., 2024) employs linear projector on the ogbn-Arxiv (Hu et al., 2020) dataset, both using the next- token prediction loss, while (Tang et al., 2024a) adopts self self-super structure- aware graph matching as the train- ing objective. However, due to limited TAG-domain data, the space alignment in these methods often remains under- trained, leading to degraded performance.
2. Related Works
Here, we briefly review existing methods by examining how they enable model generalization across TAGs.
Tuning Smaller LM Encoders. These methods typi- cally rely on source-domain graph for training. No- table works include ZeroG (Li et al., 2024e) that tunes SBert (Reimers, 2019) source datasets to align class- description embeddings with node text, thereby enhancing zero-shot performance on target datasets. Another approach, UniGLM (Fang et al., 2024), fine-tunes BERT (Kenton & Toutanova, 2019) using contrastive learning on source datasets yield a more generalizable encoder. GNNs trained with UniGLM embeddings in a supervised manner outperform models that directly adopt LM embeddings.
Multi-Task Graph Foundation Models. More ambitious studies aim to generalize across various graph-related tasks within a single framework. Notable approaches include graph prompting (Liu et al., 2023c), which introduces "prompting nodes" to transform diverse graph tasks into a unified format. These frameworks then train GNNs to address the tasks (Li al., 2024e; Liu et al., 2023a; 2024) or further integrate LLMs (Yang et al., 2024; Kong et al., 2024). Although these works are impressive, they still fail to achieve zero-shot performance comparable to those methods that focus on specific graph data domains.
Training GNNs for Generalization. These methods focus on leveraging graph structure in a generalizable manner. Among them, graph self-supervised learning (Liu et al., 2022) is particularly common for producing representations without labeled data, often employing contrastive learning or masked modeling (Veličković al., 2018; Hou al., 2022: Zhao et al., 2024). GraphMOE is more recent technique inspired by the success of mixture-of-expers (Shazeer et al., 2017), pre-training parallel graph experts targeting different structures or domains (Hou et al., 2024; Liu et al., 2024: Xia & Huang, 2024; Qin et al., 2023). Others also consider LM-GNN co-training including (He & Hooi, 2024; Zhu al., 2024) that also follow constrastive learning idea. Note that, however, all these methods still require training.
3. Generalization Principles for LLM-BP
3.1. Notations and Problem Formulation
Let (G,X, Y) represent a TAG of interest, where g(V, denotes the graph structure, V is the node set of size n, and E is the edge set. The node textual attributes are represented as X = (X1. X, and each node belongs to one of c classes, with labels given by Y = {V1, V2, .... yn E [c]".
The objective is to infer the labels of nodes in TAGs based on the node attributes and graph structure. This study primarily focuses on the zero-shot setting, where no labeled data
3

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
are assumed be available in advance. Additionally, a few-shot setting is considered, where & labeled nodes are known for each class. Due to space limitations, results for the few-shot setting are provided in Appendix D.6.
Tang et al., 2024a; Wang al., 2024). However, for these embeddings to be directly usable for label prediction without the need for additional transformation models, it is crucial to incorporate task-specific information. In other words, the embeddings must be tailored to the specific task, resulting in what we term lask-adaptive embeddings.
3.2. Motivation and the Overall Framework
LLMs are commonly used as decoders for next-token pre- diction. While LLMs excel at processing natural language inputs, they are not inherently compatible with graph data. Recently, some studies have explored methods to integrate graph data into LLMs, primarily for reasoning tasks (Perozzi et al., 2024; Zhang et al., 2024c; Tang et al., 2024b).
Achieving task adaptivity, however, presents a notable chal- lenge. Smaller LM encoders lack the expressive power nec- essary to encode nuanced task-specific information. This limitation motivates our adoption of LLM-induced encoders, driven by the emergent capabilities of LLMs in contextual learning (Sahoo et al., 2024; Chen et al., 2023).
In the context of TAGS, accurate node label inference relies on effectively combining the attributes of multiple nodes, es- pecially when a node's 's individual attributes are insufficient to determine its label. However, as noted earlier, L.MSs are constrained by limited context windows, making it challeng- ing to process all attributes from the potentially large set of connected nodes. Traditional approaches to compressing graph structural information involve creating embeddings, such as using GNNs to aggregate information from the tar- get node's 's neighbors. While effective, these embedding methods do not seamlessly integrate with LLM inputs and often require non-trivial training effort to align the LLMs' token space with the node embedding space (Chen et al., 2024b; Wang et al., 2024; Tang et al., 2024a).
There have been recent advancements extending LLMs to generate text embeddings (BehnamGhader et al., 2024; Muennighoff al., 2022). In our approach, we utilize a form of LLM2 (BchnamGhader et al., 2024), which transforms L.L decoders into encoders via retaining the unidirectional attention mechanism. Following the method- ology in (Li et al., 2024a), we extract the output embedding of (response) the token positioned immediately after the inputs - as the text embedding for the input node attributes.
To embed task-specific information into node embeddings. we propose prompting strategy structured with the follow- ing template:
(Instruct) (askkdescriptionn) ) {class ( (query) X, (responss) (I)
Our approach, LLM-BP, does not confine LLMs to their traditional usage. We first leverage their capabilities to gen- erate adaptive node embeddings. Then, instead of re- quiring LLMs to directly process these embeddings, LLMs are further employed to analyze graph data and provide gen- eralizable guidance in aggregating these embeddings. These two steps are to match the two generalization principles proposed in Sec. 1. Classification is ultimately performed by computing the cosine similarity between the final node
Here, (.) encloses specific tokens. The task details are de- scribed in {task deasckktccripionn J. and polass.info) contains the basic information of each class. An example is given in Fig. 1. The class information serves as a crucial contex- tual enhancement, enabling LLMs to generate embeddings in a conditioned manner. For more detailed on the class- conditional prompt for each dataset used in this study, refer to Appendix. B.2 and E.I.
embeddings h = |nx ...., Nxx and candidate class em- beddings qº = [of ..... g. In the zero-shot setting, class embeddings are generated as follows: we randomly sample I << n nodes and employ LLMs to infer their labels. The embeddings of sampled nodes form distinct clusters based on L.MS' prediction. We compute the average embedding of the embeddings closest to the cluster center to obtain the class embedding. In the few-shot setting, class embeddings are obtained by averaging the embeddings of labeled nodes within each class. See Appendix. B.2 for details.
3.4. Principle II: Generalizable Graph Aggregation
Graph structures can provide essential correlated informa- tion for node label inference by characterizing the relation- ships between node attributes and labels (Zhu et al., 2003; Kipf & Welling, 2016; Veličković et al., 2017; Hamilton et al., 2017; Zhu et al., 2020; Wei et al., 2022).
Specifically, we may consider each node's label and at- tributes as random variables, and each edge as a coupling between them for connected node pairs. The fundamental BP algorithm enables principled statistical inference over this set of correlated random variables (Murphy et al., 2013). Since BP is inherently agnostic to the application domain of the TAG, emulating BP offers a mechanism to aggregate cor- relation information encoded in the graph structure across domains.
3.3. Principle I: Task-Adaptive Node Embeddings x
Creating generalizable text embeddings is no longer a sig- nificant challenge. Even smaller LM encoders, such as SBert (Reimers, 2019), are capable of achieving this. In- deed, most existing works utilize these encoders to generate initial node embeddings for TAGs (Chen et al., 2024d;b;
4

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
Markov Random Field Modeling We consider the joint probability distribution PY((, X) over the graph where Y and X denotes the random variables of node labels and attributes, respectively. In (Y,(). the distribution over the node labels given the graph structure is denoted as
Algorithm 1 LLM-BP
input TAG XX.
output Class label prediction (ūr)een))
1: h <- Task-adaptive encoding following Eq. (1)
2: if zero-shot then
Po(Y)
1 Zx
II (i(w)) (KJ)EE
II
(he My).
3: Sample ( < n nodes, infer labels with LLMs,
4: Nodes clusters based on LLM prediction,
5: q + Average embedding of samples near center,
Here (b(()) denotes the unary potential for node (1j(Ui Uj) is the edge potential capturing the correlation between labels y: and y/ of adjacent nodes, and Zy is the normalization constant. For node attributes, MRF model- ing assumes that each node's attributes are conditionally independent of others given the node labels, which can be characterized by the distribution:
else if few-shot then
7: qo +- Average embedding of k samples per class,
8: end if
9: Estimate (Vi, Uj) by employing the LLM to analyze the graph data (e.g., using Eq. (6) based on the estimated
homophily level r.)
10: Initialize ( (B+) <- Eq. (5) and m m
II: Run LLM-BP (Eq. (4)) for L iterations or its approxi-
P Y) II P vi) = II VVV
Pv. (X,)
Pv.
(3)
mation (Eq. (7)) for single iteration
.EV
12: d
arg maxy. log (k) (11:
where Sy, (X;) captures the likelihood of having node i's attributes X, given its label y/:
LLM-BP To execute the above LBP algorithm, we need to specify several components based on the TAG. First, pi (0) (w:) represents the distribution of the label ys given the observed attributes X, alone, which can be estimated using normalized cosine similarities:
The proposed modeling approach is highly adaptive, as it can capture the varying graph connectivity patterns across different TAGs through interpretable edge potentials. For instance, (br( Mj) represents the unnormalized likelihood that nodes with labels y and yy are connected. This for- mulation naturally incorporates the modeling of graph ho- mophily and heterophily: Whig (Vt.
(0) P1 (1s) softmax(fcos( (
this (Vi.y)) yj) indi- cates homophily, while this (Vi: W:) < (Vt Uj) reflects heterophily. Furthermore, Py, (X,) enables the model to account for variations in the quality of text attributes (w.r.t. their indicative power for the labels) across different TAGs, further enhancing its adaptivity. For node classification, we can infer IP& X) & Hivv xpx (w:) HKLEE Vig (yi, Mn) where xx (v.) = Pr. (V1)..
(5)
where ht and Je denote node i's class-conditional embed- ding and class k's embedding given by the LLM encoder as discussed in the previous section. cos(-) denotes cosine similarity and is the temperature hyper-parameter.
Second, we characterize the edge potentials vhy My)) We employ an LLM agent to assess the homophily level of the TAG. Specifically, we uniformly at random sample T connected node pairs (T < [[)), and for each pair, we prompt the L.MM to determine whether the two nodes belong to the same class based on their attributes, as illustrated in Fig. 1. The ratio of "Yes" responses, denoted by r is used to set
Belief Propagation Exact inference for XX) is in- tractable in large-scale graphs with cycles (Koller, 2009). In practice, loopy belief propagation (LBP) is often used to con- duct an approximate inference (Murphy et al., 2013), which follows: Initialize the distributions p) (y,) x yx, (1:) and (0)
m (1,) 1/c for all j V. For k 1,2, L. we do
log m (k) (v) = LSE,, [log (vo. (k- (U,) log m log pj
(4)
bhyy (ig(M.n
r, r. if ys 7 Uj
if U y
(6)
(k- 1) (11)).
log (8) (y.) ~ log p; (y)) + Σ log m (k)
p
( (21),
Note that a more complex ( v5) can be adopted by estimating the edge probabilities between any two classes. However, we choose the homophily level as proof of con- cept. LLMs can provide a reasonably accurate estimation of the homophily level, as pairwise comparisons are typically much simpler tasks compared to full-scale classification.
JEN(0
where z denotes the equality with difference up-to constant. LSE stands for the log-sum-exp function: LSE,, (fr, m;)] = log Ew; exp(f(ur, [.)). The final arg maxy; Pi
(44) (yx) gives the label prediction. Detailed
(Wei et al., 2022) demonstrated that linear propagation can approximate single iteration of LBP when feature quality
derivation can be found in Appendix. C.
5

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
Dataset
Text Domain
Graph Structure
2024e), UniGLM (Fang et al., 2024) that tune LM encoders,
Cora (McCallum et al., 2000)
CS Publication
Homopholic
ZeroG is specifically proposed for zero-shot node classifica-
Citeseer (Giles et al., 1998)
CS Publication
Homopholic
tion. DGI (Veličković et al., 2018), GraphMAE (Hou et al.,
Pubmed (Sen al., 2008)
Medical Publication
Homopholic
History (Ni
2019)
History Books
Homopholic
2022) that perform Graph-SSL are also compared.
Children (Ni et al., 2019)
Children Literature
Homopholic
Sportsfit (Ni et al.,, 2019)
Sports Goods
Homopholic
L.Mss with Graph Adapters: including LLaGA (Chen et al., 2024b), TEA-GLM (Wang et al., 2024), and GraphGPT (Tang et al.. 2024a), which are the three rep- resentative works adopting LLMs with projectors to align compressed node representations with the token space.
Wikics (Memyei & Cangea, 2020)
Knowledge Graph
Homophotie
Cornell (Craven
1998)
School Wehpage
Heterophilic
Texas (Craven et al., 1998)
School Webpage
Heterophilic
Wisconsin (Craven et al., 1998)
School Webpage
Heterophilic
Washington (Craven et al., 1998)
School Webpage
Heterophilie
Table I: TAG Datasets selected in experiments. is limited. Based on this insight, we adopt the following approximate LBP formulation (denoted as BP appr.):
Multi-Task Graph Foundation Models: Consisting of OFA (Liu et al., 2023a) and GOFA (Kong et al., 2024), which are the state-of -f-the- multi-task foundation models.
log Pi (2) (1:) = log (0) (vi)+
L.MSs for Data Augmentation: referring to LLM- GNN (Chen et al., 2024e), specifically designed for zero- shot node classification, which utilizes LLMs as annotators for pseudo-labels and further train GNNs for inference.
logp; (0) (wi). glog 1 JEN(()
where the homophily level influences the sign of the log- likelihood aggregation from neighboring nodes. We sum- marize the overall pipeline in Algorithm. 1
Neighborhood Aggregation (NA); referring to the training- free method proposed in (Yang et al., 2024), which injects graph structural information into node representations by di- rectly aggregating the averaged neighborhood embeddings.
4. Experiments
Settings: Unlike LLM-BP which does not require addi- tional fine-tuning of LLMs, most of the baselines- except from vanilla encoders, LLMs or NA- MA-require fine-tuning. Methods of vanilla encoders and LLM-BP that require sam- pling nodes to obtain class embeddings under zero-shot settings are repeated 30 times with seed 42 to 71, and the average performance is reported in the following experiment sections. Implementation details for baselines and L.MMBBP can be found in Appendix. B.3 B.2.
In this section, we evaluate L.MM-PP based on its two design principles, with primary focus on zero-shot node classi- fication tasks. Evaluations of few-shot node classification and link prediction tasks are provided in Appendix. D.6 D.7. First, we demonstrate the effectiveness of task-adaptiv en- coding and identify issues with existing methods that rely on aligning node embeddings with the LLM token space. Second, we validate the effectiveness of the proposed BP algorithm. Finally, we present the end-to-end performance of LLM-BP, comparing it to state-of-the-a -tt---rrtt baselines. We first introduce the datasets and baselines used in the study:
4.1. Evaluation for Task-Adaptive Node Embedding
Exp.1: Ineffectiveness of LLMs w/ Graph Adapters
Datasets As listed in Table 1, we selected eleven real- world TAG datasets that encompass a variety of text do- main shifts, including citation networks, e-commerce data, knowledge graphs, and webpage networks, which cover both homophily and heterophily structures. For more de- tails, see Appendix 1.
Figure 2 illustrates the accuracy of basceder-baeed meth- ods alongside two representative LLMs- graph- methods across each dataset. Notably, using text embed- dings generated by SBert (Reimers, 2019) without incorpo- rating graph structural information significantly outperforms both LLaGA (Chen et al., 2024b) and GraphGPT (Tang et al., 2024a). These two methods align node representations that combine SBert embeddings with graph information to the LLMs' token space via projector. This finding suggests that the generalization capabilities of these approaches pri- marily stem from the pre-trained language model encoders rather than the LLMs' inherent understanding of TAG data. Consequently, future works should exercise caution when adopting this strategy.
Baselines:
We select representative baselines from all exist- ing categories for model generalization on TAGs:
including Sentence- BERT (SBert) (Reimers, 2019), RoBERTa (Liu, 2019), text- umbedding-3-largee (OpenAI, 2024), and bge-en-icl (Li et al., 2024a), a state-of-the-ard LLM2Vec encoder.
Vanilla LM/ / LLL Encoders:
Vanilla LLMs: including GPT-3.5-turoo (Achiam et al., 2023) and GPT-40 (Hurst et al., 2024), the latter being among the most advanced LLMs in reasoning. They process raw node texts without incorporating graph structures.
Exp.2: Effectiveness of The Task-Adaptive Encoder
According to Figure 2, the task-adaptive encoder achieves the best performance on most of the datasets, enhancing
Tuning LM Encoder / GNNs: including ZeroG (Li et al.,
6

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
History
Pubmed
Chiliiee
Children
Eourant
Spertally
Citeseer
Sportsfix
conel
Oreed
Cora
SBert (Encoder).
Roberta (Eacoder).
Eoxt-Embedidng--- 3-Largo
Wikics
Figure 4: Class information fed into different encoders.
Washington
Cornell
in Fig. 4, incorporating class information into smaller LM encoders, such as SBert (Reimers, 2019) or RoBERTa (Liu, 2019), may even degrade performance. Regarding Text- embeddingg3- (OpenAI, 2024), the impact of class in- formation remains inconclusive due to the unknown internal mechanisms of the black-box encoder.
Wisconsin
Texas
LLAGA
Short
LLM2Vic
GraphoPT
The hert--nbbeddiiggg---ar
Tadk-Adppiive Embedding (Ourg
Figure 2: Zero-Shot Accuracy of vanilla encoders vs. LLMMswith-Graaphe Graph-Adapters All the encoder-based methods do not leverage graph structure information.
4.2. Generalizable Graph Aggregation
Graph Type
Sampled Edlgss
Citation
100
E.Commerze
100
Know Knowledge lodge Graph
190
Weh Page
50
SBert.
Text-Embeddingg 3-Lage.
Figure 5: Left: Number of edges sampled per dataset. Right: GPT-4o-mini's prediction of the homophily level r.
Exp.3: LLM Agents for Homophily Level r Estima- tion As shown in Fig.5 (Left), we randomly sample edges (A: 100 for large graphs and A 50 for small ones), incorporating them into prompts (Fig.1) for LLM-based es- timation of the homophily level (Sec.3.4). We evaluate four LLMs: GPT-4o, GoT--s-mini(Hurstt et al., 2024), GPT- 3.5-Turbo (Achiam et al., 2023), and Mistral-7B. IB-Instruct v0.3 (Jiang et al., 2023). Each model responds to each node pair over five trials, with the final estimate determined by majority voting. Full results are provided in Fig.7 in appendix, demonstrating that GPT-4o-mini and GPT-4o ef- fectively estimate r, GPT-3.5-Tuubhe performs reasonably well, while Hiistral-BB-nnstrecl racy and cost efficiency, we select GPT-4o-mini estimation (Fig. 5 Right) for subsequent studies.
M2
Aask-Ad Facoder (Ours).
Figure 3: t-SNE visualization of encoders on Citeseer.
the vanilla L.M2Vecc on average by 2.3%, highlighting the importance of incorporating task-specific information during encoding. To further illustrate this, we use the Cite- seer (Giles et al., 1998) dataset as an example and perform t-SNE visualization (Van der Maaten & Hinton, 2008) on the embeddings derived from the encoders. As shown in Fig. 3, when provided with class information, the task-adaptive en- coder generates embeddings that exhibit tighter clustering for the same class compared to other baselines. The signif- icance test of improvement from task-adatove encoding is provided in Table. 5 in Appendix. D.1.
fails. Balancing accu-
Exp.4: Effectiveness of the BP Algorithm Experimental results are presented in Fig. 6, where we evaluate the four approaches over various graph structures. Specifically, We compare the BP algorithm (Eq. 6) and its linear approx- imation (Eq. 7) with vanilla encoders that do not utilize structure (Raw) and the NA baseline. For all the four en- coders across all the datasets, the proposed BP algorithm slightly outperforms its linear approximation, and they con- sistently outperform Raw. Moreover, in most datasets, they
Note that the benefits of class information are observed only in encoders derived from LLM decoders potentially due to their strong contextual learning capabilities. As illustrated
7

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
Homophilic
Heterophiliic
Ang Rank
Ciation Graph
E-Commerce
Knowlolge Grraph
Schools
Method
Com
Chieseer
Pubmed
Histoey
Children
Sportsiit
Wikics
Cornell
Texos
Wasconsin
Wishington
Ase
F1
Apc
F]
Acc
Acc
F1
Acc
F1
Acc
F1
Ace
F1
Acc
F1
Ace
F1
Ace
F1
Ace
Fl
Ace
F1
Shert (Reimers, 2019)
69.75 67.3 66.69
63.31
70:57
71.38
53.53
20:45
22.59
20.13
43.79
38.76
59.06
56.19
63.66
$4.59
64.58
49.79
62
10
$2.07 61.53
48.00
7.27
7.09
Roberta (Liu, 2019)
70.71 47 66,95 63.57
69.54
70.31
55.39
84
24.25
22
41.51
36.09
59.08
56.49
66,4966.668
61,68
$1.84
62:15
49.26
60.33
49.08
60.60
45.34
7.18
7.18
Text Embedding Large (OpenA1, 2024)
71.90 69.87 66.24 63.30
50.15
19.21
24.68
24.10
58.39
53.03
58.52
$1.50
70.11
75:42
63.17
73.14
57.60
5.36
4.45
LLM2Vec (BchnamGhaderr al., 2024)
67.34 65.92 67.13 64.37 74.57 74.08
53.14
19.06
25.56
24.31
57.00
52.29
62.34 58.32
$1.26
69.08
76.68
63.12
73.36
62.50
65.92
53.34
5.64
5.36
SBert + NA (Ying el al., 2024)
72,49 69.50 68. 66 64.75 71.26 71:87
57.86
21.96
96
25.28
22.74
46.84
40.85
66.26 26 63.57
54.21
44.66
56.04
41.09
54.23
46,11
58.88
43.05
5.82
6.00
G.T-3.5 (Achiame et al., 2023)
70.11 52.11 66.83 47.58 89.75 66.16
55.07
30.36 29.73
26.13
67.21
$4.45
65.53 51.19
45.54
39.30
56.14
32.53
58.56
16.81
51.09
35.66
5.64
8.18
GPT-4 4o (Hunt et sl., 2024)
70.29 62.95 64,77 47.78 89.85
67.39
53.90
31.68
30.76
29.30
66.35
56.22
66.10 56.04
45.54
41.92
63.10
50.51
56.00
52.54
48.90
42.54
5.91 6.36
UniGL M (Fong et al., 2024)
45.57 43.25 52.26 48:41 70.33 69:78
44.24
24.83 84
21.48
19.17
33:46
32,99
55.05 $2.06
23.03
22.06
21.39
18,90
27.16
26.45
24.01
23.08
11.36 9.91
ZeroG (Lá al., 202
60.4 56.02. 50.35
45.15 74.68
36.55
16.81
12.72
12.61
14.27
$0.86
10:47 6,46
53.18
15,95
12:27 12.73
iXit (Velidlooi
2018)
16.79 12.77 15:04
15.04
25,10 19.18
20.98
3,80
2.22
1/04
7.48
3,47
14.98
4.34
14.66
10.02
11:23
9,42
12.09
20.96
14.15
13.91
14.75
GriphMAF (Hon al. 2023)
15.13 7.10 8.11 7.67 36.56
34.79
16.36
5.75
7,24
1.97
30.50
6.99
8.91
4,03
23.04
14.95
17.65
11.67
23.02
11.87
24.89
13.34
15:18 15:45
OFA (Liu at al., 2023g)
20.36 16.57 41,31 33.37 28.18 26.62
8,25
3.48
3.05
2.29
15.18
4.7
30.77
25.22
29.84
12.62 11.77
5.87
4.8
3.44
6.04
4.28
13.91
14.73
GOFA (Kong et al., 2024)
71,06 70.21 65.72 64.18
74.76
73.00
56.25
31,57
12.15
7.73
31.87
33.19
68.62
62.91
39.50
35.47
38.37
29.54
32.51
25.12
31.02
21.24
8:00 7.45
GrsphCPPT (Ting et al., 2024s)
17.48 12:68 13.93 12.78
42.94
25.68
12.31
9.15
9.94
4.04
4.53
7,44
33.59
30.21
10.18
14.71
18.48
9.85
12.35
6.32
20.64
15.79
14:55
14.64
LLAGA (Chen 2024
11,62 14.42 19,52 23.34 7.56
13:40
7,95
8.89
10.09
5.00
16.73
12:57
20.1 15.51
22,97
15.09
18.98
15:36 13.64
L.M-BP
72.59 71.10 69.51 66.29
75.55
75.32
59.86
22.66
24.81
22.66
61.92
57.51
65.53
63.28
80
$1.66
65,41
77.75
63.70
73.14
57.33
2.27 2:55
M.M-BP (uppe)
71.41 70.11 68.66 68.66 65.62
76.81
76.81
(9.44
23.02.
29.40 28 45
61.51
57.09
67.96
64.27
$4,92
74.19
79.39 64.63 75.65 62,55
70.04
55.53
2:45 2.27
Table 2: Zero-Shot End-to-End Evaluation. 'NA' refers to neighborhood embedding aggregation.
History
Pubmed
History
Pubmed
History
Pubmed
History
Pubmed
Children
Children
Children
Sportsfit
Sportsfi
Sportsfte
Sports
Cora
Corn
Come
Cora
Wikica
Wikica
Wikica
Wikica
Washington
Washington
Washington
Washington
Cornell
Cornell
Texas
Wisconsin
Texas
Wisconsin
Texas
Wisconsin
Toxas
Wisconsin
SBert.
Text- Eew.-edmmedddnnn... Large.
Vec.
Class-Condiee Conditional Encoding (Ours).
Figure 6: Experiments on graph information aggregation. 'Raw' refers no graph structure usage, "w/ NA' refers to the neighborhood embedding aggregation (NA) proposed in (Yang et al., 2024), 'w/ BP refers to the belief propagation following Eq. 6, 'w/ BP (appr.)' refers to its simplified linear form that follows Eq. 7.
also surpass the NA baseline, particularly on heteophilic graphs, where direct neighborhood embedding aggregation negatively affects performance. These results highlight the generalizability of our data modeling approach and the ef- fectiveness of the key-parameter estimation design in BP.
ing that fine-tuned LM encoders may suffer performance degradation out-of-domain TAGs. Similarly, graph-SSL methods (DGI (Veličković et al., 2018), GraphMAE (Hou et al., 2022)) show limited generalization across structural shifts.
Among multi-task graph foundation models, GOFA achieves strong performance, likely benefiting from a larger tre-train corpus for graph-text alignment (Hu et al., 2021; Ding et al., 2023) compared to GraphGPT (Tang et al., 2024a) and LLaGA (Chen et al., 2024b), which are trained solely on ogbn-arxiv. However, GOFA still requires broader pre-training and instruction fine-tuning to improve general- ization under text domain shifts, and its reliance on GNNs may limit effectiveness on heterophilic data.
4.3. End-to-End Evaluation
Exp.S: Main Results in the Zero-Shot Setting The main experimental results are presented in Table 2. Among the basclines, vanilla encoders and LLMs demonstrate strong zero-shot generalization. GPT-3.5-Turbo (Achiam al., 2023) ranks first on the Sportsfit dataset, while GPT- 4o (Hurst et al., 2024) achieves the best performance Pubmed and Children.
UniGLM (Fang et al., 2024) and ZeroG (Li et al., 2024e) per- form well in domains aligned with their pre-training, such as citation networks (e.g.. ZeroG enhances SBert's perfor- mance on Cora, Pubmed, and Wikics). However, both strug- gle on TAGs with unseen text distributions (e.g., Sportsfit) or novel graph structures (e.g., webpage networks), suggest-
Notably, LLM-BP and LLM-BP (appr.) achieve the highest average ranking across all datasets on both homophilic and heterophilic graphs. For fine-grained average ranking that distinguish between homophilic and heterophilic graphs, refer to Appendix. D.2. Another interesting observation is that when we randomly sample 20c nodes to obtain the class
8

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
embeddings with the help of LLMs following Algorithm. the zero-shot performance of the encoders in this setting is comparable to their performance between 5-10-shot setting as shown in Table. 10 in the Appendix. Further comparisons with LLM-GNN (Chen et al., 2024e) and TEA-GLM (Wang et al., 2024) are provided in Appendix D.5.
References
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L.,, Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
Exp.6: Main Results under Few-shot Setting We con- 5, 10-shot settings. Using
BehnamGhader, P., Adlakha, V., Mosbach, M., Bahdanau, D., Chapados, N., and Reddy, S. LIm2vec: Large lan- guage models are secretly powerful text encoders. arXiv preprint arXiv:240..05961, 2024.
duct the evaluation in & 10 different random seeds, sample the shots from the training set and repeat the experiments 10 times. The ex- perimental results are presented in Table 10 in Appendix D. Across all k-shot settings, LLM-BP and LLM-BP (appr.) outperform the baseline models.
Bi, S., Li, C., Han, X., Liu, Z., Xie, X., Huang, H., and Wen, Z. Leveraging bidding graphs for advertiser-aweer aware relevance modeling in sponsored search. In Findings of the Association for Computational Linguistics: EMNLP 2021, pp. 2215-2224, 2021.
5. Discussion and Limitations
Graph learning tasks often face substantial data constraints compared to other domains, underscoring the importance of establishing fundamental principles that foster model gen- cralization. Our approach exemplifies this by leveraging LLMs to analyze graph data and determine suitable infer- ence strategies, particularly via homophily estimation for belief propagation. While LLM-BP achieves notable suc- cess TAGs for node classification and extends partially to link prediction, it remains step away from fully com- prehensive graph foundation model that addresses a wider range of graph learning tasks. Nonetheless, the core idea of leveraging LLM-driven graph analysis to guide algorithmic decisions aligned with task- specifcc inductive biases holds broad potential for future applications.
Bobadilla, J., Ortega, F., Hemando, A., and Gutiérrez, A. Recommender systems survey. Knowledge-basee sys- tems, 16:109-132, 2013.
Cai, H., Zheng, V. W., and Chang, K. C.-C. Active learning for graph embedding, arXiv preprint 2017.
Cao, Y., Han, S., Gao, Z.,, Ding, Z., Xie, X., and Zhou, S. K. Graphinsight: Unlocking insights in large language models for graph structure understanding. arXiv preprint arXiv:2409.0322 03258, 2024.
Chen, B., Zhang, Z., Langrené, N., and Zhu, S. Unleash- ing the potential of prompt engineering in large lan- guage models: a comprehensive review. arXiv preprint arXiv:2310. 14735, 2023.
Acknowledgements
H. Wang, S. Liu, R. Wei and P. Li are partially supported by NSF awards IIS 2239523,,,, CCF-2402816, I12-2428777, PHY-21 17997; DOE award DE-FOA-0002785 JPMC fac- ulty awards; Openai Research Credits; and Meta research award.
Chen, N., Li, Y., Tang, J., and Li, J. Graphwiz: An cnstructionfolllovinn language model for graph com- putational problems. Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 353-353---- 364, 2024a.
We extend our sincere gratitude to Hongbin Pei, Zhen Wang, and Jingcheng Cen for their valuable assistance in identify- ing the raw node text of the heterophilic graphs used in this study.
Chen, R., Zhao, T., Jaiswal, A., Shah, N., and Wang, Z. Llaga: Large language and graph assistant. arXiv preprint arXiv:2402.08) 70, 2024b.
Chen, Z., Mao, H., Li, H., Jin, W., Wen, H., Wei, X., Wang, S., Yin, D., Fan, W., Liu, H., et al. Exploring the po- tential of large language models (Ims) in learning on graphs. ACM SIGKDD Explorations Newsletter, 25(2): 42 22-61, 2024c.
Impact Statement
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, Z., Mao, H., Liu, J., Song, Y., Li, B., Jin, W., Fatemi, B., Tsitsulin, A., Perozzi, B., Liu, H., et al. Text-space graph foundation models: Comprehensive benchmarks and new insights. arXiv preprint arXiv:2406.10727, 2024d.
9

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
Chen, Z., Mao, H., Wen, H., Han, H., Jin, W., Zhang, H., Liu, H., and Tang, J. Label-free node classification graphs with large language models (Ilms). ICLR, 2024e.
for enhanced text-attributed graph representation learning. ICLR, 2024.
He, Y. and Hooi, B. Unigraph: Learning a cross-domain graph foundation model from natural language. arXiv preprint arXiv:2402.13622 2024.
Chien, E., Chang, W.- Hsich, C.-J., Yu, H.-F., Zhang, J., Milenkovic, O., and Dhillon, S. Node feature extraction by self-supervised multi-scale neighborhood prediction. ICLR, 2022.
Hou, Z.., Liu, X., Cen, Y., Dong, Y., Yang, H., Wang, C., and Tang, J. Graphmae: Self-supervised masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 594-5544 2022.
Craven, M., DiPasquo, D., Freitag, D., McCallum, A., Mitchell, T., Nigam, K., and Slattery, S. Learning to extract symbolic knowledge from the world wide web. AAAI/AAА, 3(3.6):2, 1998.
Hou, Z., Li, H., Cen, Y., Tang, J., and Dong, Y. Graphalign: Pretraining one graph neural network on multiple graphs via feature alignment. arXiv preprint arXiv:2406.0299) 2024.
Dai, X., Qu, H., Shen, Y., Zhang, B., Wen, Q., Fan, W., Li, D., Tang, J., and Shan, C. How do large language models understand graph patterns? a benchmark for graph pattern comprehension. arXiv preprint arX:v:2410.05228, 2024.
Hu, L.. Xie, H., Yu, L., Huang, T., Li, L., Li, M., ZHOU, J., and Wang, D. Low-cost enhancer for text attributed graph learning via graph alignment. 2024.
Ding, N., Chen, Y., Xu, B., Qin, Y., Zheng, Z., Hu, S., Liu, Z., Sun, M., and Zhou, B. Enhancing chat language mod- els by scaling high-quality instructional conversations. arXiv preprint ar arXiv:2305.142:3 14233, 2023.
Hu, W., Fey, M., Zitik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 33:22118 18-22133, 2020.
Duan, K., Liu, Q., Chua, T.-.., Yan, S., Ooi, W. T., Xie,
Q. and He, J. Simteg: A frustratingly simple ap- proach improves textual graph learning, arXiv preprint arXiv:2308.00 026605, 2023.
Fan, W., Wang. S., Huang, J., Chen, Z., Song, Y., Tang, W., Mao, H., Liu, H., Liu, X., Yin, D., et al. Graph machine learning in the of large language models (Ilms), arXiv preprint arXiv:2404.1 1...404.1492 14928, 2024.
Hu, W., Fey, M., Ren, H., Nakata, M., Dong, Y., and Leskovec, J. Ogb-Isc: A large-scale challenge for machine learning on graphs. arXiv preprint :XXi:21133004400 2021.
Fang. Y., Fan, D., Ding. S., Liu, N., and Tan, Q. Uniglm: Training one unified language model for text-attributed graphs. arXiv preprint arXiv:2406. /2052, 2024.
Huang, J. and Chang, K. C.-C. Towards reasoning in large language models: survey. arXiv preprint arXiv:2212. 2022.
Feng, J., Liu, H., Kong, I.., Zhu, M., Chen, Y., and Zhang, M. Taglas: An atlas of text-bttributed graph datasets in the era of large graph and language models. arXiv preprint arXiv:2406.1445 14683, 2024.
Huang, X., Han, K., Yang, Y., Bao, D., Tao, Q., Chai, Z., and Zhu, Q. Can gnn be good adapter for Ilms? In Proceedings of the ACM on Web Conference 2024, pp. 893-904, 2024.
Fey, M. and Lenssen, J. E. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 1903.0248, 2019.
Hurst, A., Lerer, A., Goucher, A. P., Perelman, A., Ramesh, A., Clark, A., Ostrow, A., Welihinda, A., Hayes, A., Radford, A., et al. Gpt-4o system card. arXiv preprint urXi::2410.212777 2024.
Giles, C. L., Bollacker, K. D., and Lawrence, S. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pp. 89-98, 1998.
Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., Casas, D. d. I., Bressand, F., Lengyel, G., Lample, G., Saulnier, L., et al. Mistral 7b, arXiv preprint arXiv: arXiv:2310.06825, 2023.
Hamilton, W., Ying, Z., and Leskovec, J. Inductive repre- sentation learning large graphs. Advances in neural information processing systems, 30, 2017.
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint arXiv:2001 08361, 2020.
He, X., Bresson, X., Laurent, T., Perold, A., LeCun, Y., and Hooi, B. Harnessing explanations: Lim-to-in Im interpreter
10

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
Kenton, J. D. M.-W. C. and Toutanova, L. K. Bert: Pre- training of deep bidirectional transformers for language understanding. In Proceedings of naacL-HHLT, volume 1. Minneapolis, Minnesota, 2019.
Li, Y., Wang, P., Zhu, X., Chen, A., Jiang, H., Cai, D., Chan, V. W. K., and Li, Glbench: A comprehensive benchmark for graph with large language models. arXiv preprint arXiv:240..07457 2024F
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv: (ew9:6609.000 1ew..6699900,,... 2016.
Li, Z.., Zhang, X., Zhang, Y., Long, D., Xie, P., and Zhang, M. Towards general text embeddings with multi-stan contrastive learning. arXiv preprint arXiv:2308. 03281, 2023.
Koller, D. Probabilistic graphical models: Principles and techniques, 2009.
Li, Z., Gou, Z., Zhang, X., Liu, Z., Li, S., Hu, Y., Ling, C., Zhang, Z., and Zhao, L. Teg-db: A comprehensive dataset and benchmark of textual-edge graphs arXiv preprint arXiv:2406. 10310, 2024g.
Kong, L., Feng, J., Liu, H., Huang, C., Huang, J., Chen, Y., and Zhang, M. Gofa: A generative one-for-all model for joint graph language modeling. arXiv preprint NXiv:2407.09709, 2024.
Liu, H., Feng, J., Kong, L., Liang, N., Tao, D., Chen, Y., and Zhang, M. One for all: Towards training one graph model for all classification tasks. arXiv preprint arXiv:23000000 2023a.
Kumar, S., Spezzano, F., Subrahmanian, V., and Faloutsos, C. Edge weight prediction in weighted signed networks. In Data Mining (ICDM), 2016 IEEE 16th International Conference on, pp. 221-230 IEFE, 2016.
Liu, J., Yang, C., Lu, Z., Chen, J., Li, Y., Zhang, M., Bai, T., Fang. Y.. Sun, L., Yu, P. S., et al. Towards graph foundation models: A survey and beyond. arXiv preprint arXiv:2310.11822 2023b.
Kumar, S., Hooi, B., Makhija, D., Kumar, M., Faloutsos, C., and Subrahmanian, V. Rev2: Fraudulent user predic- tion in rating platforms. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 333-341. ACM, 2018.
Liu, J., Mao, H., Chen, Z., Fan, W., Ju, M., Zhao, T., Shah, N., and Tang. J. One model for one graph: A new per- spective for pretraining with cross-domain graphs. arXiv preprint arXiv:2412.00311 2024.
Li, C., Pang, B., Liu, Y., Sun, H., Liu, Z., Xie. X., Yang, T., Cui, Y., Zhang, L., and Zhang, Q. Adsgnn: Behavior- graph augmented relevance modeling in sponsored search. In Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval, pp. 223 202,232,222 2021.
Liu, Y. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 364, 2019.
Liu, Y., Jin, M., Pan, S., Zhou, C., Zheng, Y., Xia, F., and Philip. S. Y. Graph self-super learning: A survey, IEEE transactions on knowledge and data engineering, 35(6):5879 5900, 2022.
Li, C., Qin, M., Xiao, S., Chen, J., Luo, K., Shao, Y., Lian, D., and Liu, Z. Making text embedders few-shot learners. arXiv preprint arXiv:2409.1 15700, 2024a.
Li, H., Freitas, M. M. d., Lee, H., and Vasarhelyi, M. En- hancing continuous auditing with large language mod- els: Ai-assisted real- real-time accounting information cross- verification. Available SSRN 4692960, 2024b.
Liu, Z., Lin, Y., Cao, Y., Hu, H., Wei, Y., Zhang, Z., Lin, S., and Guo, B. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF international conference computer vision, pp. 10012-10022 2021.
Li Q. Zhao, T., Chen, L., Xu, J., and Wang, S. Enhancing graph neural networks with limited labeled data by ac- tively distilling knowledge from large language models. arXiv preprint arXiv:2407. 33989, 2024c.
Liu, Z., Yo, X., Fang, Y., and Zhang, X. Graphprompt: Uni- fying pre-training and downstream tasks for graph neural networks. In Proceedings of the ACM Web Conference 2023, pp. 417-428, 2023c.
Li, R., Li, J., Han, J., and Wang, G. Similarity-based neighbor selection for graph llms. arXiv preprint MXXv:2402.033200. 2024d.
Luo, H., Meng. X., Wang. S., Zhao, T., Wang, F., Cao, H., and Zhang, Y. Enhance graph alignment for large lan- guage models. arXiv preprint arXiv:2410. 11370, 2024.
Li, Y., Wang, P., Li, Z., Yu, X., and Li, J. Zerog: Inves- tigating cross-dataset zero-shot transferability in graphs. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1725-1735, 2024e.
Ma, J., Ma, Z., Chai, J., and Mei, Q. Partition- based ac- tive learning for graph neural networks. arXiv preprint arXiv:2201.0939/ 2022.

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
Mao, H., Chen, Z., Tang, W., Zhao, J., Ma, Y., Zhao, T., Shah, N., Galkin, M., and Tang. J. Graph foundation models. arXiv preprint arXiv:2402.02216. 2024.
Perozzi, B., Fatemi, B., Zelle, D., Tsitsulin, A., Kazemi, M., AI-Rfou, R., and Halerow, J. Let your graph do the talking: Encoding structured data for Ilms, arXiv preprint arXiv:2402.05862, 2024.
McCallum, K., Nigam, K., Rennie, J., and Seymore, K. Automating the construction of internet portals with ma- chine learning. Information Retrieval, 3:127-163, 2000.
Qin, Y., Wang. X., Zhang, Z., and Zhu, W. Disentangled representation learning with large language models for text-attributed graphs. arXiv preprint ux1v:2310.18112. 2023.
Mernyei, and Cangea, C. Wiki-cs: wikipedia-basee benchmark for graph neural networks. arXiv preprint AxXiv:2007002001, 2020.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pp. 8748-8763. PMLR, 2021.
Moreira, G. d. S. P., Osmulski, R., Xu, M., Ak, R., Schif- ferer, B., and Oldridge, E. Ny-retriever: Improving text embedding models with effective hard-negative mining. arXiv preprint arXiv:2407.1588
2024.
Reimers, N. Sentence-bert: Sentence embeddings using siamese bert-networks. arXiv preprint arXiv:1908. 10084, 2019.
Muennighoff, N., Tazi, N., Magne, L., and Reimers, N. Mteb: Massive text embedding benchmark. arXiv preprint arXiv:2210.07316, 2022.
Sahoo, P., Singh, A. K., Saha, S., Jain, V., Mondal, S., and Chadha, A. A systematic survey of prompt engineering in large language models: Techniques and applications. arXiv preprint arXiv:2402.077: 2024.
Murphy, K. Weiss, Y., and Jordan, M. I. Loopy belief propagation for approximate inference: An empirical study. arXiv preprint arXiv: 301.6725, 2013.
Ni, J., J., and McAuley, J. Justifying recommendations using distantly-labeled reviews and fine-grained aspects. In Proceedings of the 2019 conference on empirical meth- ods in natural language processing and the 9th interna- tional joint conference on natural language processing (EMNLP-IJCNLP), pp. 188-
Schuhmann, C., Beaumont, R., Vencu, R., Gordon, C., Wightman, R., Cherti, M., Coombes, T., Katta, A., Mullis, C., Wortsman, M., et al. Laion-5b: An open large-scale dataset for training next generation image-text models. Advances in Neural Information Processing Systems, 35: 25278-25294, 2022.
OpenAI. Gpt text-embedding---large 2024. URL ht //tptt::///tttt////p openai. com/ docs/ /embeedd ngs.
Sen, P., Namata, G., Bilgic, M., Getoor, L.,, Galligher, B., and Eliassi-Ras Rad, T. Collective classification in network data. Al magazine, 19(3):93-93, 2008.
Ouyang, S., Hu, Y., Chen, G., and Liu, Y. Gundam: Align- ing large language models with graph understanding. arXiv preprint arXiv:2409.2005: 2024.
SHAPIRO, S. and WILK, M. B. analysis of variance test for normality (complete samples). Biometrika, 52(3- 4):591-611, dec 1965. doi: 10. 10.1093/biioeet552..455553 10. http://1.111200 10w./1199/bbeee
URL https: / 3-4.597
Pan, B., Zhang, Z., Zhang, Y. Hu, Y., and Zhao, L. Distilling large language models for text-attributed graph learning. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pp. 1836- 1845, 2024.
Shazeer, N., Mirhoseini, A., Maziarz, K., Davis. A., Le, Q., Hinton, G., and Dean, J. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. arXiv preprint 1711:0170,.0638,, 2017.
Pang, B., Li, C., Liu, Y., Lian, J., Zhao, J., Sun, H., Deng. W., Xie, X., and Zhang, Q. Improving relevance modeling via heterogeneous behavior graph learning in bing ads. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3713-3721, 2022.
Song, K., Tan, X., Qin, T., Lu, J., and Liu, T.-Y. Mpnet: Masked and permuted pre-training for language under- standing. Advances in neural information processing systems, 33:1 33:16857-16867, 2020.
Student. The probable error of mean. Biometrika, pp- 1-25, 1908
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Tang, J., Yang, Y., Wei, W., Shi, L., Su, L., Cheng, S., Yin, D., and Huang, C. Graphgpt: Graph instruction tuning for large language models. In Proceedings of the
12

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 491-500, 2024a.
Xia, L. and Huang, C. Anygraph: Graph foundation model in the wild. 2024.
Yan, H., Li, C., Long, R., Yan, C.,, Zhao, J., Zhuang, W., Yin, J., Zhang, P., Han, W., Sun, H., et al. A comprehen- sive study text-attributed graphs: Benchmarking and rethinking. Advances in Neural Information Processing Systems, 36: 0ss17238-17264 2023.
Tang, J.. Zhang, Q., Li, Y., and J. Grapharena: Bench- marking large language models on graph computational problems, arXiv preprint arXiv:2407.00379, 2024b.
Tibshirani, R. J. and Efron, B. An introduction to the boot- strap. Monographs on statistics and applied probability, 17(1),1-436, 1993.
Yang, H., Wang, X., Tao, Q. Hu, S., Lin, Z., and Zhang, M. Gl-fusion: Rethinking the combination of graph neu- ral network and large language model. arXiv preprint arXiv:2412.06844 2024.
Van der Maaten, L. and Hinton, G. Visualizing data using t-sne. Journal of machine learning research, 911), 2008.
Yang, J., Liu, Z., Xiao, S., Li, C.,, Lian, D., Agrawal, S., Singh, A., Sun, G., and Xie, X. Graphformers: Gnn- nested transformers for representation learning textual graph. Advances in Neural Information Processing Sys- tems, 34:28798 2881288811 2021.
Veličković, P.. Cucurull, G., Casanova, A., Romero, A.,
Lio, P., and Bengio. Y. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Veličković, P., Fedus, W., Hamilton, W. L., Liò, P., Bengio, Y., and Hjelm, R. D. Deep graph infomax. arXiv preprint 1eXiv 2018.
Yu, J., Ren, Y., Gong, C., Tan, J., Li, X., and Zhang, X. Em- power text-attributed graphs learning with large language models (Ilms). arXiv preprint TrXiv:2310.09877 2023.
Virtanen, P.. Gommers, R., Oliphant, T. E.,, Haberland, M.,
Reddy, T., Cournapeau, D., Burovski, E., Peterson, P.,
Yuan, Z., Liu, M., Wang, H.,, and Qin, B. Gracore: Bench- marking graph comprehension and complex reasoning in large language models. arXiv preprint arXiv:2407.02936, 2024.
Weckesser, W., Bright, J., van der Walt, S. J., Brett, M., Wilson, J., Millman, K. J., Mayorov, N., Nelson, A. R. J., Jones, E., Kern, R., Larson, E., Carey, C. J., Polat, I., Feng. Y., Moore, E. W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E. A., Harris, C. R., Archibald, A. M., Ribeiro, A. H., Pedregosa, F. van Mulbregt, P., and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 10.
Zhai, X., Mustafa, B., Kolesnikov, A., and Beyer, L. Sig- moid loss for language image pre-training. In Proceed- ings of the IEEE/CVF International Conference on Com- puter Vision, pp. 11975-11986, 2023.
Zhang, M., Sun, M., Wang, P., Fan, S., Mo, Y., Xu, X., Liu, H., Yang, C., and Shi, C. Graphtranslator: Aligning graph model to large language model for open-ended tasks. In Proceedings of the ACM on Web Conference 2024, pp. 1003-1014, 2024a.
Wang, D., Zuo, Y., Li, F., and Wu, J. Lims zero-shot graph learners: Alignment of gnn representations with I1m token embeddings. arXiv preprini arXiv:2408. 14512, 2024.
Zhang, T., Yang, R., Yan, M., Ye, X., Fan, D., and Lai, Y. Cost-effective label-free node classification with Ilms. arXiv preprint arXiv:2412.1 1983, 2024b.
Wei, R., Yin, H., Jia, J., Benson, A. R., and Li, P. Un- derstanding non-linearity in graph neural networks from the Dnyesian-inference perspective. Advances in Neural Information Processing Systems, 35:34024-34038, 2022.
Zhang, W., Wang, Y., You, Z., Cao, M., Huang, P., Shan, J., Yang, Z.,, and Cui, B. Rim: Reliable influence-bart based ac- tive learning on graphs. Advances in Neural Information Processing Systems, 34:27978 27990, 2021.
Wei, Y., Fu, S., Jiang, W., Zhang, Z., Zeng, Z., Wu, Q., Kwok, J., and Zhang, Y. Gita: Graph to visual and textual integration for vision- vision-language graph reasoning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Zhang, Y., Wang, H., Feng, S., Tan, Z., Han, X., He, T., and Tsvetkov, Y. Can Ilm graph reasoning generalize beyond pattern memorization? arXiv preprint arXiv:2406. 15992, 2024c.
Wilcoxon, F. Individual comparisons by ranking methods. In Breakthroughs in statistics: Methodology and distribu- tion, pp. 196-202. Springer, 1992.
Zhao, H., Liu, S., Chang, M., Xu, H., Fu, J., Deng, Z., Kong, L., and Liu, Q. Gimlet: A unified graph-text model for instruction-baser molecule zero-shot learning. Advances in Neural Information Processing Systems, 36: 5850-5887, 2023a.
Wolf, T. Huggingface's transformers: State-of-the- art natural language processing. arXiv preprint arXiv: 1xXiv:191000377.. 2019.
13

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
Zhao, H., Chen, A., Sun, X., Cheng, H., and Li, All in one and one for all: A simple yet effective method towards cross-domain graph pretraining. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4443-4454, 2024.
Zhao, J., Qu, M., Li, C.,, Yan, H., Liu, Q. Li, R., Xie, X., and Tang, J. Learning on large-scale text-attributed graphs via variational inference. ICLR, 2023b.
Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020.
Zhu, J.. Cui, Y., Liu, Y., Sun, H., Li, X., Pelger, M., Yang, T., Zhang, L., Zhang, R., and Zhao, H. Textgnn: Improving text encoder via graph neural network in sponsored search. In Proceedings of the Web Conference 2021, pp. 2848- 2857, 2021.
Zhu, X., Ghahramani, Z., and Lafferty, J. D. Semi- supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International con- ference on Machine learning (ICML-03), pp. 912-919, 2003.
Zhu, Y., Shi, H., Wang. X., Liu, Y., Wang, Y., Peng, B., Hong. C., and Tang, S. Graphelip: Enhancing trans- ferability graph foundation models for text-attributed graphs. arXiv preprint arXiv:2410. 10329, 2024.
Zolnai-Lucas, A., Boylan, J., Hokamp, C., and Ghaffari, P. Stage: Simplified text-attributed graph embeddings using pre-trained lms. arXiv preprint 2407 12800 2024.
14

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
A. More Related Works
LLMs for Data Augmentation annotate pseudo-labels via their advanced zero-shot text classification performance. E.g. LLM-GNN (Chen et al., 2024e). Cella (Zhang et al., 2024b) and (Hu al., 2024) propose heuristics to actively select and annotate pseudo-labels for supervised GNN training. (Pan al., 2024) performs knowledge distillation with LLMs as teachers. (Yu et al., 2023; Li et al., 2024c) generate synthetic node text with LLMs. The performance of these methods depend on the capability of LLM, and may still require relatively high annotating and training cost.
LLMs for Graph Property Reasoning focus on reason graph structure properties (e.g., shortest path, node degree, etc) (Tang et al., 2024b; Dai et al., 2024; Yuan et al., 2024; Ouyang et al., 2024). Representative works include (Perozzi al., 2024; Chen et al., 2024a; Zhang et al., 2024c; Cao et al., 2024; Wei et al., 2024).
Tuning LMs/GNNs towards Better Task-Specific Performance aims push the limits of task-specific performance on TAGs other than generalization. These methods develop novel techniques optimize LMs GNNs for pushing the limits of in-domain performance (Chien al., 2022; Duan et al., 2023; He et al., 2024; Zhao al., 2023b; Zhu al., 2021: Li et al., 2021; Yang et al., 2021; Bi et al., 2021; Pang et al., 2022; Zolnai-Lucas et al., 2024; Yang et al., 2021).
Text embeddings Generating unified text embeddings is a critical research area with broad applications, including web search, accounting documents (Li et al., 2024b) and question answering. Numerous text encoders (Reimers, 2019; Liu, 2019; Song et al., 2020) based on pre-trained language models have served as the foundation for various embedding models. Recently, decoder-only LLMs have been widely adopted for text embedding tasks (Li al., 2023; Moreira et al., 2024) achieving remarkable performance the Massive Text Embedding Benchmark (MTEB) (Muennighoff et al., 2022). This progress stems from LLM2Vec (BehnamGhader et al., 2024), which introduces a novel unsupervised approach to transforming decoder-only LLMs into embedding models, including modifications to enable bidirectional attention. Recent findings (Li et al., 2024a) suggest that retaining the unidirectional attention mechanism enhances L.M2Vec's empirical performance.
B. Experiment Details
B.1. Dataset Details
Meta-Data In Table. 3, show the meta-data of all the eleven datasets used in experiments.
Number of Nodes
Number of Edges
Number of Classes
Ground Truth Homophily Ratio
Cora
2708
10556
0.809
Citeseer
3186
8450
0.764
Pubmed
19717
88648
3
0.792
History
41551
503180
12
0.662
Children
76875
2325044
24
0.464
Sportsfit
173055
3020134
13
0.9
Wikics
11701
431726
0.678
Cornell
191
292
0.115
Texas
187
310
0.067
Wisconsin 265
510
0.152
Washington
229
394
5
0.149
Table 3: Meta data of the datasets in this study.
Dataset Split For the datasets (all the homophily graphs) that have been used for study in TSGFM (Chen et al., 2024d), we follow their implementation to perform data pre- pre-procss,,ng, obtain raw texts and do data split, the introduction to data source can found at Appendix. D.2 2 their original paper, the code can be found at the link
As to the heterophily graphs, the four datasets are originally from (Craven al., 1998). We obtain the raw texts from (Yan
'https://gt thub. com htttss//ttttt.oooo/////e//////es
15

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
al., 2023), which be found from². As to data split, for zero-shot inference, all the nodes marked test data; for few-shot setting, k labeled nodes are randomly sampled per class and the rests marked as test data. To the best of our knowledge, the four heterophily graph datasets used in this study are the only graphs that provide raw texts feature.
B.2. LLM-BP Implementation Details
server with AMD EPYC 7763 64-Core Processor and eight NVIDIA RTX 6000 Ada GPU cards, methods mainly implemented with PyTorch (Paszke et al., 2019), Torch- Geometric (Fey & Lenssen, 2019) and Huggingface Transformers (Wolf, 2019). To obtain the embeddings, all the encoders that run locally on the server without API calling in this study run with the random seed 42.
Infrastructure and Seeds All the local experiments
Class Embedding
Zero-Shot Setting: We uniformly randomly sample 20c nodes per graph, where e denotes the number of classes, we employ GPT-4o (Hurst et al., 2024) to infer their labels. With the predictions from L.MSs, the sampled nodes form distinct clusters. For each cluster, we take the top-k (10 in the experiments) nodes whose embedding are closest with the cluster center and calculate their average embedding as the class embedding.
We notice that some works directly feed text descriptions into encoders as class embeddings (Yang et al., 2024; Chen et al., 2024d), we find that different encoders can be highly sensitive to variations text description. Therefore, we adopt the above method to ensure fairness among different encoders.
Few-Shot Setting: We directly take the class embedding the averaged embeddings of labeled nodes per class.
The Task-Adaptive Encoder: We directly adopt the pre-trained LLM2Vec encoder released by (Li et al., 2024a), which is based on Mistral7B-vO.1 (Jiang et al., 2023). We check the pre-training data used in the original paper for aligning LLM decoders with the embedding space, the datasets are mainly for text-retrieval and therefore do not overlap with the TAG datasets adopted in our study. For detailed introduction of the datasets for LLM2Vec pre-training, see Section 4. training data in the original paper. The task adaptive prompting follows the format as:
Instruct)
Given the {task description). classify it into one of the following i classes:
{class labels)
{ query)
(raw node texts)." response) )
where the (task ]escriptions} prompts for each dataset is the same as that used for vanilla LLMs, see Table. 13 for details.
Hyper-PPate mer-Parameters for BP algorithm For LLM-BP, adopt 5 message-passin pasggng layers, for its linear approximation form, 7 in computing node potential initialization in Eq. (5) is set as 0.025 for LLM-BP and 0.01 for LLM-BP (appr.) across all the datasets. Attached in Table. 4 is the homophily ratio r we used (predicted by GPT-4o-mini (Hurst et al., 2024).
we use single layer. The temperature
Cora
Citeseer
Pubmed
History
Children
Sportsfit
Wikies
Corell
Texas
Wisconsin
Washington
Ground Truth
0.81
0.76
0.79
0.66
0.46
0.90
0.67
0.11
0.06
0.15
0.19
Homophony Ratio
predicted by
0.70
0.81
0.81
0.73
0.35
0.81
0.52
0.05
0.04
0.06
0.02
GPT-4o-mini
Table 4; predicted by GPT-4o-mini, that is used in all the experiments in this study.
16

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
B.3. Baseline Implementation Details
Vanilla Encoders Vanilla encoders like SBert (Reimers, 2019), Roberta (Liu, 2019) and text-embedding-3-Ee (OpenAI, 2024) directly encode the text of the nodes. Vec the prompts:
(Instruct) (ask_ ceascrrptionn((ueeyey (response). (repoo))
(8)
where the ftask description} for each dataset is provided in Appendix. E.1.
Vanilla LLMs Prompts for GPT-4o and GPT-3.5-turbo adopts the format as follows:
"role": "system"
"content"; "You are chatbot who is an expert text classification"
"role": "user"
"content": "We have (task description) from the following categories: fclass labels)
The text is follows:
fraw node text)
Please tell which category the text belongs to:"
The (task description) for the vanilla LLMs for each class provided in Appendix. E.2.
Tuning LM/GNNS We adopt the pre-trained UniGLM (Fang et al., 2024) released by the official implementation, which adopts Bert the encoder, for direct inference. For ZeroG (Li al., 2024e), we re-implement the method and train it on ogbn-arxiv (Hu et al., 2020) for fair comparison with other baselines.
As to GNNs tuning methods, we pre-train GraphMAE (Hou et al., 2022) and DGI (Veličković et al., 2018) on ogbn-arxiv (Hu et al., 2020), where the input for both models are from SBert (Reimers, 2019), and we follow in implementation in TSGFM (Chen et al., 2024d) benchmark.
Multi-Task GFMs OFA (Liu al., 2023a) is trained on ogbn-arxiv (Hu al., 2020). As GOFA, directly adopt the model after pre-training (Hu al., 2021; Ding al., 2023) and instruct fine-tuning ogbn-arxiv (Hu al., 2020) provided by the authors due to the huge pre-training cost, the zero-shot inference scheme also follows their original implementation.
LLMs with Graph Adapters Both LLaGA (Chen et al., 2024b) and GraphGPT (Tang et al., 2024a) are trained on oghn-arxiv (Hu et al., 2020), we follow the hyper-parameter setting in their original implementation.
C. Detailed Derivations
C.1. Derivation for Eq. (4)
In node classification task, given a node our goal is minimize the mean-square enror (MSE) in predicting the node label under the observations X:
min MSE().) E [v: - 21)²
x
(9)
The optimal solution 9: is then given by:
0 = Σ yo p(us x).
(10)
where the posterior marginal p(u: x) is computed as:
P(y: x) Σ
P(Y |X).
(11)
YV
Factorized Posterior under an MRF distribution factors as:
Assuming a Markov Random Field (MRF) over a graph G (V,E), the posterior
PY X) x II (x.))
II
Mhyy (15(,.,U)). Uz),
(12)
KEV
(K))S
where the node potential is defined as xxx (v:) = Po. (X,) (s6)
17

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
General Message-Passingg Framework. To compute the marginal p(y X), the loopy belief propagation (LBP) algorithm iteratively updates messages between nodes. The general message update rule from node to node iteration
is:
(4) m 1 (us)
pxx; (1s) (Ui, Ms)
II
(k-1) mi-i (v:)
(13)
(EN())
where 04z+j normalization constant ensuring the message sums to
Node Belief Updates. The node belief p. (yi) at iteration & is obtained by combining the node potential with incoming messages from all neighbors:
Pi (ys) xx, (vt)
II
(k) m mi-i (vs).
(14)
(EN())
Reformulating the Messages. Substituting Eq. (14) into Eq. (13) simplifies the message-passing equation. The message from node! node iteration & can be rewritten as:
(yE)
2 (15) O3++
Evis (1r Uz)
(15)
m (y:)
(k-1)
This reformulation prevents double-counting the contribution of node to node i in the previous iteration.
Log-Space Stability.
To avoid numerical underflow, the log-space version of the message update is commonly used:
log m m (Us) = LSE log this (y:. v;) + log P. (4) (ys) logm (K-1) (us)
(16)
where I.S((-) log Σ exp(-).
Summary. By iteratively applying these message updates and node belief calculations, LBP provides an approximation for the posterior marginal p(y: X). The final prediction Ú; under the MMSE criterion is:
js = Σ
P (J:).
(17)
This completes the derivation of the message-passing update in Eq. (4).
D. More Experiment Results
D.I. Significance Test of Effectiveness of Task-Adaptive Encoding
Cora
Citeseer
Pabmed
History
Children
Sportsfit
Wikics
Comell
Texas
Wisconsin
Washington
90% CI
Tasp-Ade Encoding
0.7% 1.3%
-0.2% 1.3%
1.3% 2.3% 3.2% 5.2% 3.3% 3.7% 1.0% 2.6% 1.0%
1.8% 4.0% 4.9%
1.5% 2.7% 0.1% 0.8% -0.2% 0.5%
low, high
vs.
Vanilla L.L22Vcc
value
1c-8
0.38
Ie-10
Ic-9
3e-59
le-4
3e-8
7e-18
5e-8
Ie-3
0.82
90% CI
Task-Adaprive Encoding
low, high
-0.3%
-0.3%
1.0%
6.9% 9, 9.1%
0.7%.
2.0%
4.1%
1.1%
4.7%
0.1% 1.2%
-0.04%
Text. Fast-embedddng.. 3-1 arge
value
6e-27
8e-7
0.51
7e-21
Se-59
1e-9
2e-25
1e-9
0.07
1e-
Table 5: Lower and upper bound of improvement (f) in accuracy of aask-adaetive encoding over baselines with 90% confidence interval, with significance level p (L).
We conduct significance test on the improvment of task-adeetive encoding over vanilla LLm2Vec (Li et al., 2024a) and Text- Embedding-3-Len L-rrge (OpenAI, 2024) under the zero-shot setting, with results shown Table. 5. We replicate experiment for 100 times with random seeds from 42 to 141 and obtain classification accuracy of each method. To check normality, we
18

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
first apply Shapiro-Wilk test (SHAPIRO & WILK, 1965). If the data follows normal distribution, we perform Paired-t test (Student, 1908); otherwise,
Wilcoxon Signed-Rank test (Wilcoxon, 1992), with packages from SciPy (Virtanen al., 2020). The lower and upper bounds under 90% confidence interval are estimated with bootstrap algorithm (Tibshirani & Efron, 1993) to sample 10, 000 times. Task-adaptive encoding show statistically significant improvement over vanilla LLM2Vecc in 9 out 11 dataset and outperforms Text-Embedding-3- LarLe in 8 out of 11 datasets (bolded in the table).
D.2. Fine-Graine Grained Ranking Results
We report the fine-graines ranking results of each method on homophilic and heterophilic graphs. The ranking is shown in Table. 6. Across the three sub-categories of graphs, LLM-BP and its approximation algorithm both achieves the top performance.
Ranking
Homophilic
Heterophilic
Acc
F1
Acc
F1
Shert
8.57
8.00
5.00
5.50
Roberta
7.71
7.57
6.25
6.50
Text-Embbdding----Larg
6.43
5.71
3.50
2.25
Lec2
6.86
6.14
3.50
4.00
SBert + NA
4.57
5,00
8.00
7.75
GPP--35-turbo
4.43
7.86
7.75
8.75
GPT-4o
4.86
6.29
7.75
6.50
UniGLM
11.00
9.43
12.00
10.75
ZeroG
11.29
11.00
14.00
15.75
DGI
15.29
15.71
15.00
15.00
GraphMAE
14.86
15.29
12.25
13.75
OFA
14.29
14.29
15.25
16.25
GOFA
6.71
5.71
10.25
10.50
GraphGPT
14.43
14.86
14.75
14.25
LLAGA
15.86
14.71
14.50
11.75
LLM-BP
2.86
3.14
1.25
1.50
LLM-BP (appr.)
2.86
2.29
1.75
2.25
Table 6: Average ranking in homophilic and homophilic graphs.
D.3, LLM Agents' Prediction on Homophily Ratio r
Ruad aesoreit mesiispion
Beat sisensss Washiggon
GPT-4o.
GPT-4o-mini.
GPT-3.5-turb.
MistsalBB-nnsrucc-00.33
Figure 7: LLM agents' performance predicting the homophily constant
More prediction performance of GPT-4o, GPT-3.5-turbo and Histral/b-Instrucee are shown in Fig. 7.
D.4. Sensitivity Analysis of Sampled Edge Numbers
We conduct sensitivity analysis on homophily ratio r prediction with respect to the number of sampled edges that feeds to LLM. According to Table, 7, the homophily ratio prediction performance is stable across the sampled edge numbers from 40 100.
19

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
Cora
Citeseer
Pubmed
Bookhis
Bookchild
Sportsfit
Wikics
value
gap J
value
gap J
value
gap
value
gap |
value
gap |
value
gap
value
gap
ground truth
0.81
0.76
0.79
0.66
0.46
0.90
0.67
100
0.70
0.11
0.81
0.05
0.81
0.02
0.73
0.07
0.35
0.11
0.81
0.09
0.52
0.15
80
0.70
0.11
0.77
0.01
0.83
0.04
0.75
0.09
0.37
0.09
0.76
0.14
0.55
0.12
40
0.65
0.16
0.77
0.01
0.81
0.02
0.75
0.09
0.33
0.13
0.75
0.15
0.50
0.17
Table 7: Sensitivity test of homophily ratio prediction performance with respect to the number of sampled edges. As shown in the left column, 100, 80 and 40 edges are sampled feed the LLMs to predict homophily ratio r. 'value' refers the predicted r, and "gap' the gap between prediction and ground truth.
D.5. Zero-Shot Comparison with LLM-GNN (Chen et al., 2024e) and TEA-GLM (Wang et al., 2024)
Cora
Citeseer
Pubmed
Wikics
DA-AGE-W
74.96
58.41
65.85
59.13
DA-RIM-W
74.73
60.80
77.94
68.22
DA- DA-GraphPart-V W
68.61
68.82
79.89
67.13
LLM-BP
72.59
69.51
75.55
67.75
LLM-BP (app.)
71.41
68.66
76.81
67.96
Table 8: Accuracy compared with LLM-GNN, where 'DA' denotes the 'C-Density' methods proposed (Chen et al., 2024c), '-W' refers to the weighted cross-entropy loss function used for training, AGE (Cai al., 2017), RIM (Zhang et al., 2021), GraphPart (Ma et al., 2022) are different graph active learning baselines used in the original paper.
Cora
Pubmed
History
Children
TEA-GLM
20.2
84.8
52.8
27.1
LLM-BP
72.59
75.55
59.86
24.81
LLM-BP (app.)
71.41
76.81
59.49
29.4
Table 9: Accuracy compared with TEA-GLM (Wang al., 2024).
Here we present the comparison with LLM-GNN (Chen et al., 2024c) in Table. 8. We compare with three different graph active learning heuristics from their original paper. Our training-free free methods, LLM-BP and LLM-BP (appr.) achieves top performance on Citeseer and Wikics, while performs comparably with the baselines in Cora and Pubmed. Note that the results of LLM-GNN are from Table. in the original paper.
The comparison with TEA-GLM is shown in Table. 9, Results of TEA-GLM are from Table. in their original paper.
D.6. Experiment Results in Few-Shot Setting
We use 10 different random seeds from 42 to 52 sample the k-shoo labeled nodes from training dataset, and report the average accuracy and macro Fl score with standard variance. Results are shown in Table. 10. Across all the ks, our LLM-BP achieves the top ranking performance across all the eleven datasets, exhibiting similar insights with the zero-shot setting.
D.7. Zero-Shot Link Prediction Results
For each dataset, We randomly sample & remove 1000 edges and 1000 node pairs from the graph testing data. A straightforward approach is to compare the cosine similarity between node embeddings to determine the presence of a link. Specifically, we aggregate embeddings for 3 layers on the incomplete graph and compute the cosine similarity between node representations, achieving better zero-shot performance than SaAMs--wih-Grrph-ddaaa
methods (Wang et al., 2024; Chen et al., 2024b; Tang et al., 2024a), as shown in Table. 11. Note that the performance in the table refers to MiMh--hrrrapp--Ae
that have only been trained on other tasks and never on link prediction tasks.
20

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
Cora
Pldeasd
Hilear
Chidron
Wilkee
Comeet
Wacceds
Warkingss
Aug Rork
37 13346
T0T
Siee
C3 1 45.056
155+26
167551 18
166.3
1166665
756667
47
15
10
8.5
Site
106-11
97418
18045
179664
84
13346.
361460
5.3-34
421-5a
56666
903e6
415-65
175-104
57
T6:33aag RP
1-56
107465
035475
711474
123630
13627
3-18
1-35
570673
03364
01146
16
61 68
3:34176
10041:
43413
776-56
911-77
919-10
16.5e104
85
15.+11
100de:
750-1
363451
113we1
(D3444
425412
167-313
165-1n0
74
L1M coans
Kio
-2. 1-6.1 13
543464
[T:2431
13/631
167223
16-101
(006:31
51446
18imin:
1.8 34
11M--9 roan)
S6..k11
366-17
618674
542474
(586113
513466
716488
5364775
02-15:
033224
313924
15
20125
3.3050
41436.5
4F3013
47481123
111
11.4
Sicn
57.305.
64:855
42.0824
25.4224
11.8803
325531
064240
52.3860
424865
365067
35385.9
913:58
05
9.5
22:3235
T6-3lage
345867
775577
672811
66.649
714456
116663
22
(2.4500
22.3221 162221
1 159e
56355
57.004
S3.142
113343
755523
(82e123
31.4550
55 53
T.B.slaage
13.4511
51.420 1833255
18.2
505529 36
133433
16382.
(636111
315584
6200123
913558
63 65
M
51.5e57
11:150
11.4414: DP
137363
03460
474404
2411
187637
$1.5133
341851
13115
72325
SL5641
61 59
L135-22 toan)
20.110
53.544
719451
11255
12:45
T144121
S.3.2.
LL36-30
32 (eam)
01.7642
013323
01585.1
$1.459
30,2110
227235
21761
56.7227
57.447
55.643
11.368
$45667
$1366
963641
1218115
24
Siten
55.425
555470
413-39
Kio
17
14 (4345))
21
201
1 Sc4e12
350664
(37x11
745457
61675
5:5-12
74
74
756653
758054
114657
62:5-1
Slne
033666
563-16
714419
1:344:
S14470
S.5-6
S.5412
71.545
11333
M03-4
555-1
75
(6/663
113
515474
31,3410 31
31.360
63360
1E315
711-45
65 53
11MM
65.3634
(00011
72/66-1
124455
Sila1]
313660
(64411
313.44
565-0
L1M
06.163
(7.655
633651
16366.2
36.611
634224
653-37 Alleh
$13651
63326
163648
19
19
14M--0 tran) UP Saper
660013
667764
754665
34166
364666
266677
27
62.6234
6-
024615
574454
774444
TEA6L
77468
661654
24
24
70.544
455568
565-45
25.133
Shee
BP
Th be3
65.e11 T
$85525
319e1
005-1 1 Sm
6330825
187866
366662
184
105
Riv
76
993663
35002
181-1880
316434
$13+19
3-3-4
03-46
16
60:2-16
333631
N.3-13
13 MTSee
Kew
62
6- 70:-11 13:434
655467
17.+1
6-685-1 663634
115-50
D541
815-17
(806)
015-15
74 15
13 MTNe
315467
815-1
633-1
53
11M (een))
70:6-33
1-11 (41-2.
11
(3.5-11
5-1-1
(9-3- 71
859433
413-17
187e5]
856-37
061-11
1IM--0 32 tran)
X0
20
72.5-13
12.322 07.3613
156460
345-24
467724
25 x 76.203 71551. 703-24 7146244
01-11
016417
166663
f11-14
074-14
24 26
11M rean)
2ppr
71.4435
715-37 10:122
66.5011
261-14
15 736450
31,6631 Sutell Se 756-33 71a-31
863624 118438
933-19
913617
38662
858-33
Table 10: Few-Shot Performance. 'T-E-3-Large' is short for -mmeedddng----aaae
We leave the design of adap-vee embeddings and generalized graph structural utilization for link prediction as future work, including adsktadattvve encoding prompts.
E. Prompts
E.1. Task Description for Vanilla LLM2Vee without Class Information
Table. 12 shows the task description for vanilla LLM2Vec encoder across all the datasets.
E.2. Prompts for Vanilla LLMs
Table. 13 shows tha task description for vanilla LLM decoders.
21

---

Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models
Citation Graph
E-Commerce & Knowledge Graph
Cora
Citeseer
Pubmed
History
Children
Sportsfit
Wikics
OFA
0,492
0.481
0.431
0.484
0.517
LLaGA
0.527
0.543
0.515
0,500
0.502
GraphGPT
0.520
0.569
0.449
0.422
0.597
TEA-GLM
0.586
0.689
0.579
0.571
0.553
SBert
0.979=0.033
0.990#0.001
0.979+0.000
0.985+0.002
0.972#0.030
0.975+0.003
0.972+0.005
Text-Embedding-
-iinbeddding--Largeee L-rge 0.975=0.003
0.989=0.000 002 0.979=0.000
0.985#0.001
0.980#0.002
0.987#0.001 0.977=0.00 002
LLM2Vec
0.966#0.004 0.98240.002 0.970=0.003
0.971 0.973+0.003 0.975#0.002 0.978+0.008
Table 11: Performance zero-shot link prediction tasks (AUC). Results of baselines from (Wang et al., 2024).
Dataset
Task Description
Cora
Encode the text of machine learning papers:
Citeseer
Encode the description opening text of scientific publications:
Pubmed
Encode title and abstract of scientific publications:
History
Encode the description or title of the book:
Children
Encode the description or title of the child literature:
Sportstit
Encode the title of good in sports & fitness:
Wikies
Encode the entry and content of wikipedia:
Cornell
Encode the webpage text:
Texas
Encode the webpage text:
Wisconsin
Encode the webpage text:
Washington
Encode the webpage text:
Table 12: (Task description} | for vanilla LLM2Vec (Li et al., 2024a) encoder. See Eq. 8 for detailed prompting format.
Dataset
Task Description
Cora
opening text of machine learning papers description or opening text of scientific publications title and abstract of scientitic publications description or title the book description or
Citeseer
Pubmed
History
Children
child literature
Sportsfit
the title of a good in sports & fitness entry and content of wikipedia webpage text webpage text webpage text webpage text
Wikies
Comell
Texas
Wisconsin
Washington
Table 13: (Task description] in the prompts for both vanilla LLM decoders (See Section. B.3) and task adaativee encoder (See Section. B.2).
22


Reviews:
[{"review_id": "PZJQKbb3an", "reviewer": "Reviewer_JW3s", "summary": "This paper explores zero-shot generalization in graph problems on Text-Attributed Graphs (TAGs) using a pure LLM-based approach. The authors propose two key principles for model design:\n\n- Task-Adaptive Embeddings – An LLM-based encoder processes raw node text along with a prompt, allowing node embeddings to dynamically adjust based on the prompt content.\n- Graph Aggregation System – The graph is modeled as a Markov Random Field (MRF), and Belief Propagation (BP) is mimicked to perform aggregation.\n\nThe proposed approach is evaluated on graph datasets from multiple domains, considering both homophilic and heterophilic scenarios.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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*:\n\n**1. [New Class with limited data]** \n\nLLM-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:\n\nDue 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.\n\nRegarding 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.\n\n**2. [Applying LLM-BP to Graph-level Tasks]** \n\nThis 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. \n\nThat 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.\n\n**3. [Limitation in QA tasks]** \n\nWe 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.\n\n**4. [zero-shot link prediction]** \n\nFor 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.", "claims_and_evidence": "The claims are accurate and supported by clear evidence.", "methods_and_evaluation_criteria": "The model design is promising, built on two important principles. The idea of using prompts along with node text as input to an LLM encoder to learn adaptive node embeddings is particularly interesting.\n\nHowever, I have a question regarding the second principle. In the LLM-BP algorithm, the method for calculating class embeddings seems to rely on the assumption that there is abundant data for each novel class. Is that correct? If a category is truly new and has very limited data, how would this method adapt? What is the reasoning behind this design choice?\n\nThe evaluation is also well-structured, including zero-shot baselines from different model types (LLM, GNN, LLM+GNN) and demonstrating performance improvements on these tasks. Additionally, the visualization of the embedding space strengthens the claims made in the paper.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "The authors made a comprehensive discussion of the related works.", "other_strengths_and_weaknesses": "- Strength: \n1) The paper is well-written, clearly presenting both the motivation and model details.\n2) The model design is interesting and thoughtfully structured.\n3) The experiments demonstrate strong performance, supporting the proposed approach.\n- Weakness: \n1) Please refer to the Methods and Evaluation Criteria section for specific concerns.\n2) Additionally, I wonder whether this approach can be generalized to zero-shot graph classification tasks. Another potential limitation is that the model output is still not fully flexible, which makes it difficult to handle zero-shot QA tasks effectively.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- I notice the link prediction zero-shot performance is pretty high compared to baselines, could you explain the possible reason?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E6R597aAzG", "reviewer": "Reviewer_ppW1", "summary": "This paper tackles node classification on text-attributed graphs (TAGs) -- graphs where each node has a textual description but labelled examples are scarce. It identifies two major challenges of existing approaches that utilise LLMs for this task: *(i)* LLMs have limited context length, making it hard to include extensive neighbor information for a node, and *(ii)* there is a mismatch between typical node embeddings (from graph encoders) and the token-based input space of LLMs. To address these, the authors propose LLM-BP, a framework based on two principles. First, they create task-adaptive text embeddings for each node by leveraging the idea of LLM2Vec with carefully crafted prompts that include task description and class information. Second, instead of feeding aggregated neighbor embeddings into an LLM, they perform a belief propagation (BP)-inspired label inference on the graph, using an LLM to estimate the edge coupling parameters (essentially the graph’s homophily/heterophily) for adaptive neighbour aggregation.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n**1. [Average Ranking]**  \n\nWe 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.\n\nTo 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.\n\n|  | Citation Graph |  | E-Commerce & KG |  | School Webpage |  |\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n|  | Acc | F1 | Acc | F1 | Acc | F1 |\n| Sbert | 8.3 | 7.3 | 9.3 | 8.8 | 5.8 | 6.0 |\n| Roberta | 7.3 | 7.0 | 7.5 | 8.0 | 6.8 | 7.0 |\n| Text-Embedding-3-Large | 5.3 | 4.3 | 7.3 | 6.3 | 3.3 | 2.5 |\n| LLM2Vec | 8.3 | 5.3 | 6.5 | 5.5 | 3.8 | 4.0 |\n| SBert + NA | 5.0 | 5.0 | 6.0 | 5.8 | 8.3 | 8.3 |\n| GPT-3.5-turbo | 5.0 | 11.3 | 3.5 | 6.3 | 7.3 | 8.3 |\n| GPT-4o | 6.0 | 10.0 | 3.5 | 3.5 | 7.0 | 5.5 |\n| UniGLM | 11.0 | 10.3 | 10.8 | 10.5 | 12.0 | 10.8 |\n| ZeroG | 9.3 | 9.3 | 12.3 | 12.0 | 13.8 | 15.8 |\n| DGI | 15.3 | 15.3 | 15.3 | 16.0 | 15.0 | 15.0 |\n| GraphMAE | 15.7 | 15.7 | 14.3 | 15.0 | 12.3 | 13.8 |\n| OFA | 13.7 | 13.3 | 14.8 | 15.0 | 15.3 | 16.3 |\n| GOFA | 5.7 | 3.7 | 7.0 | 7.3 | 10.3 | 10.5 |\n| GraphGPT | 14.3 | 15.7 | 14.5 | 14.3 | 14.8 | 14.3 |\n| LLAGA | 16.0 | 15.0 | 15.8 | 14.5 | 14.5 | 11.8 |\n| LLM-BP | 3.0 | 2.0 | 2.3 | 3.0 | 1.3 | 1.3 |\n| LLM-BP (appr.) | 3.3 | 2.3 | 2.8 | 1.5 | 1.8 | 2.3 |\n\n**2. [Empirical gain of LLM-BP over GPT-4o on homophily data]** \n\nWe 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.\n\nMore 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.\n\nTo 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.\n\n|  | Cora |  | Citeseer |  | Pubmed |   |\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n|  | Acc | F1 | Acc | F1 | Acc | F1  |\n| GPT-4o | 58.67 | 48.01 | 62.19 | 46.76 | 70.32 | 51.38  |\n| LLM-BP | 68.91 | 67.36 | 69.04 | 65.98 | 74.36 | 74.06  |\n| LLM-BP (appr.) | 67.5 | 65.62 | 67.87 | 64.92 | 76.68 | 75.55 |\n\n\n**3. [Pre-training Free Claim]** \n\nThank 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.”*\n\nOur 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.  \n\n-------------\n\nWe hope this response addresses the reviewer’s concerns, and we would be happy to provide further clarification if needed.", "claims_and_evidence": "Several claims regarding LLM-BP’s effectiveness are questionable, particularly in how its performance is measured and presented.\n\n1. **Misleading Use of Average Ranking**: The claim that \"LLM-BP and LLM-BP (appr.) achieve the highest average ranking\" is misleading due to dataset size imbalance. Homophilic datasets (e.g., Cora, Citeseer, Pubmed) are much larger than heterophilic ones (e.g., Cornell, Texas, Wisconsin), yet the ranking metric treats all datasets equally. This underemphasises LLM-BP’s weaker performance on large datasets while inflating its success on smaller ones, distorting the overall conclusion.\n2. **Limited Gains on Large, Homophilic Graphs**: LLM-BP performs similarly to or worse than GPT-4o on homophilic graphs, where node text alone is highly informative and graph structure contributes little additional value. Since homophilic datasets are much larger, this suggests that the ranking metric overstates LLM-BP’s generalisation ability. \n3. **Misleading \"Pre-training-Free\" Claim**: The paper states: *\"Unlike LLM-BP which is training-free, most of the baselines–except from vanilla encoders, LLMs or NA–require pre-training.\"* This is misleading because LLM-BP relies on a pre-trained LLM, just as other methods rely on pre-trained models (e.g., fine-tuned graph encoders). The correct distinction is that LLM-BP does not require fine-tuning on graph-specific data.\n\nThe third point is relatively minor but the first two demonstrate strong limitations of this work.", "methods_and_evaluation_criteria": "The general applicability of the proposed methods remains questionable and it has been discussed in *Claims And Evidence*.", "theoretical_claims": "The proposed methodology is largely based on established concepts in probabilistic graph models and appear to be correctly applied. There are no entirely new theoretical claims that require deep proof.", "experimental_designs_or_analyses": "This work has a good coverage of datasets and baselines. Issues regarding the analyses have been discussed above.", "relation_to_broader_scientific_literature": "This work is situated at the intersection of graph machine learning and large language models, and the authors do a commendable job relating it to prior research.", "essential_references_not_discussed": "Not found.", "other_strengths_and_weaknesses": "n/a", "other_comments_or_suggestions": "- Formatting issue: The main paper, which does not include a conclusion, exceeds the page limit a bit.", "questions_for_authors": "n/a", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ans6zkIkyh", "reviewer": "Reviewer_JRhf", "summary": "The paper proposes a new method to enhance LLM's ability on graph learning tasks. It first proposes to incorporate task and class information into the node embedding generated by the language model, it then proposes to use belief propagation on pseudo-labels of the nodes to enhance prediction. Experiments show consistent improvement over existing methods.\n\n## update after rebuttal\n\nAfter the rebuttal phase, the paper still stands out as a very interesting paper with outstanding performance, despite some misleading discussion on the contribution, which should be easy to fix during revision. Hence, I am keeping my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n**1. [Connections with other works]** \n\nWe 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.\n\n**2. [Zero-shot experiment setting with SBert]** \n\nThe 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.\n\n**3. [LLM-BP’s advantages on heterophilic data]** \n\nThank you for the comment. We offer two clarifications in response:\n\nFirst, 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.\n\nSecond, 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.\n\nIn 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.\n\n|  | Cornell |  |  |  | Texas |  |  |  | Wisc |  |  |  | Wash |  |  |  |\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| # samples for class embedding | 3c |  | 5c |  | 3c |  | 5c |  | 3c |  | 5c |  | 3c |  | 5c |  |\n|  | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 |\n| Text-Embedding-3-Large | 51.65 | 40.50 | 57.78 | 45.35 | 63.72 | 53.03 | 64.90 | 49.80 | 56.53 | 50.92 | 59.38 | 51.61 | 56.28 | 42.09 | 61.06 | 45.21 |\n| LLM2Vec | 45.28 | 35.74 | 51.20 | 38.35 | 59.17 | 48.23 | 62.11 | 46.40 | 53.78 | 46.79 | 57.69 | 48.69 | 51.39 | 37.74 | 56.59 | 39.31 |\n| Task-Adaptive Encoding | 52.68 | 40.40 | 60.71 | 47.40 | 64.85 | 51.99 | 67.90 | 52.60 | 60.31 | 52.35 | 64.26 | 53.72 | 54.94 | 41.33 | 60.82 | 45.10 |\n| LLM-BP | 56.57 | 44.05 | 66.05 | 50.35 | 66.99 | 53.97 | 69.47 | 53.70 | 61.04 | 53.25 | 65.72 | 54.29 | 55.41 | 43.65 | 62.80 | 46.25 |\n| LLM-BP (appr.) | 56.91 | 43.60 | 65.67 | 50.80 | 67.12 | 53.98 | 70.48 | 55.18 | 59.70 | 52.50 | 63.32 | 52.02 | 55.64 | 43.00 | 62.12 | 46.69 |\n\n\n**4. [Typo in Equation 5.]** \n\nThanks for pointing out the typo, the $q^C_k$ here in Equation. (5) should be fixed with $h^C_k$.\n\n[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.", "claims_and_evidence": "While the author claims principal 1 as a novel observation, incorporating task information to generate embedding has been widely discussed by many works that the author also mentioned. The connection to them should be emphasized.", "methods_and_evaluation_criteria": "Yes, very solid evaluation.", "theoretical_claims": "NA.", "experimental_designs_or_analyses": "How do you conduct zero-shot experiment with sBERT? Do you also compare the cos similarity? In particular, Figure 2 shows that sBERT is better than LLaGA, what's the setup for this comparison.", "relation_to_broader_scientific_literature": "The paper's contribution is mainly the pseudo-label belief propagation process powered by LLM, which seem to bring significant performance improvement. The enhanced embedding paradigm is also effective, yet the improvement on this end is not surprising, and has been studied in various related works.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The paper is well-written, and backed by a comprehensive list of experiments.", "other_comments_or_suggestions": "Is $q_k^c$ in equation 5 $h_k^c$, or is it the candidate embedding introduced earlier, or are they the same thing?", "questions_for_authors": "I am not entirely sure how the model handles heterophilic cases, or is advantageous in heterophily at all. From Figure 6, we see that using the LLM embedding, the heterophlic performance is already good.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Doz6vwSWFn", "reviewer": "Reviewer_gfhg", "summary": "This paper introduces LLM-BP, a framework for zero-shot inference on text-attributed graphs using large language models. The framework requires no training and generalizes well across homophilic and heterophilic graphs. Experiments show that LLM-BP outperforms existing methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank *reviewer gfhg*’s time in reviewing our paper and their constructive comments. Below we try to address the concerns.\n\n**1. [Convergence of BP]** \n\nWe 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.\n\n**2. [Variance metric in Table. 2]** \n\nBelow, 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.\n\nAs 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.\n\n|  |  | Cora | Citeseer | Pubmed | History | Child | Sportsfit | Wikics | Cornell | Texas | Wisc | Wash  |\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Task-adaptive encoding vs. Text-Embedidng-3-Large| Low,Up | -0.3,-0.2 | 0.5,1.0 | -0.3,1.0 | 6.9,9.1 | 4.1,4.4 | 0.7, .8 | 1.1,2.0 | 0.3,0.4 | 3.1,4.7 | 0.1,1.2 | -0.0,-0.1  |\n| | P | 6e-27 | **8e-7** | 0.51 | **7e-21** | **5e-59** | **0.03** | **1e-9** | **2e-25** | **1e-9** | **0.07** | 1e-13  |\n| Task-adaptive encoding vs. LLM2Vec| Low,Up | 0.7,1.3 | -0.2,1.3 | 1.3,2.3 | 3.2,5.2 | 3.3,3.7 | 1.0,2.6 | 1.0,1.8 | 0.4,0.5 | 1.5,2.7 | 0.1,0.8 | -0.2,0.5  |\n| | P | **1e-8** | 0.38 | **1e-10** | **1e-9** | **3e-59** | **1e-4** | **3e-8** | **7e-18** | **5e-8** | **1e-3** | 0.82  |\n| LLM-BP vs. Task-adaptive Encoding | Low,Up | 3.6,4.0 | 2.3,2.5 | 0.6,1.1 | 1.4,1.7 | -0.3,0.4 | 2.3,2.5 | 4.1,4.4 | 0.3,0.4 | 3.2,3.7 | 2.0,2.6 | 5.5,6.5  |\n| | P | **2e-52** | **1e-15** | **1e-6** | **6e-35** | 0.26 | **1e-69** | **8e-65** | **1e-15** | **3e-40** | **1e-16** | **1e-35**  |\n| LLM-BP (appr.) vs. Task-adaptive Encoding | Low,Up | 2.6, 2.8 | 1.5,1.6 | 1.6,1.8 | 1.1,1.3 | 0.3,0.5 | 2.0,2.1 | 4.4,4.8 | 1.9,2.3 | 1.0,1.5 | 0.4,0.6 | 2.8,3.5  |\n| | P | **1e-52** | **2e-57** | **3e-9** | **1e-43** | **6e-20** | **3e-18** | **4e-60** | **2e-4** | **5e-14** | **0.06** | **3e-27** |\n\n**2. [Sensitivity Analysis]** \n\nThanks 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:\n\n|  | Cora |  | Citeseer |  | Pubmed |  | Bookhis |  | Bookchild |  | Sportsfit |  | Wikics |   |\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n|  | value | gap | value | gap | value | gap | value | gap | value | gap | value | gap | value | gap  |\n| ground truth | 0.81 | - | 0.76 | - | 0.79 | - | 0.66 | - | 0.46 | - | 0.90 | - | 0.67 | -  |\n| 100 | 0.70 | 0.11 | 0.81 | 0.05 | 0.81 | 0.02 | 0.73 | 0.07 | 0.35 | 0.11 | 0.81 | 0.09 | 0.52 | 0.15  |\n| 80 | 0.70 | 0.11 | 0.77 | 0.01 | 0.83 | 0.04 | 0.75 | 0.09 | 0.37 | 0.09 | 0.76 | 0.14 | 0.55 | 0.12  |\n| 40 | 0.65 | 0.16 | 0.77 | 0.01 | 0.81 | 0.02 | 0.75 | 0.09 | 0.33 | 0.13 | 0.75 | 0.15 | 0.50 | 0.17  |\n\n\n**3. [Computational Overhead Analysis]** \n\nIt 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: \n\nFirst, obtaining node or class embeddings using an encoder has the same order of complexity as the baseline methods.\n\nSecond, 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.\n\nIf there are specific concerns regarding computational complexity that we may have overlooked, we would greatly appreciate further clarification.\n\n---\n\nWe hope that we have addressed the concerns of *reviewer gfhg*, we would be happy to respond to any other questions.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "While the derivation of BP updates (Section 3.4, Appendix C) is logically presented, the theoretical guarantees for convergence or approximation bounds of the proposed BP variant (Eq. 7) are not rigorously analyzed.", "experimental_designs_or_analyses": "- Error bars or variance metrics (e.g., standard deviation) are missing in the main results (Table 2).\n- Sensitivity of results to the number of sampled edges is not analyzed.\n- Experiments on computational overhead need to be supplemented.", "relation_to_broader_scientific_literature": "The work situates itself within the growing literature on integrating LLMs with graph learning.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "None.", "questions_for_authors": "I am quite concerned about the issue of computational overhead. If we select two nodes each time to query the LLM, the cost for large graph datasets will be extremely high. Can the authors help explain this issue?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes using an LLM-based approach to enhance graph learning on text-attributed graphs. The method is novel, and extensive evaluations are conducted on graph datasets from various domains, demonstrating significant performance improvements over baseline methods. Overall, this is a solid work. To improve the final paper, the authors should clarify the utility of graph structure, provide performance details on both homophilic and heterophilic datasets, and explain incremental improvements specifically on homophilic datasets.
Decision: Accept (poster)