Bridging Semantics and Structure: A Theoretically Grounded Framework for Link Prediction on TAGs

Chen Shao; Ruirui Wang; Tobias Kafer; Danai Koutra

cs.AIOct 29, 2026

Bridging Semantics and Structure: A Theoretically Grounded Framework for Link Prediction on TAGs

Authors: Chen Shao, Ruirui Wang, Tobias Kafer, Danai Koutra

Organizations: Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany · University of Zurich, Zurich, Zurich, Switzerland · University of Michigan, Ann Arbor, Michigan, USA

Abstract

Link prediction on text-attributed graphs (TAGs) is a fundamental problem with applications in knowledge discovery, recommendation and beyond. Recent progress has highlighted the promise of combining Graph Neural Networks (GNNs) with Language Models (LMs) in order to leverage the complementary structural and semantic signals. However, due to the distinct inductive biases of GNNs and LMs, the design of an optimal fusion strategy remains an open research question. In this work, we present Bridge-LP, an intuitive, simple, efficient and theoretically grounded framework that unifies graph and language representations. It is built around three theoretically-justified design components: (D1) jumping connection of textual proximity, which enables robust LM training; (D2) compressed embedding, which encodes neighborhood information long exploited by classical link prediction heuristics, thereby enriching structural signals in a learnable way; and (D3) cache embedding training strategy, which reduces computational complexity. Together, these mechanisms establish an end-to-end cross-modal framework that scales to large graphs while capturing richer graph-text interactions. We conduct an extensive empirical evaluation, comparing against 40 existing models across 9 diverse datasets. Experiments show that Bridge-LP consistently outperforms state-of-the-art approaches, delivering up to a 43.06% improvement in Mean Reciprocal Rank (MRR) and setting a new benchmark for language-graph integration.

Figures & tables

Figure 1. Bridge-LP maintains accuracy (x-axis) while improving efficiency (y-axis) by 5% over our most competitive baseline on GNN4LP and PLM-based baselines. § Sec. 4

Figure 2. Overview of Bridge-LP . The framework consists of three graph signals: S1 Structural proximity from the graph structure (common neighbors, Eq. 1 ) ; S2 Semantic proximity from PLM text embeddings ; S3 Propagated proximity from GCNs; and the final step concatenates S1-3 through an MLP to perform link prediction.

Works	ZS		FT
Works	MLP	GCN	MLP	GCN
Graphformer ( Yang et al., 2021 )				✓
GAINT ( Chien et al., 2022 )	✓	✓
SimTeG ( Duan et al., 2023 )	✓	✓
TAPE ( He et al., 2024 )		✓
LEADING ( Xue et al., 2023 )		✓

Table 1. Comparison with existing methods. ✓ : public benchmark, ✓ : benchmarked model, Zero-Shot: ZS, Fine-Tune: FT

Figure 3. Ablation study of D1. Comparison of link prediction performance (AUC) with and without the proposed bypass connection. Across three benchmark datasets, the absence of D1 results in a performance degradation of 4%–6.8%, validating its role in facilitating effective gradient flow and preserving PLM semantic nuances.

Figure 4. Left: Overlapping rate between

\mathbf{H}_{C}

and

\mathbf{S}_{T}

; Right: AUC gap between models with and without compression. The results show that

\mathbf{H}_{C}

and

\mathbf{S}_{T}

are approximately compressive and that the framework equipped with D2 converges to a similar performance level as the non-compressed variant.

Panel of Figure 5 — Figure 5. (a) Sensitivity of Bridge-LP to the common-neighbor degree cutoff $\tau$ used in the TCN threshold, on Hits@50, MRR, and AUC. (b) Sensitivity of Bridge-LP to the structural-proximity mixing weight $\beta$ used in D2, on Hits@50, MRR, and AUC. Both sweeps are on Cora, averaged over five seeds; shaded bands show standard deviation.

Panel of Figure 6 — Figure 6. (a) The effect of graph encoder depth (number of GNN layers) on test AUC for Cora and PubMed datasets. The shaded areas represent the standard deviation, indicating the variance in performance across different trials. (b) The effect of LLM backbone choice on AUC for the Cora dataset. The figure shows three series: E5, BERT along with Sentence-Transformers.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Models	Cora		PubMed		Arxiv 2023
	Hits@100	AUC	Hits@100	AUC	Hits@100	AUC
RotatE	56.60 $\pm$ 6.29	61.57 $\pm$ 3.88	38.58 $\pm$ 2.59	80.89 $\pm$ 0.40	34.57 $\pm$ 0.84	76.73 $\pm$ 0.44
TransE	57.00 $\pm$ 7.06	64.19 $\pm$ 3.83	50.04 $\pm$ 2.63	85.29 $\pm$ 0.97	30.22 $\pm$ 1.96	73.03 $\pm$ 1.04
ComplEx	73.59 $\pm$ 0.90	75.71 $\pm$ 1.09	53.87 $\pm$ 3.09	89.60 $\pm$ 0.51	32.17 $\pm$ 2.38	73.31 $\pm$ 0.61
DistMult	73.12 $\pm$ 0.28	76.53 $\pm$ 0.80	54.82 $\pm$ 2.95	89.91 $\pm$ 0.53	32.37 $\pm$ 1.62	73.25 $\pm$ 0.39
BERT-Inf	56.90 $\pm$ 3.26	65.09 $\pm$ 1.41	48.73 $\pm$ 1.43	88.96 $\pm$ 0.31	48.74 $\pm$ 1.15	86.37 $\pm$ 0.27

