Unleashing the Potential of Text-attributed Graphs: Automatic Relation Decomposition via Large Language Models

We sincerely appreciate the reviewer’s feedbacks. We would like to address the reviewer’s concerns as below.

[Streamlined Prompting of RoSE]

W1. We would like to first clarify that the term “automatic” in our method refers to the pipeline of our relation type identification and labeling, which eliminates the need of manual process; the determination of plausible relation types and edge decomposition are all done by LLMs.

Although the prompt for these LLM agents are manually written, our prompts for relation generator and discriminator are intentionally minimal, requiring only basic and essential information. Specifically, the graph description includes a brief description of the node and edges, a sample node text attribute, and a list of predefined categories. For relation filtering, we apply two guidelines fixed across all benchmarks: (1) exclude edge types beyond the LLM's analytical scope, and (2) retain only essential types. Note that the example node text in these prompts is randomly chosen, and the number of relation types is dynamically determined by LLMs, without the need of manual supervision. By incorporating these compact information, we minimize the introduction of human bias to edge decomposition.

As the reviewer pointed out, these prompts may need slight adaptation for different datasets, since individual graphs exhibit different properties (e.g., citation graphs vs. co-purchasing graphs). However, once edges are semantically classified via RoSE, the enriched dataset is agnostic to the selection of GNN architecture and does not require re-processing, similar to the feature preprocessing stage. Additionally, RoSE leverages LLMs' zero-shot capabilities without needing further fine-tuning, distinguishing it from prior works [1, 2, 3, 4].

---

References

[1] Node feature extraction by self-supervised multi-scale neighborhood prediction, ICLR 2022.

[2] Simteg: A frustratingly simple approach improves textual graph learning, ArXiv preprint (2023).

[3] Llm-to-lm interpreter for enhanced text-attributed graph representation learning, ICLR 2024.

[4] Learning on large-scale text-attributed graphs via variational inference, ICLR 2023.

[5] Sentence embeddings using siamese bert-networks, EMNLP 2019.

[6] Edgeformers: Graph-empowered transformers for representation learning on textual-edge networks, ICLR 2023.

We appreciate the reviewer for giving us chance to have further discussion.

[Upon Feature Encoders]

W2. Our RoSE-efficient is primarily designed to reduce the computational cost while preserving the performance of our original algorithm. While this focus on efficiency may entail some trade-offs in capturing intricate semantic nuances, the semantic richness of Sentence-BERT as a TAG node feature encoder has been widely acknowledged in this field, including [1, 2], with its significant performance enhancement compared to traditional node features. Furthermore, [3] evaluates the quality of generated node descriptions by measuring their embedding similarity to ground-truth descriptions, using Sentence-BERT’s encoding (referred to as the SBERT score), highlighting its effectiveness as an evaluator as well. Hence, we decide Sentence-BERT is a sufficient candidate to apply RoSE-efficient, and the effectiveness of performance preservation of RoSE-efficient with Sentence-BERT is demonstrated in our paper.

Nevertheless, if the input TAG requires exceptionally high semantic fidelity, we recommend two alternative approaches: (1) using our original algorithm, RoSE or (2) employing advanced feature encoders such as fine-tuned Deberta, which is also a widely adopted node feature encoder in TAG domain [1, 4, 5]. Regarding approach (2), we provide a performance comparison of Sentence-BERT and Deberta in the table below.

There are two key observations worth to be highlighted — First, incorporating Deberta into a vanilla GNN further improves performance compared to Sentence-BERT, confirming that Deberta captures richer semantic information. Second, integrating Deberta-based node feature with RoSE-efficient markedly enhances performance over RoSE-efficient + Sentence-BERT, also outperforming a strong GNN+LLM baseline - TAPE [4]. In such a case where we deploy a fine-tuned feature encoder to enhance the semantic modeling capabilities, we find RoSE-efficient to be even more helpful, where the performance gap between RoSE-efficient and vanilla is further pronounced with fine-tuned Deberta features.

Table 3. Node classification accuracy according to different feature encoders, averaged over 10 runs.

---

References

[1] Exploring the potential of large language models (llms) in learning on graphs, KDD Explorations 2024.

[2] One for all: Towards training one graph model for all classification tasks, ICLR 2024.

