PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphText: Graph Reasoning in Text Space

Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, Jian Tang

arXiv:2310.01089v1cs.CLcs.LG

TL;DR

LLMs struggle with graph machine learning because graph structure and features are difficult to express in natural language, while graph-specific GNNs may not generalize across graphs. GRAPHTEXT builds graph-syntax trees that translate attributes and relationships into text prompts for LLM reasoning, achieving performance on par with or surpassing supervised GNNs without graph-data training and enabling natural-language interaction.

  • Problem

    Graph structure and features are difficult to transform into natural language, and graph-specific GNNs may not generalize to unseen graphs.

  • Method

    GRAPHTEXT constructs graph-syntax trees containing node attributes and relationships, traverses them into text prompts, and uses an LLM for text-based graph reasoning.

  • Results

    GRAPHTEXT with ChatGPT delivers performance on par with or surpassing supervised graph neural networks through in-context learning without training on graph data.

  • Takeaways & Limitations

    GRAPHTEXT enables training-free, explainable, and interactive graph reasoning through natural-language interactions with humans and LLMs.

  • Takeaways & Limitations

    Open-source models show reduced performance on raw text inputs, which the paper attributes to limited parameter sizes and pre-training corpora.

Abstract

from arXiv · show

Large Language Models (LLMs) have gained the ability to assimilate human knowledge and facilitate natural language interactions with both humans and other LLMs. However, despite their impressive achievements, LLMs have not made significant advancements in the realm of graph machine learning. This limitation arises because graphs encapsulate distinct relational data, making it challenging to transform them into natural language that LLMs understand. In this paper, we bridge this gap with a novel framework, GraphText, that translates graphs into natural language. GraphText derives a graph-syntax tree for each graph that encapsulates both the node attributes and inter-node relationships. Traversal of the tree yields a graph text sequence, which is then processed by an LLM to treat graph tasks as text generation tasks. Notably, GraphText offers multiple advantages. It introduces training-free graph reasoning: even without training on graph data, GraphText with ChatGPT can achieve on par with, or even surpassing, the performance of supervised-trained graph neural networks through in-context learning (ICL). Furthermore, GraphText paves the way for interactive graph reasoning, allowing both humans and LLMs to communicate with the model seamlessly using natural language. These capabilities underscore the vast, yet-to-be-explored potential of LLMs in the domain of graph machine learning.

1 INTRODUCTION

GRAPHTEXT addresses the difficulty of applying LLM reasoning to graph data by translating graphs into natural-language prompts through graph-syntax trees. It supports training-free and interactive graph reasoning while achieving performance comparable to or better than supervised GNNs through in-context learning.

  • 1 INTRODUCTION: Graph-specific GNNs often require separate training for each graph and may not generalize to unseen structures or feature representations.The graph-language gap also limits the use of natural-language reasoning for graphs.
  • 1 INTRODUCTION: GRAPHTEXT builds a graph-syntax tree containing node attributes and relationships, whose traversal produces a natural-language graph prompt for LLM reasoning.The resulting graph reasoning process is treated as text generation.
  • 1 INTRODUCTION: GRAPHTEXT enables training-free graph reasoning with closed- or open-source LLMs, including ChatGPT performance on par with or surpassing supervised GNNs through in-context learning.This property allows graph reasoning without training on graph data.
  • 1 INTRODUCTION: GRAPHTEXT enables humans and other LLMs to interact with graph reasoning through natural-language prediction generation and explanation.The framework is presented as supporting interactive graph reasoning rather than only fixed graph prediction.

2 METHODOLOGY

GRAPHTEXT formulates graph reasoning as text-to-text prediction by mapping graph information into natural language and LLM outputs back to labels. Its graph-syntax trees organize textual attributes and relationships into hierarchical prompts that preserve graph structure and incorporate graph inductive biases.

  • 2.1 THE GRAPHTEXT FRAMEWORK: GRAPHTEXT maps graph inputs to text, applies a graph-shared LLM, and maps generated text back to graph-label predictions.This contrasts with graph-specific GNN functions and supports text-to-text graph reasoning.
  • 2.1 THE GRAPHTEXT FRAMEWORK: Graph-syntax trees bridge relational graphs and sequential language by producing traversable natural-language sentences for LLM processing.The tree addresses the mismatch between graph relational structure and text’s one-dimensional sequence.
  • 2.2 TEXTUAL AND RELATIONAL INFORMATION FOR SYNTAX TREES: GRAPHTEXT represents node information with textual attributes derived from text or discretized continuous features, such as K-means cluster indices.Attributes can include feature and label types, while continuous inputs are converted into discrete sequential data.
  • 2.2 TEXTUAL AND RELATIONAL INFORMATION FOR SYNTAX TREES: Relational information is encoded by matrices representing node-pair relationships, including original connectivity, high-order connectedness, PageRank, or other relations.These matrices determine the nodes and structure included in the graph-syntax tree.
  • 2.3 GRAPH-SYNTAX TREE COMPOSITION: For each target node, GRAPHTEXT constructs an ego-subgraph, selects relationship-based leaf nodes, and builds internal nodes and edges from attribute types and relationships.The resulting tree is ordered so its natural-language contents can be traversed as a sequence.
  • 2.3 GRAPH-SYNTAX TREE COMPOSITION: Graph-syntax trees preserve hierarchy and allow GNN inductive biases such as feature propagation and similarity-based aggregation to be encoded through attributes and relationships.Unlike direct graph flattening, the tree can be topologically sorted and provides a hierarchical structure for LLM reasoning.

