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

Authors: Hyunjin Seo, Taewon Kim, June Yong Yang, Eunho Yang
Primary area: learning on graphs and other geometries & topologies
Keywords: large language models (LLM), pretrained language models (PLM), text attributed graphs (TAG), graph neural networks (GNN)

Abstract:
Text-attributed graphs (TAGs) integrate textual information with graph structures, offering unique opportunities for leveraging language models to enhance node feature quality. However, our extensive analysis reveals that the downstream task performance on TAGs is hindered by the graph structure itself; treating diverse semantics(e.g. “advised by”, “participates in”) as a singular relation (e.g. hyperlinks). By decomposing conventional edges into distinctive semantic relations, we discover significant improvement in GNNs’ downstream task performance. Motivated by this, we present **RoSE** (Relation-oriented Semantic Edge-decomposition), a novel framework that leverages large language models (LLMs) to automatically decompose graph structures into different semantic relations without requiring expensive human labelling or domain expertise. **RoSE** consists of two stages: (1) identifying semantic relations via an LLM-based generator and discriminator, and (2) decomposing each edge into corresponding relations by analyzing raw textual contents associated with connected nodes via an LLM-based decomposer. The decomposed edges provided by our framework can be applied in a model-agnostic, plug-and-play manner, enhancing its versatility. Moreover, **RoSE** achieve state-of-the-art node classification results on various benchmarks and GNN architectures.

Decision: reject
Reviewer scores: 5, 5, 6, 5

Reviews and discussion:
<thread>
creation date:
1729455314702

thread_type:
official_review

<thread_object>
creator: reviewer_xzxr

<content>
summary:
This paper proposes a prompting-based method for augmenting edge types in graphs. It contains several stages, such as relation generation, relation filtering, and relation decomposer. Experimental results on node classification show that the augmented edge types are useful.

strengths:
1. Using LLM to augment the predefined graph structure is interesting.
2. The paper is well-written and easy to follow.
3. Amount of experimental results are provided to demonstrate the effectiveness of the proposed method.

weaknesses:
1. My biggest concern is that the proposed method is not as totally automatic as they claimed, since for graphs from different domains, this method requires a large effort to try the best prompt for graph descriptions and relation filtering guidelines.
2. The proposed efficient relation-type annotation strategy seems too simple. The assumption that the neighbor nodes should have a similar relation type with the central node is not realistic. For example, a paper can cite one paper via a positive sentiment but cite another via a negative sentiment.
3. The proposed method can be viewed as an edge classification method. The authors should include some datasets with ground-truth edge labels to show how much the proposed method can approximate the ground-truth edge labels. In the experiment, the authors should also include the node classification performance with the ground-truth edge labels for comparison.

questions:
see weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730595577706

thread_type:
official_review

<thread_object>
creator: reviewer_ndzw

<content>
summary:
The paper presents a framework RoSE (Relation-oriented Semantic Edge-decomposition) to enhance the representation learning of Graph Neural Networks by decomposing edges of TAGs into semantically meaningful relations. The authors highlight the limitations of traditional TAG methods that treat all edges uniformly and demonstrate that automatic edge decomposition using LLMs significantly improves node classification performance. The framework operates in two stages: (1) identifying potential relation types with an LLM-based generator and discriminator, and (2) categorizing each edge into identified relation types using LLMs. Extensive experiments show that RoSE leads to up to a 16% improvement in node classification accuracy on benchmark datasets.

strengths:
1. The introduction of RoSE as an automated method to address the challenge of edge oversimplification in TAGs is interesting. 
2. The authors provide extensive experiments that demonstrate substantial improvements across multiple datasets and GNN architectures. 
3. The introduction of an efficient edge-sampling strategy to minimize LLM queries is a thoughtful addition.