[3] LLaGA: Large Language and Graph Assistant, ICML 2024.

[4] Llm-to-lm interpreter for enhanced text-attributed graph representation learning, ICLR 2024.

[5] Learning on large-scale text-attributed graphs via variational inference, ICLR 2023.

[Further Experiments on Approximating Ground-truth Edge Types]

W3. Thank you for your positive feedback and insightful suggestions to include knowledge graphs as additional benchmarks. To evaluate the approximation of ground-truth edge types, we provide predefined relation categories in the prompt and instruct the relation decomposer to classify the edge types based on their associated text attributes. This setup allows us to assess how accurately the LLM-based decomposer can infer relation types given the textual context. In our experiments on the Amazon Clothing and Sports datasets, the edge-wise text attributes are user reviews and the corresponding edge types represent user ratings of purchased items. LLMs, including LLaMA family, have been well-regarded for their strong zero-shot, training-free capabilities in text analysis and sentiment interpretation [1, 2, 3]. Hence, this enables the relation decomposer to achieve a reasonable degree of edge classification accuracy, resulting in a minimal performance gap in node classification tasks compared to settings where ground-truth edge types are directly utilized.

Extending our analysis, we conducted additional experiments on two knowledge graphs, Wikidata and YAGO adopted in [4], as suggested. In these experiments, the downstream task is set to link (relation) prediction, as these benchmarks lack node labels and are originally designed for link prediction. Note that the validation and test edges are not accessible during message passing phase in GNN. Hence, the decomposer is instructed to predict the relation type between two connected entities in message-passing edge set, based on their node-wise text attributes. As shown in Table 3, our relation decomposer shows decent classification performance in knowledge graphs as well, leveraging significant zero-shot capabilities of LLMs. This leads to notable performance enhancement compared to vanilla GNN (with no edge decomposition), as well as demonstrating comparable performance to the setting with ground-truth edge type-based decomposition. Furthermore, the results validate the efficacy of our proposed approach in scenarios involving semantically rich and complex edge categories.

We hope these results address your remaining concerns.

Table 4. Edge classification accuracy (%) of our LLM-based decomposer.

Table 5. Link prediction performance of vanilla RGCN, decomposition with ground-truth edge types, and RoSE, averaged over 10 runs (higher, the better).

---

References

[1] LLaGA: Large Language and Graph Assistant, ICML 2024.

[2] Exploring the potential of large language models (llms) in learning on graphs, KDD Explorations 2024.

[3] Label-free Node Classification on Graphs with Large Language Models, ICLR 2024.

[4] Learning to Sample and Aggregate: Few-shot Reasoning over Temporal Knowledge Graphs, NeurIPS 2022.

Dear Reviewer XZxr,

We kindly present additional case studies on our relation decomposer, to provide enriched insights of the impressive performance on approximating ground-truth edge types. As shown in the following examples on Amazon Clothing dataset, our decomposer can well-distinguish relatively unsatisfactory, moderate, and satisfactory sentiments (please refer to the bold-faced parts), resulting in promising edge classification accuracy and thereby significantly improving the node classification performance.

[Raw text attributes and corresponding predicted edge types (ratings) from relation decomposer]

Predicted rating: 1 (unsatisfactory)

I am between S and M depending on the brand in clothes. Read the reviews here and decided on size L for this one. It barely fits me. It was a struggle to hook it in the front, when I finally got it on, it is extremely tight, I can barely breathe and certain movements will cause you pain. I should have gotten size XL to start with, but I will keep it, as it is incredibly motivating to try and work out and lose weight and my body looks fantastic in dresses and pants and dresses that barely fit me looked fabulous on me. I can only wear it for a few hours a day. Wearing it to work is not recommended unless you got the size right

Predicted rating: 3 (moderate)

Delivery was perfect. I ordered a large for my 5'3" and 150 lb frame. My complaint is that the dress was a bit too snug across the bust and the bodice was short. I know how this dress should fit. I grew up seeing my aunt fitting dresses like these for her clients.

Predicted rating: 5 (satisfactory)

These earrings are perfect when you want to go big and fancy without spending a lot of money! I am impressed by how “real” these earrings look. And you don’t have to worry about losing them. Great price for a great look.