3 RELATED WORK

Related work connects language and graph learning mainly through graph-specific architectures combining text encoders with GNN predictors. GRAPHTEXT instead uses a graph-syntax language to support graph-shared, training-free, interactive reasoning across graph types and learning settings.

  • Training-free Graph Reasoning: GNNs handle relational data through message passing and graph inductive biases encoded in structure-aware representations.These methods remain centered on graph-based modeling.
  • Unlock Graph Space for Language Models: GRAPHTEXT designs both textual and relational components of a graph-syntax tree to infuse graph inductive biases while reasoning in a graph-shared domain.The framework therefore targets broader applicability than graph-specific models.
  • Connecting Both Worlds: Many language-graph methods combine a text encoder with a GNN predictor, retaining a graph-specific paradigm.This differs from using one graph-shared LLM across diverse graphs.
  • Connecting Both Worlds: GRAPHTEXT supports in-context learning and instruction tuning for general and text-attributed graphs, while offering a flexible structured language for graph reasoning.Its graph-syntax representation distinguishes it from prior language-graph approaches.

4 EXPERIMENTS

GRAPHTEXT is evaluated for training-free, interactive, ablation, and text-attributed graph reasoning, using graph-syntax prompts with LLMs across multiple datasets and settings. Results show strong performance, interactive adaptation, and sensitivity to prompt structure, model type, and input modality.

  • 4.1 TRAINING-FREE GRAPH REASONING: The combination of synthetic text attributes and synthetic relations yields GRAPHTEXT’s highest accuracy on four of five datasets.Adding synthetic relations improves performance across all datasets, while synthetic text attributes help in most cases.
  • 4.1 TRAINING-FREE GRAPH REASONING: GRAPHTEXT surpasses several supervised GNN baselines without graph-data training, especially at low label rates and on heterophilic datasets.A single pre-trained ChatGPT model is used across datasets, whereas the GNN baselines are trained separately for each graph.
  • 4.2 INTERPRETABLE AND INTERACTIVE GRAPH REASONING: Natural-language graph reasoning lets GRAPHTEXT expose and adapt LLM reasoning through demonstrations or external feedback.The framework supports direct interaction by humans and LLMs while leveraging pre-trained knowledge for graph prediction.
  • 4.2 INTERPRETABLE AND INTERACTIVE GRAPH REASONING: GPT-4 reaches 73.3% accuracy versus ChatGPT’s 26.7% after demonstrations, while human interaction raises GPT-4 to 100% and improves ChatGPT by 36.9%.The interactive evaluation uses Cora node #2188 and shows that models can adjust prior inductive biases through demonstrations and feedback.
  • 4.3 ABLATION STUDIES ON GRAPH-SYNTAX TREES: GRAPHTEXT’s hierarchical graph-syntax tree consistently outperforms alternative designs, whereas sequence and set prompts cause large drops associated with label-counting behavior.Reversing the hierarchy also hurts performance, and removing internal nodes matters except on Texas, where attribute types are nearly identical.
  • 4.4 EXPERIMENTS ON TEXT-ATTRIBUTED GRAPH: With text-attributed graphs, instruction-tuned Llama-2-7B can surpass ChatGPT and approach GNN baselines, while ChatGPT performs poorly with continuous features.The paper attributes this contrast to open-source models’ ability to map continuous embeddings, whereas closed-source models are designed for raw discrete text.

5 CONCLUSION