Appendix

Table 9. Benchmark result of local and global heuristic, graph embedding, vanilla GCNs, GCN2LPs, LLM-Inf, LLM-FT.

Models	Cora		PubMed		Arxiv 2023
	Hits@50	MRR	Hits@50	MRR	Hits@50	MRR
MiniLM-GAT-CT	54.23 $\pm$ 4.08	13.74 $\pm$ 5.21	29.44 $\pm$ 2.84	4.26 $\pm$ 1.75	13.76 $\pm$ 2.22	2.62 $\pm$ 0.55
MiniLM-SAGE-CT	63.04 $\pm$ 9.23	15.09 $\pm$ 1.35	45.31 $\pm$ 3.83	6.70 $\pm$ 3.61	49.11 $\pm$ 4.22	11.48 $\pm$ 3.41
mpnet-GIN-CT	89.01 $\pm$ 5.54	29.06 $\pm$ 7.96	46.82 $\pm$ 4.22	11.86 $\pm$ 3.68	55.11 $\pm$ 3.70	18.88 $\pm$ 5.89
mpnet-GAT-CT	74.90 $\pm$ 9.22	23.16 $\pm$ 11.10	35.82 $\pm$ 3.81	5.36 $\pm$ 1.69	19.50 $\pm$ 1.91	4.49 $\pm$ 0.91
mpnet-SAGE-CT	82.01 $\pm$ 4.19	25.34 $\pm$ 8.06	57.58 $\pm$ 3.78	11.91 $\pm$ 3.58	52.97 $\pm$ 5.05	14.51 $\pm$ 3.37

Appendix

Table 10. Benchmark result of local and global heuristic, graph embedding, vanilla GCNs, GCN2LPs, ZO, FT.

Text-Attributed Graph Learning

Text-attributed graph learning combines node text and graph structure to improve classification, retrieval, anomaly detection, and reasoning.

See all 66 papers

TAG-DLM: Diffusion Language Models for Text-Attributed Graph Learning
Jun 30, 2026Lingjie Chen, Yuanchen Bei, Haobo Xu +3Masked Diffusion Models Link Prediction
UIUC · VISA
TaLK: Text-attributed Graph Dataset Distillation via Coupling Language Model with Graph-Aware Kernel
Jun 22, 2026Yeongho Kim, Yeonje Choi, Kijung ShinText-Attributed Graph Learning Dataset Distillation
Kim Jaechul Graduate School of AI, KAIST
PromptGNN-sim: Deep Fusion and Alignment of GNN and LLMs for Text-Attributed Graph Learning
Jun 29, 2026Zhifei Hu, Alexandra I. CristeaText-Attributed Graph Learning Multimodal Fusion
Durham University, Durham, United Kingdom

Jun 30, 2026J/K move · Enter open · S save

TAG-DLM: Diffusion Language Models for Text-Attributed Graph Learning

Lingjie Chen, Yuanchen Bei, Haobo Xu, Yanjun Zhao+2

UIUC · VISA

Masked Diffusion Models Link Prediction LLM Reasoning with Graphs Text-Attributed Graph Learning Diffusion Language Models Node Classification+1

Open paper AskPDF arXiv

Text-attributed graphs (TAGs), where each node carries a natural language description, require models to jointly reason over text and graph topology. Existing approaches often handle the two modalities separately: graph neural networks operate on shallow text features, while hybrids of LLMs and graphs use the language model mainly as a text encoder and delegate structure learning to a separate graph module. We propose method that unifies textual reasoning and graph message passing within a masked diffusion language model, a language model with bidirectional attention and generative decoding. For each graph instance, method linearises a sampled local neighbourhood into a token sequence and injects graph structure through a topology attention mask, which realises message passing over the graph. Because the diffusion language model can both interpret and generate text, the method adapts to different tasks simply by changing the prompt, supporting node classification, link prediction, and cross-dataset transfer with no target-specific fine-tuning. Experiments show that method outperforms graph neural networks, graph transformers, and LLM-based baselines on all three TAG benchmarks across two tasks, improving over the strongest baseline by up to 3.9 points.

Abstract

Text-Attributed Graph Learning

Explore similar work

TAG-DLM: Diffusion Language Models for Text-Attributed Graph Learning

TaLK: Text-attributed Graph Dataset Distillation via Coupling Language Model with Graph-Aware Kernel

PromptGNN-sim: Deep Fusion and Alignment of GNN and LLMs for Text-Attributed Graph Learning