[Computational Cost of RoSE]

W2 & Q1. We appreciate the reviewer’s helpful feedback. In response, we present the comparison a detailed comparison of the time and space complexity in Table 2, on large-scale datasets with RGCN as a backbone. For comprehensive analysis, we also include the complexity analysis of GLEM [11], a recent baseline for TAGs that enhances node features through co-training between GNN and LM.

Although our method incurs additional complexity (an average of 121.19 and 23.19 minutes for RoSE and RoSE-efficient, respectively) when compared against vanilla GNN, it offers an effective balance between computational efficiency and performance when compared with GLEM. As shown in the table, both RoSE and RoSE-efficient outperform GLEM. Furthermore, RoSE-efficient reduces the total runtime by an average of 96.94 minutes and peak memory usage by 20,508 MB compared to GLEM.

It is also noteworthy that once the edges are semantically classified, the enriched dataset remains consistent across GNN architectures and requires no additional re-processing. Furthermore, unlike prior methods [8, 9, 10, 11], RoSE leverages language models for relation inference without requiring further fine-tuning, making it both efficient and adaptable.

Table 2. Computational cost analysis of vanilla GNN, GLEM, RoSE, and RoSE-efficient. The comparison is conducted on the machine with NVIDIA RTX A6000 GPU/Intel(R) Xeon(R) Gold 6226R CPU @2.90GHz.

[On Contribution of Relation Discriminator]

W3 & Q2. In response to the reviewer’s comment, we elaborate the design and impact of our relation discriminator in RoSE.

After the relation generator produces a set of plausible relation types, the relation discriminator refines this set by filtering out types that are either infeasible or redundant. The filtering process is based on two guidelines fixed across all benchmarks: (1) exclude relation types beyond the LLM's analytical scope, and (2) retain only essential relation types. Using these guidelines, along with basic graph descriptions (node/edge representations, predefined categories, and a randomly sampled text attribute), the discriminator removes noisy candidates that the generator may have initially produced. We provide detailed prompt templates for relation discriminator in Appendix A (p. 15).

The effectiveness of the relation discriminator is shown in Table 4, where consistent improvements are observed across 23 out of 24 settings when the discriminator is applied, compared to using unfiltered relation types (only the generator and decomposer). Additionally, we illustrate the types retained and filtered out by the discriminator in Table 3 (main manuscript, p. 7) and Table 10 (Appendix, p. 18). In Table 3 for the Cora dataset, the generator produces plausible but overlapping types like “complementary insights” and “contrasting approaches,” as well as infeasible types such as “performance benchmark”, which is difficult to infer from nodes’ text attributes (i.e., paper abstracts). The discriminator effectively removes such redundant or infeasible types, resulting in a more focused set of relation types. Similarly, in Table 10 for the Texas dataset, the “studies_under/has_student” relation is redundant considering the presence of the “advised_by/advises” relation, and therefore filtered out by the relation discriminator.

Hence, these results demonstrate the relation discriminator’s role in refining the relation set, leading to performance enhancement by retaining only essential and distinct relation types.

We sincerely appreciate the reviewer’s feedbacks. We would like to address the reviewer’s concerns as below.

[Upon Clarification of Our Setting]

W1. We thank the reviewer for the insightful comment. However, we respectively disagree with the reviewer’s perspective, for three aspects: (1) Prevalence of graphs without such text attributed edges, (2) Our observation on edge simplification goes beyond performance gains in current dataset but further provides insights on future dataset curation works., and finally that (3) RoSE offers flexibility to pre-constructed datasets. We detail each assertion in the following paragraphs.

(1) Prevalence of “Conventional Graphs”

We acknowledge that some datasets [1] include textual attributes as edge features. However, we emphasize that this is not the case for many real-world graphs [2, 3, 4, 5, 6, 7, 10], where datasets are often pre-constructed without such textual edge descriptions or types. Our work specifically aims to enhance the performance of GNNs on these textual-attributed graphs that lack edge-level textual attributes during the dataset construction process.