GRAPHTEXT enables graph reasoning in text space by converting graph structure into natural-language prompts for LLMs. It supports training-free reasoning, interactive communication, and performance comparable to or exceeding supervised GNNs through in-context learning.

  • GRAPHTEXT converts graph reasoning into text generation by traversing a graph-syntax tree and feeding the resulting natural-language prompt to an LLM.
  • Training-free GRAPHTEXT can achieve performance on par with, or surpassing, supervised graph neural networks through in-context learning.
  • Natural-language graph reasoning enables humans and LLMs to interact with and explain graph-learning predictions.

ETHICS STATEMENT

GRAPHTEXT can reduce the computational load and carbon footprint of training many non-transferable graph-specific models. Its low-cost training-free capability also presents potential misuse risks in malicious recommendation systems and malware.

  • GRAPHTEXT may reduce the computational load and carbon footprint associated with training numerous non-transferable graph-specific models.
  • The training-free capability introduces potential misuse risks in malicious recommendation systems and malware.

A EXPERIMENTAL SETTINGS

The experiments frame node classification as multiple-choice question answering and convert available node information into textual attributes. Continuous features can additionally be projected into an LLM's input embedding space during instruction tuning.

  • Node classification is formulated as a multiple-choice question-answering task using prompts, raw text attributes, and textual labels.Nodes without data receive the value “NA,” so every general graph can be treated as a text-attributed graph with at least one text attribute.
  • During instruction tuning, an MLP projector maps continuous attributes into the input text space of the open-source LLM.

A.2 DATASETS

The experiments use citation networks, web-page networks, and text-attributed versions of citation datasets, with GRAPHTEXT parameter choices covering text attributes and graph relations. Dataset statistics and hyperparameters are documented in Tables 5 and 6.

  • Table 5 reports dataset statistics, while Table 6 reports GRAPHTEXT in-context-learning hyperparameters.
  • The datasets include citation networks, WebKB web-page networks, and Cora-TAG and Citeseer-TAG text-attributed graphs.
  • Citation-graph nodes represent computer-science papers, with citation edges, bag-of-words title features, and category labels.
  • WebKB nodes represent university web pages connected by hyperlinks and classified into student, project, course, staff, and faculty categories.
  • GRAPHTEXT selects text attributes and relations from propagated or raw features and labels, shortest-path distances, feature similarity, and PageRank-based relations.

B PROMPT EXAMPLES

The prompt examples show how GRAPHTEXT represents graph information as structured text for node classification, instruction tuning, and interactive reasoning. They also illustrate that tree design and selected graph information affect reasoning performance.

  • B.1 FEW-SHOT IN-CONTEXT LEARNING: Few-shot prompts define node-classification tasks with natural-language instructions, label choices, graph information, and an answer format for the LLM.The Citeseer example supplies demonstrations before asking the model to classify a paper topic.
  • B.1 FEW-SHOT IN-CONTEXT LEARNING: The Citeseer prompt represents graph information with a center node, feature-similarity neighbors, and PPR labels before eliciting answer C.The example combines these graph-derived labels into a serialized natural-language prompt.
  • B.2 INSTRUCTION TUNING: Instruction-tuning prompts encode node features and feature-similarity relations in XML-like graph text, with the target response expressed as a class label.The example uses an embedding for feature x generated by an MLP projector.
  • B.3 EXAMPLES OF TEXAS: Texas examples compare center-node and second-hop pseudo labels, showing cases where the target class matches the dominant graph-derived labels.The listed nodes include both uniform and mostly consistent second-hop label patterns.
  • B.3 EXAMPLES OF TEXAS: For the best Texas setting, removing text information does not hurt performance because center-node pseudo labels mostly assemble the second-hop neighbors.The result is tied to removing internal nodes from the graph-syntax tree.
  • B.3 EXAMPLES OF TEXAS: The Texas analysis attributes GRAPHTEXT’s gain over GCN and GAT to decoupling depth and scope in the graph-syntax tree.It also relates the observation to A2 as an important high-order aggregation scheme for Texas.
  • C INTERACTIVE GRAPH REASONING: GRAPHTEXT supports interactive graph reasoning by enabling self-interaction through zero-shot chain-of-thought and human guidance to refine reasoning.The section presents both AI self-interaction and direct human interaction as use cases.

C.1 ZERO-SHOT CHAIN OF THOUGHT REASONING