weaknesses:
1. One of the biggest concerns is edge oversimplification in TAGs may not be a problem. There is a type of graph called textual-edge graphs, where edges are annotated with rich text information [1, 2].
2. Although RoSE introduces methods to improve efficiency, the initial decomposition process may still be resource-intensive for practitioners working with massive TAGs. A more detailed analysis of the computational cost compared to traditional methods would strengthen the paper.
3. The relation discriminator's role and effectiveness are crucial to RoSE, yet the description of its implementation and performance impact lacks clarity. Further explanation or ablation studies would help clarify its significance.

[1] Li, Zhuofeng, et al. "TEG-DB: A Comprehensive Dataset and Benchmark of Textual-Edge Graphs." arXiv preprint arXiv:2406.10310 (2024). 
[2] Ling, Chen, et al. "Link Prediction on Textual Edge Graphs." arXiv preprint arXiv:2405.16606 (2024).

questions:
1. Can you provide a more in-depth analysis of the computational cost associated with RoSE, especially for large-scale datasets? A direct comparison with simpler baselines could give a clearer picture of the trade-offs involved.
2. Can you elaborate on the design and function of the relation discriminator, including specific examples and results from ablation studies?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730792137271

thread_type:
official_review

<thread_object>
creator: reviewer_efoe

<content>
summary:
This paper focus on the study of including LLMs in enhancing the textual meaning of edge connections in the graph, and then use multi-relation types graph to improve the prediction performance compared to using single-type graph structure. The authors first use a LLM generator to generate the possible types of edges, and another LLM discriminator is adopted to choose the appropriate edge type(s). A multi-relational GNN is applied on the obtained graph for prediction targets.

strengths:
1. The presentation of this paper is clear and easy to follow.
2. The overall idea of enhancing the edges with semantic level types is interesting.
3. The results from human labeled edge types have shown promising potential of adopting enriched semantic edges idea.

weaknesses:
1. The efficiency is a main concern. As the proposed framework requires LLM on both edge types generation and discrimination, it requires significant amount of time in these steps for both training and inference stage. This largely harms the practical potential of this method.
2. The experimental results on different datasets varied a lot. On some datasets such as Cora and Pubmed, the improvement of proposed method is very limited. Can authors give intuitive reasons behind it?
3. In some cases the semantic description between two nodes may not be able to be classified into several types, or require some domain knowledge. How the proposed method can handle those situations?

questions:
Will the number of generated types (5, 10, 20, etc) affect the results a lot?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730939210446

thread_type:
official_review

<thread_object>
creator: reviewer_g77l

<content>
summary:
The paper identifies the problem that conventional edges on text-attributed graphs hinder the representation learning process of GNNs on downstream tasks when integrated with advanced node features. To resolve the issue the edges are decomposed into semantic relations by the LLM. This has also been proposed as a data enhancement method where edge attributes are absent. 
The relations are identified using an LLM-based relation generator and discriminator through prompting. To avoid labeling every edge and making a lot of LLM queries, similar relations are applied to similar semantic relations nodes with a threshold value.

strengths:
The paper presents good experiments with multiple runs to prove their hypothesis. Multiple GNN architectures have been used on various datasets which adds to the fact the technique works.

weaknesses:
1. I have concerns about the novelty of the ideas presented. Generating edges' relations through LLM is not new; it has been shown to be the basic strategy for combining LLMs and GNNs. 
2. As asked in the "Question section" I am not sure that the time and space complexity added would be worth the accuracy increase. Presenting those numbers would make the argument stronger.

questions:
What is time increment for each process? The time table only has comparison on the sampling approach vs not using the approach. What is the time takes for - 
1. Assigning edge labels
2. Training with edge attributes
</content>
</thread_object>

</thread>
<thread>
creation date:
1732218483807

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
Dear Reviewers and AC, 

We sincerely appreciate your dedicated time and insightful feedback in improving our manuscript.

As acknowledged by the reviewers, we propose a novel observation on GNNs (efoe, ndzw) - the oversimplification of edges in prior textual attributed graphs (TAGs), and the possibility of enhancing performance via semantic edge decomposition. To address this, we propose RoSE, a novel (efoe, ndzw, XZxr) framework that utilizes the capabilities of LLMs to decompose edges into semantic categories. Our method is supported through extensive analysis on multiple benchmark datasets and architectures, demonstrating both its efficacy and versatility (g77L, ndzw, XZxr).