In such scenarios, two main options arise: (a) manually labeling edges with textual attributes or (b) automatically generating textual descriptions for edges. RoSE provides a superior solution compared to both approaches. It avoids the substantial cost of manual labeling by leveraging automation through LLMs while delivering significantly better performance gains than naïve methods for generating edge descriptions. The empirical results in Table 1 below validate this assertion. As shown, RoSE surpasses GNNs trained with naïve textual edge descriptions from LLMs, highlighting the empirical significance of our semantic decomposition.

(2) Insights to Future Data Curation Works

We further emphasize the significance of our work, particularly in highlighting the critical role of edge simplification for text-attributed graphs (TAGs) in the construction of future datasets. Specifically, our observation underscores the importance of ensuring discernibility among edges during the dataset construction process of text-attributed graphs with edge attributes. By prioritizing the semantic differentiation of edges - either in terms of feature vectors or raw text, dataset creators can facilitate more effective downstream tasks, enabling GNNs to better capture meaningful relationships within the graph.

(3) Offering flexibility to pre-constructed datasets

Additionally, we believe RoSE has the potential to provide additional flexibility to pre-constructed datasets. More specifically, the optimal edge attributes for a given TAG may differ when the task of focus changes (e.g., addition / exclusion of labels of node classification, change of classes in node classification). In such a scenario, manually re-identifying and assigning relevant edge attributes demands significant burden. However, when incorporated with RoSE, the graph's edge attribute can be dynamically changed based on the targets and tasks, where the relation generator and discriminator selects appropriate set of edge descriptions to solve the given task. This offers engineers an additional flexibility in their training process, with a high possibility (demonstrated through the versatility of our work) of performance gain.

Table 1. Node classification accuracy (%) of RoSE and GNNs with textual edge descriptions, averaged over 10 runs.

---

References

[1] TEG-DB: A Comprehensive Dataset and Benchmark of Textual-Edge Graphs, ArXiv preprint (2024).

[2] Automating the construction of internet portals with machine learning, Information Retrieval 2000.

[3] A wikipedia-based benchmark for graph neural networks, ArXiv preprint (2020).

[4] Collective classification in network data. AI magazine 2008.

[5] Learning to extract symbolic knowledge from the world wide web, AAAI/IAAI 1998.

[6] A comprehensive study on text-attributed graphs: Benchmarking and rethinking, NeurIPS 2023.

[7] Open graph benchmark: Datasets for machine learning on graphs, NeurIPS 2020.

[8] Node feature extraction by self-supervised multi-scale neighborhood prediction, ICLR 2022.

[9] Simteg: A frustratingly simple approach improves textual graph learning, ArXiv preprint (2023).

[10] Llm-to-lm interpreter for enhanced text-attributed graph representation learning, ICLR 2024.

[11] Learning on large-scale text-attributed graphs via variational inference, ICLR 2023.

We sincerely appreciate the reviewer’s feedbacks. We would like to address the reviewer’s concerns as below.

[Efficiency of Relation Generator/Discriminator]

W1. To clarify, our relation generator and discriminator are prompted only once per dataset, prior to GNN training. In this initial step, the generator produces plausible relation candidates, which are subsequently filtered by the discriminator. This entire process is completed within a single round of prompts, with no need for additional prompting during GNN training or inference. Moreover, in inductive setting, only the relation type assignment is required, without the need to send new queries to the relation generator or discriminator. Unlike prior methods [1, 2, 3, 4], RoSE utilizes language models for relation inference without necessitating further fine-tuning, ensuring adaptability and ease of use.

[Performance on Cora & Pubmed Datasets]

W2. We appreciate the reviewer’s thoughtful comment. As discussed in Section 3, decomposing edges into multiple semantic relations enhances node representations by making them more distinguishable. In datasets like Cora and Pubmed, however, the original GNN accuracy is already high, indicating that the node features themselves are sufficiently distinguishable (please refer to the Figure 6 in Appendix of our revised manuscript). Additionally, both datasets are categorized as homophilous graphs, suggesting that GNNs achieve high representation quality through neighborhood aggregation alone. As a result, the performance enhancement when integrated with our method could be limited for further improvement. The benefits of our method is more pronounced in cases where GNNs face challenges due to their ambiguous node representations. Nevertheless, as demonstrated in the table below, our method can achieve superior performance compared to TAPE [3] (a strong recent GNN-LLM baseline), when combined with a fine-tuned feature encoder.