Zero-shot reasoning exposes how ChatGPT and GPT-4 use graph-derived labels differently when classifying a Cora paper. The examples also reveal failures caused by weak PPR recall and persistent center-node bias.

  • C.1 ZERO-SHOT CHAIN OF THOUGHT REASONING: The Cora example supplies center-node and PPR pseudo labels, demonstrations, and fixed answer choices as the input to zero-shot chain-of-thought reasoning.The prompt asks the model to classify the paper topic from graph-derived information.
  • C.1 ZERO-SHOT CHAIN OF THOUGHT REASONING: The examples state that PPR pseudo labels provide a more robust prediction mechanism than relying only on the center-node label.The paper describes either PPR majority voting or the foremost PPR label as effective in the examples.
  • C.1 ZERO-SHOT CHAIN OF THOUGHT REASONING: ChatGPT can reach the correct class by counting PPR labels, but it can instead follow the center-node label and produce an incorrect answer.The paired responses show both majority-label reasoning and center-node anchoring.
  • C.1 ZERO-SHOT CHAIN OF THOUGHT REASONING: GPT-4 can use PPR ordering to identify the correct class when the center-node label conflicts with the ranked PPR labels.The demonstrated reasoning treats the first PPR label as especially important.
  • C.1 ZERO-SHOT CHAIN OF THOUGHT REASONING: The section frames natural-language explanations as useful for identifying weaknesses in the models’ graph reasoning.The subsequent discussion uses those explanations to motivate further interaction with GRAPHTEXT.
  • C.1 ZERO-SHOT CHAIN OF THOUGHT REASONING: The reported failure modes include incomplete recall of graph priors and persistence in a pre-existing belief that the center node is most important.Only 26.7% of ChatGPT reasoning relies on PPR, and center-node bias is identified as a primary mistake source.

C.2 GRAPH REASONING WITH HUMAN INTERACTION

Human interaction helps GRAPHTEXT correct graph-reasoning biases by explicitly explaining PPR importance and asking the model to reassess competing labels. The reported gains are strongest for GPT-4, while ChatGPT remains occasionally inconsistent.

  • C.2 GRAPH REASONING WITH HUMAN INTERACTION: The interaction defines PPR labels as an importance-ranked sequence and asks the model to compare their reliability with the center-node pseudo label.The instruction makes the first PPR label the most crucial one for reassessment.
  • C.2 GRAPH REASONING WITH HUMAN INTERACTION: The section evaluates interaction through examples in which models reconsider their initial predictions after receiving the explicit PPR guidance.The examples are introduced as cases where reasoning is refined after interaction.
  • C.2 GRAPH REASONING WITH HUMAN INTERACTION: In the demonstrated correction, ChatGPT prioritizes A over G because A appears earlier in the PPR sequence and revises the answer to Theory.The revised response explicitly treats later PPR labels as less important.
  • C.2 GRAPH REASONING WITH HUMAN INTERACTION: After human feedback, GPT-4 reaches 100% accuracy by following the PPR logic, while ChatGPT improves accuracy by 36.9%.ChatGPT nevertheless sometimes refuses to update its prediction or becomes confused.
  • C.2 GRAPH REASONING WITH HUMAN INTERACTION: The human-guided procedure is presented as a way for both ChatGPT and GPT-4 to adjust pre-existing graph biases.The paper reports this adjustment across the examples and consolidated results.

D LIMITATIONS AND FUTURE WORK

The paper identifies unresolved limitations in feature discretization and graph-proxy-tree design, while outlining future uses of natural-language and training-free graph reasoning. These constraints leave substantial design choices for practitioners.

  • D LIMITATIONS AND FUTURE WORK: The discussion concludes that GRAPHTEXT offers notable advantages while retaining ample room for enhancement and new applications.The limitation framing accompanies the paper’s broader future-work agenda.
  • D LIMITATIONS AND FUTURE WORK: Continuous-feature discretization remains unresolved, and most optimal settings are label-based, making GRAPHTEXT resemble label propagation except on Citeseer.The paper attributes this trend to ineffective discretization or discord between feature and label spaces.
  • D LIMITATIONS AND FUTURE WORK: Constructing the text-attribute set, relation set, and their combinations creates a vast graph-proxy-tree search space that often requires expertise or hyperparameter optimization.Because the framework is training-free, the paper notes that hyperparameter optimization can nevertheless be swift.
  • D LIMITATIONS AND FUTURE WORK: GRAPHTEXT opens research directions for graph reasoning in natural language and for integrating advances in LLM reasoning, decision-making, tool use, and multi-agent collaboration.These directions are presented as applications enabled by the framework’s natural-language representation.
  • D LIMITATIONS AND FUTURE WORK: Training-free graph learning can streamline validation of graph-model designs by allowing researchers to identify suitable relation and feature settings before applying them to other GNNs or LLMs.This assumes that the optimal relation and feature sets transfer across models or settings.
Loading 2310.01089v1…