To address your constructive comments, we have conducted the following additional experiments and discussions:

- **Detailed computational cost analysis** including peak memory and total duration, compared with LLM-based graph enhancement methods — RoSE-efficient offers a **balance** between computational efficiency and performance.
- Additional **mitigation strategy in extreme scenarios** — *e.g.*, when relationships cannot be classified into distinct types.
- Discussion upon the importance of edge oversimplification on TAGs — **RoSE gives the second chance to pre-constructed conventional graphs**.
- Additional experiments demonstrating that **RoSE effectively approximates ground-truth edge types**.

Thank you for your guidance and support.

Sincerely,

Authors.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732509403058

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Gentle Reminder

comment:
Dear Reviewers and AC,

We thank the reviewers once more for the constructive feedbacks in improving our manuscript.

As the rebuttal period is nearing to its end, we kindly request you to review our responses, as this week (~26th) marks the end of our interaction period.

We have faithfully addressed your concerns, and further highlight the main contributions of RoSE once again:

- **Prevalence of Graphs Without Text-Attributed Edges**: For many real-world graphs [1, 2, 3, 4, 5, 6, 7], datasets are often pre-constructed without such textual edge descriptions or types. RoSE is tailored to enhance GNN performance on these graphs during the dataset construction process. Note that existing LLM-GNN approaches for TAGs primarily focus on enhancing node-wise attributes, while treating edges as uniform, binary connections without identifying the inherent semantics.
- **Insights for Future Dataset Curation**: We have revealed the importance of ensuring discernibility among edges during the dataset construction in our observation. By prioritizing the semantic differentiation of edges via RoSE - 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.
- **Flexibility for Pre-Constructed Datasets**: RoSE provides additional flexibility to pre-constructed datasets. In reality, 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, offering additional flexibility to engineers in their training process, with a high performance gain.

We sincerely thank you for your time and efforts in reviewing our paper, and your insightful and constructive comments.

Thank you,

Authors.

---
**References**

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

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

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

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

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

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

[7] Llm-to-lm interpreter for enhanced text-attributed graph representation learning, ICLR 2024.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733121029348

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Gentle Reminder for Final Discussion

comment:
Dear Reviewers,

With only two days remaining in the discussion period, we eagerly await your feedback. 

We have carefully addressed your concerns, and hope our responses have resolved any issues or questions. 

If you have any additional comments or concerns, please don't hesitate to let us know.

Sincerely,

Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper discusses RoSE, a framework aimed at enhancing Graph Neural Networks' performance on text-attributed graphs by using language models to decompose edges into meaningful semantic relations. The approach focuses on improving graph structure alongside node features, integrating advanced language processing for automated semantic edge decomposition, and implementing efficient sampling to reduce computational costs.

However, the work exhibits several critical weaknesses. The computational analysis lacks sufficient depth, particularly regarding cost evaluation and resource requirements for large-scale applications. The methodology faces significant challenges, including the need for substantial manual intervention in prompt adaptation and insufficient justification for assumptions about relation type similarity among neighboring nodes. The evaluation against available ground truth edge labels is limited, and the novelty is questionable given existing approaches in the field.

The paper demonstrates significant limitations that warrant rejection. While the approach shows potential, it primarily offers incremental improvements without substantial theoretical innovation. The practical constraints are particularly problematic, including computational overhead without clear benefits and resource demands that limit large-scale application viability. The framework's automation claims are undermined by the necessary manual effort in cross-domain prompt engineering. Technical foundations show weaknesses in sampling strategy assumptions, inconsistent performance improvements, and insufficient ground truth comparisons. The evaluation lacks comprehensive analysis of computational efficiency versus performance benefits, comparisons with simpler alternatives, and explanations for varying performance across different scenarios.