Table 1. Node classification accuracy (%) of RoSE and TAPE integrated with Deberta feature encoder, utilizing RGCN as a backbone.

---

References

[1] Node feature extraction by self-supervised multi-scale neighborhood prediction, ICLR 2022.

[2] Simteg: A frustratingly simple approach improves textual graph learning, ArXiv preprint (2023).

[3] Llm-to-lm interpreter for enhanced text-attributed graph representation learning, ICLR 2024.

[4] Learning on large-scale text-attributed graphs via variational inference, ICLR 2023.

[5] Sentence embeddings using siamese bert-networks, EMNLP 2019.

We sincerely appreciate the reviewer’s feedbacks. We would like to address the reviewer’s concerns as below.

[On Our Original Contribution]

W1. We appreciate your constructive feedback. However, we respectfully disagree with the characterization of our approach as standard LLM-GNN approaches. While prior works have indeed integrate LLMs with GNNs, they primarily focus on enhancing node-wise attributes [1, 2, 3, 4, 5, 6]. However, as we have emphasized in related works section, all these approaches treat graph edges as uniform, binary connections without capturing the nuanced, inherent semantics that many real-world TAGs contain. Additionally, existing methods that attempt to enrich edge attributes [7, 8] rely on settings where edges already have ground-truth descriptive texts or predefined relation types, limiting their applicability.

In contrast, RoSE addresses this limitation by leveraging analytical capabilities of LLMs to infer and assign rich semantic relations to edges in TAGs where edge descriptions and ground-truth labels are absent. This enables conventional TAGs to be enriched with meaningful relational information, consequently leading to empirical performance improvements.

---

References

[1] Textgnn: Improving text encoder via graph neural network in sponsored search, WWW 2021.

[2] Node feature extraction by self-supervised multi-scale neighborhood prediction, ICLR 2022.

[3] Simteg: A frustratingly simple approach improves textual graph learning, ArXiv preprint (2023).

[4] Graphformers: Gnn-nested transformers for representation learning on textual graph, NeurIPS 2021.

[5] Learning on large-scale text-attributed graphs via variational inference, ICLR 2023.

[6] Llm-to-lm interpreter for enhanced text-attributed graph representation learning, ICLR 2024.

[7] Edgeformers: Graph-empowered transformers for representation learning on textual-edge networks, ICLR 2023.

[8] Learning multiplex embeddings on text-rich networks with one text encoder, ArXiv preprint (2023).

[On Complexity of RoSE]

W2 & Q1. We would like to clarify that the time analysis in our manuscript encompasses the process of edge sampling and decomposition process. In addition to the time analysis provided in the main paper, we present a detailed comparison of the time and space complexity for the following scenarios: (1) edge sampling with edge label assignment (Table 1), (2) training GNNs with/without edge attributes (Table 2), and (3) overall procedure, all on large-scale datasets using RGCN (Table 3). For a thorough evaluation, we also include the complexity analysis of GLEM [5], a strong baseline that enhances node features through co-training between GNN and LM (Deberta).

As shown in Table 2, incorporating edge attributes into downstream GNN training sacrifices an average overhead of only 6.81 seconds compared to training a vanilla model. Furthermore, both RoSE and RoSE-efficient outperform GLEM, as demonstrated in Table 3. Notably, RoSE-efficient reduces the total runtime by an average of 96.94 minutes and peak memory usage by 20,508 MB compared to GLEM. These results highlight that our method offers a balance between computational efficiency and performance.

We also emphasize that once edges are semantically classified via RoSE, the model developer can freely choose the GNN model to be utilized. Meaning that, once processed, the dataset is agnostic to the selection of GNN architecture and does not require re-processing, analogous to the feature preprocessing stage. Additionally, unlike prior works [2, 3, 5, 6], RoSE does not require further fine-tuning of language models, leveraging the significant zero-shot capabilities of LLMs to determine semantic relations based on text.

Table 1. Complexity analysis of relation type assignment (and edge sampling for RoSE-efficient).

Table 2. Complexity analysis of downstream GNN training.

Table 3. Complexity analysis of total procedure. The comparison is conducted on the machine with NVIDIA RTX A6000 GPU/Intel(R) Xeon(R) Gold 6226R CPU @2.90GHz.