Verbalized Graph Representation Learning

Abstract

Representation learning on text-attributed graphs (TAGs) underpins applications from document classification to drug discovery, yet existing methods make a fundamental compromise: GNNs deliver strong structural reasoning but rely on opaque numerical parameters, while LLM-augmented variants provide only partial, post-hoc interpretability. We introduce Verbalized Graph Representation Learning (VGRL), a framework that constrains the entire parameter space to human-readable text, replacing stochastic gradient descent with prompt-based optimization and replacing numerical decoders with semantic label matching. The result is a graph learner whose input encoding, training updates, and final decisions are all expressed in natural language.

Motivation & Challenges

Conventional GNNs (GCN, GAT, GraphSAGE) update real-valued parameters via SGD, making the training trajectory a black box. Self-explainable GNNs and post-hoc explainers (e.g., GNNExplainer, SE-SGformer) only address isolated stages, producing fragmented explanations. We identify two challenges that any framework aiming for end-to-end interpretability must resolve:

Challenge 1 — Interpreting the training process. Numerical SGD updates make it impossible to trace, diagnose, or correct errors that arise from label noise or misclassification propagation.
Challenge 2 — Unifying interpretability across input, training, and decision-making. Existing approaches explain one stage in isolation, leading to inconsistent or non-actionable explanations.

Methodology

VGRL is a four-LLM pipeline in which all parameters θ live in the space of token sequences Θ_language. The framework is depicted in Algorithm 1 of the paper and operates as a Predictor / Optimizer / Summary / Enhancer cooperative loop:

Enhancer LLM — graph-to-text encoding. An ego-graph view of each target node is verbalized: the node's textual attributes are concatenated with a short summary of its k-hop neighbors' attributes and labels, yielding an enhanced textual embedding Z_{v_i}^k.
Predictor LLM — Label Feature Matching Mechanism (LFMM). Instead of softmax classification, an LLM directly compares Z_{v_i}^k against verbalized class descriptions {L_c^(t−1)}_c=1^C and emits both a predicted label and a natural-language explanation.
Optimizer LLM — verbalized parameter update. Using the predicted vs. true label, the optimizer LLM rewrites the textual class descriptions θ_t with explicit reasoning: it diagnoses misclassifications and rewrites the relevant class definitions, accepting any prior knowledge Ψ supplied through prompts.
Summary LLM — global consolidation. Mini-batch updates {θ̃_t^v_i} are merged into a coherent, deduplicated global θ_t, ensuring that training progress accumulates rather than oscillates.

Because every parameter update is a human-readable diff in θ, users can intervene mid-training — for instance, injecting a rule such as "papers discussing the Transformer architecture should be classified under Neural Networks" — without modifying mislabeled samples.

Key Results

We evaluate VGRL on the Cora text-attributed graph under three predictor backbones (Llama3.1-8B, DeepSeek-R1-Distill-Qwen-32B, DeepSeek-R1) and three input schemes (node-only, cited, summary). VGRL is benchmarked against direct LLM-as-predictor baselines and three classical GNNs (GCN, GAT, GraphSAGE), and stress-tested under aggressive edge removal.

01

Consistent Gains over LLM Baselines

On Cora with summary inputs, VGRL improves Llama3.1-8B from 73.62% → 75.54% and DeepSeek-R1-Distill-Qwen-32B from 80.17% → 81.59%, outperforming the direct LLM-as-predictor baseline in nearly all configurations.

02

Robust to Missing Edges

When all edges are removed, traditional GNNs collapse to ~19% accuracy, while DeepSeek-R1 + cited + VGRL still reaches 84.80% — showing that semantic label matching is largely insensitive to graph sparsity.

03

Ablation Confirms Both Optimizers

Removing the Optimizer LLM or the Summary LLM consistently degrades accuracy across all three backbones, validating that both the per-batch verbalized update and the global consolidation step are necessary.

04

End-to-End Interpretability

Every prediction is accompanied by a chain-of-thought explanation, every parameter update is a readable diff of class descriptions, and prior knowledge can be injected as plain text — a property no SGD-trained GNN currently offers.

Conclusion

VGRL reframes graph representation learning as a natural-language optimization problem, eliminating opaque numerical parameters in favor of textual ones that can be inspected, edited, and audited by humans. Beyond TAG node classification, the framework points toward a broader research direction in which the entire learning trajectory of a model — not just its outputs — is rendered transparent.

Source code is released anonymously at anonymous.4open.science/r/VGRL-DF46.

Citation

If you find this work useful, please cite:

@article{ji2024verbalized,
  title   = {Verbalized graph representation learning: A fully interpretable graph model based on large language models throughout the entire process},
  author  = {Ji, Xingyu and Liu, Jiale and Li, Lu and Wang, Maojun and Zhang, Zeyu},
  journal = {arXiv preprint arXiv:2410.01457},
  year    = {2024}
}