PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Chen Shao, Ruirui Wang, Tobias Kafer, Danai Koutra

arXiv:2610.40192v1cs.AI

TL;DR

Link prediction on text-attributed graphs raises the question of how to combine textual semantics and graph structure, while prior cross-modal approaches can be computationally expensive and do not always outperform GNNs. Bridge-LP combines three graph signals with theoretically justified design components; across 9 TAG datasets, it achieves state-of-the-art performance with up to 43.06% improvement in MRR.

  • Problem

    Combining language-model semantics and graph structure for link prediction remains challenging because existing cross-modal approaches can be expensive and do not necessarily outperform GNNs.

    Source: §1 · p. 2

  • Method

    Bridge-LP fuses structural, semantic, and propagated proximity through an MLP and uses three designs for robust training, compressed embeddings, and reduced training memory.

    Source: §1 · p. 3, §3.1 · p. 5, §3.2 · p. 6

  • Results

    Across 9 TAG datasets, Bridge-LP achieves state-of-the-art performance, with up to 43.06% improvement in MRR.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The authors report that the designs also serve as plug-in modules that consistently enhance existing GCN and PLM architectures.

    Source: §1 · p. 3

    Bridge-LP is designed for static TAGs; extending it to dynamic TAGs would require revisiting all three signals.

    Source: §5 · p. 19

Abstract

from arXiv · show

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.

1 Introduction

The introduction motivates combining textual semantics with graph structure for link prediction, noting that existing cross-modal methods can be costly and do not consistently outperform GNN approaches. It presents Bridge-LP as a three-signal framework with theoretically justified designs and reports state-of-the-art results across TAG datasets.

1 Introduction

  • Existing cross-modal methods can require expensive joint encoding of text pairs with deep LMs and GCNs, and do not necessarily outperform GNNs or strong link-prediction baselines.Reported inference costs range from seconds to hours, while some preliminary studies failed to outperform BUDDY and NCNC.Source: §1 · p. 2
  • Bridge-LP fuses structural, semantic, and propagated proximity signals through an MLP to predict link likelihood.Structural proximity captures local connectivity, semantic proximity encodes text or features, and propagated proximity reflects multi-hop information.Source: §1 · pp. 2–3, Figure 2 · p. 3
  • Its three designs target robust cross-modal training, compressed embeddings, and lower training-memory requirements, with theoretical justification for their joint use.The introduction also states that the designs can improve existing GCN and PLM architectures as plug-in modules.Source: §1 · p. 3
  • The framework is presented as an end-to-end, computationally efficient way to integrate graph and text modalities.The authors describe it as a plug-and-play alternative to GCNs that integrates with PLMs at no additional computational cost.Source: §1 · p. 3
  • Bridge-LP achieves state-of-the-art performance across 9 TAG datasets, with up to 43.06% improvement in MRR.The evaluation compares it against over 40 baselines under consistent experimental settings.Source: §1 · p. 3

2 Related Work

Related work spans shallow and PLM-based text encoders, multiple strategies for combining language models with graph networks, and methods for modeling link-specific structure. Bridge-LP is positioned as a static-TAG framework addressing the efficiency and performance challenges of cross-modal fusion.

2 Related Work

  • The reviewed text encoders range from shallow statistical representations to PLMs that generate sentence-level node embeddings.The section describes PLMs as capturing higher-order semantics and using objectives such as contrastive fine-tuning or domain-adaptive pretraining.Source: §2 · p. 4
  • PLM-based TAG methods use zero-shot embeddings, task-specific fine-tuning, or instruction tuning, while another line injects graph structure at the tokenizer level.The section notes a prior observation that naive iterative LLM-GCN combinations may fail to yield meaningful performance gains.Source: §2 · p. 4
  • Bridge-LP targets static TAGs and is positioned as a theoretically unified, computationally efficient alternative for combining PLM semantics with multi-level structural signals.The related-work discussion distinguishes dynamic TAG methods, where node text and graph structure evolve over time.Source: §2 · p. 4
  • Pair-specific methods such as SEAL and NBFNet model information for target links but incur high training costs by constructing and featurizing a subgraph for each link.Other methods decouple message passing from pairwise modeling; examples include NCNC, BUDDY, HL-GNN, and Neo-GNN.Source: §2 · p. 4

3 Bridge-LP: A New Efficient, Simple and Theoretically Justified Model

Bridge-LP combines structural, textual, and multi-hop propagated signals in a lightweight architecture, with three design mechanisms intended to improve cross-modal training and efficiency.

3.1 Data Signals in Bridge-LP

  • Bridge-LP fuses structural, semantic, and propagated proximity as proxies for latent relationships, with propagated proximity capturing similarity diffusion across multi-hop connections.The latent-space motivation connects common neighbors and feature similarity to latent distance; propagated proximity is especially useful when structure exhibits homophily.Source: §3.1 · pp. 5–6
  • Structural proximity uses thresholded common neighbors, retaining stronger connections while removing noisy edges and hub bias from shared global hubs.The threshold is applied to a binary indicator of common neighbors.Source: §3.1 · p. 5
  • Semantic proximity scores node pairs from pretrained language-model text features, using learned weights to emphasize semantic dimensions predictive of latent relationships.The learned formulation is contrasted with fixed measures such as cosine similarity.Source: §3.1 · pp. 5–6
  • Propagated proximity extends beyond pairwise or local signals by diffusing node features over K steps with symmetrically normalized adjacency and self-loops.The final GCN embedding is H^K.Source: §3.1 · p. 6

3.2 Bridge-LP: Efficient Iterative Architecture

  • The lightweight iterative architecture computes the three signals independently and fuses them only at the final stage, avoiding expensive intermediate interactions.The framework uses simple linear transformations and component-wise nonlinearities rather than heavy fusion mechanisms.Source: §3.2 · p. 6
  • D1 adds a direct textual bypass that preserves PLM information and gradient flow, enabling more robust and efficient PLM optimization.The paper’s influence analysis says D1 strengthens the sensitivity of the link-likelihood objective to PLM parameters.Source: §3.2 · p. 7

PLM-direct (self) path

The PLM-direct self path has a strict influence increase when its bypass is nonzero and does not cancel the existing self-path.

PLM-direct (self) path

  • A nonzero bypass matrix strictly increases the influence score when it does not cancel the existing self-path.The bypass matrix B is trainable.Source: PLM-direct (self) path · p. 7

Appendix A.

Appendix A evaluates the three designs and explains their mechanisms and computational trade-offs. Its experiments support D1’s AUC gains and show that D2’s compression approaches the non-compressed model’s performance as overlap declines.

Appendix A.

  • D1 raises AUC by up to 6% on Cora, 4% on Pubmed, and 6.8% on Arxiv_2023, consistent with its gradient-flow rationale.The ablation compares Bridge-LP with and without D1 across three benchmark datasets.Source: Appendix A · p. 7, Figure 3 · p. 8
  • D2 replaces concatenation with addition, reducing hidden dimension from d=|H^K|+|T|+|V| to d=|H^K| based on low structural-semantic overlap.Under the stated latent-space model, structural and semantic proximity are complementary link-formation mechanisms, allowing compact representation with negligible information loss.Source: §3.2.2 · p. 8
  • As |V_s| grows, overlap decays approximately linearly and the D2 AUC gap converges toward zero, indicating similar predictive performance with reduced complexity.The overlap rate measures overlap between non-zero elements; the AUC gap is AUC(M with D2) − AUC(M without D2).Source: §3.2.2 · p. 9, Figure 4 · p. 9
  • D3 re-encodes only minibatch endpoint nodes and uses cached features for others, reducing per-batch encoding cost from O(|V||T|d) to O(b|T|d).The cache error depends on parameter drift since a node’s last refresh; it stays controlled when updates shrink or the cache is periodically refreshed.Source: §3.2.3 · pp. 9–10, Appendix C · p. 10

Appendix C),

  • With bounded step size and periodic refresh, cache error is uniformly bounded and vanishes as training converges when updates are summable and nodes continue to be refreshed.The discrepancy is governed by cache staleness rather than node coverage alone.Source: Appendix C · p. 10

3.3 Time Complexity of Bridge-LP

  • Quadratic attention dominates for long token sequences, whereas graph message passing dominates for dense graphs.The complexity analysis includes Transformer attention and feed-forward computation, graph message passing, activation storage, and attention-matrix storage.Source: §3.3 · p. 10

4 Empirical Evaluation

The empirical evaluation compares Bridge-LP with GCN- and PLM-based link predictors on standard and larger text-attributed graphs, and examines graph signals, design components, efficiency, robustness, and LLM backbone choices through ablations.

4.1.2 Results.

  • Bridge-LP improves on Arxiv_2023 by up to 5.72% in Hits@100, Pubmed by 4.75% in Hits@50 over GIN, and Cora by 9.57% in MRR over PageRank.It surpasses eight different state-of-the-art approaches across nine comparative experiments.Source: Table 3 · p. 12, §4.1.2 · p. 12

4.2.2 Results.

  • On Cora, Bridge-LP beats MiniLM-NCNC by up to 43.06% in MRR, while Mpnet-Bridge-LP exceeds ZS-GCN by up to 2% on Hits@K.Fine-tuned BERT-MLP reaches 54.17% on Cora, while combining PLMs with GCNs does not yield stable or significant gains over FT-MLP.Source: Table 4 · p. 13, §4.2.2 · pp. 13–14
  • Scaling the zero-shot MLP text encoder advances its average rank from 17th to seventh, with the trend consistent within E5, BERT, and Sentence-Transformer families.The compared scale range includes BERT embeddings and larger decoder-only models such as LLaMA-3-8B.Source: §4.2.2 · p. 14

4.3.2 Results.

  • Bridge-LP achieves at least 4.72% improvement, reaches 89.36% test accuracy, exceeds 99% accuracy on large-scale graphs, and ranks first on average across datasets.The large-scale evaluation uses AUC and compares Bridge-LP with the strongest baselines in each category; results are averaged over five random splits.Source: §4.3.2 · pp. 14–15, §4.3.1 · p. 14, Table 5 · p. 15

4.4.1 Impact of the Graph Signals.

  • Removing S1 lowers AUC to 75.27% on Cora and 67.39% on Pubmed, while removing S2 lowers MRR to 39.17% on Cora and 14.12% on Pubmed.S1 is the thresholded common-neighbor signal, and S2 is semantic proximity from PLM text embeddings.Source: §4.4.1 · pp. 15–16, Table 6 · p. 16
  • Removing S3 drops Cora Hits@50 to 88.14% and MRR to 38.53%; including S3 improves every Hits@50, MRR, and AUC cell across datasets.The observed GCN effect is less visible on low-clustering Pubmed, though its MRR still declines by 3.2% when S3 is removed.Source: Table 6 · p. 16, §4.4.1 · p. 17
  • On Cora, Hits@50 stays within 1.1 points across τ and β sweeps, while AUC varies by at most 0.16 and 0.13 points, respectively.The main experiments use τ=2 and β=0.1; MRR is more sensitive, varying by up to 10.5 points across τ and 7.8 across β.Source: Figure 5 · p. 16, §4.4.1 · pp. 16–17

4.4.2 Impact of the Design Components (D1–D3).

  • D1 improves AUC on Cora and Pubmed, but its Hits@50 and MRR effects vary by metric and dataset; D3 is designed to reduce memory use and training cost while maintaining competitive performance.With D1, AUC changes from 84.96% to 91.90% on Cora and 93.08% to 95.32% on Pubmed; Hits@50 changes from 72.64% to 78.05% and 42.99% to 42.85%, respectively. MRR changes from 21.28% to 21.25% on Cora and from 8.02% to 11.46% on Pubmed.Source: §4.4.2 · pp. 17–18, Table 8 · p. 18
  • Hits@50 rises from 72.64% to 92.13% on Cora and from 42.99% to 76.23% on PubMed with compressed embeddings (D2).MRR likewise rises from 21.28% to 50.00% on Cora and from 8.02% to 25.75% on PubMed; the thresholded common-neighbor indicator maps pairs with no shared neighbors to zero, reducing uninformative features.Source: §4.4.2 · p. 18
  • The cache-embedding strategy (D3) makes the full model approximately 3.7× faster on both Cora and PubMed without generally compromising predictive performance.Per-epoch time falls from 17.4 to 4.7 seconds on Cora and 139.2 to 37.6 seconds on PubMed; total memory falls by 56.1% and 53.9%, respectively, though PubMed Hits@50 degrades slightly.Source: §4.4.2 · p. 18

4.4.3 Effect of GCN layers.

  • Test AUC fluctuates only slightly across 1–5 GCN layers, remaining around 98% on PubMed, indicating robustness to moderate depth changes.The figure reports test AUC for Cora and PubMed, with shaded regions showing standard deviation across trials.Source: §4.4.3 · p. 18, Figure 6 · p. 19

4.4.4 Impact of the LLM Choices and Scale.

  • Larger models within the E5, BERT, and Sentence-Bert series consistently improve performance, while backbone rankings vary by metric.Mpnet-based models generally yield higher MRR, whereas MiniLM and E5-large variants show stronger Hits@K stability; the passage reports mpnet performance as comparable to E5-large. The figure presents AUC for Cora.Source: §4.4.4 · p. 19, Figure 6 · p. 19

5 Conclusion

  • Up to 20% improvement in MRR is reported against 40 existing link-prediction models across 9 diverse TAG datasets.The evaluated datasets range from small academic networks to billion-scale graphs. Bridge-LP is designed for static TAGs; dynamic TAG support and evaluation are left to future work.Source: §5 · pp. 19–20

A Proof of Thm. 3.2

  • Design D1 leaves off-diagonal unnormalized influence unchanged and makes unnormalized influence non-decreasing, with a possible strict increase on the self term.Under normalized influence, however, the self (PLM-direct) influence decreases; the proposition’s claim concerns unnormalized influence.Source: A Proof of Thm. 3.2 · p. 25

B Proof of Thm. 3.3

The proof analyzes additive compression by bounding the distortion between summed and concatenated structural and semantic representations. When their overlap is small, the resulting AUC gap is also small.

B Proof of Thm. 3.3

  • The proof bounds the distortion from replacing concatenation [H_C; S_T] with addition H_C+S_T through the overlap between the two signals.The bound follows from the cross terms in the inner product of summed representations.Source: B Proof of Thm. 3.3 · p. 25
  • When structural and semantic signals have disjoint coordinate support, summation preserves the Gram matrices exactly and is lossless for inner-product- or distance-based link prediction.More generally, the distortion is controlled by cross-signal overlap, which the analysis finds small in practice.Source: B Proof of Thm. 3.3 · p. 25
  • As the number of nodes |V_s| grows, the supports’ overlap rate decays toward zero and the AUC gap between additive and concatenated variants vanishes accordingly.The observed complementarity is consistent with structural and semantic proximity acting as distinct link-formation mechanisms.Source: B Proof of Thm. 3.3 · p. 25

C Proof of Thm. 3.4

The proof bounds the cache-induced error in gradients for GCN and predictor parameters under encoder Lipschitzness and a smooth feature-to-gradient map. The bound depends on parameter drift since each node’s last cache refresh.

C Proof of Thm. 3.4

  • The proof assumes a fixed graph, a PLM encoder Lipschitz in its parameters, and a uniformly Lipschitz feature-to-gradient map for the GCN loss.The latter smoothness assumption can follow from Lipschitz loss and gradient composed with the GCN, but its constant is assumed rather than derived.Source: C Proof of Thm. 3.4 · p. 26
  • The bound concerns GCN/predictor parameters ϕ: freshly re-encoded endpoints are exact, so error arises only from stale non-endpoint feature rows.The approximation to the PLM gradient from caching non-endpoint features is explicitly outside the bound’s scope.Source: C Proof of Thm. 3.4 · p. 26
  • The cache-gradient error is controlled by parameter drift since each node’s last refresh, not by node coverage alone.It is uniformly bounded with bounded updates and periodic refresh, and vanishes under summable updates if every node is refreshed infinitely often.Source: C Proof of Thm. 3.4 · p. 26

D Complexity Analysis: Details

The complexity analysis separates Transformer-based language-model cost from sparse GNN propagation cost, then gives their combined order.

D Complexity Analysis: Details

  • Transformer-based LLM time complexity is O(l(|T|d^2 + |T|^2d)), where |T| is token length, d is token hidden dimension, and l is the number of Transformer layers.Source: D Complexity Analysis: Details · p. 26
  • The overall complexity is O(d^2|T| + d|T|^2 + d|E|), combining language-model and graph propagation costs.The GNN component is O(d|E|) for a sparse adjacency matrix.Source: D Complexity Analysis: Details · p. 27

E Hardware Specification

The experiments use a single A100 GPU, and the implementation is reported to fit all proposed datasets within its 40 GB of VRAM.

E Hardware Specification

F.1 LLM Fine-Tune details

  • Training is reported to fit all proposed datasets on a single A100 GPU with 40 GB VRAM, using full parameter fine-tuning and specified frozen encoder layers.The frozen layers extend through layer 6 in MiniLM, 32 in Llama3, 12 in BERT, and 23 in e5-large.Source: §F.1 · p. 27

F.2 GCN Fine-Tune Details

The appendix specifies tuning protocols for graph baselines and language-model variants, then gives Bridge-LP’s fixed architecture and limited tuning choices.

F.2 GCN Fine-Tune Details

  • Because tuning the full search space is not feasible for larger datasets, the study uses, for each parameter, the average optimized value from the smaller graphs Cora, Pubmed, and Arxiv_2023.Source: §F.2 · p. 27
  • The GCN baseline search covers learning rate, batch size, dropout, weight decay, layer counts, and hidden and output dimensions.Training uses a full adjacency matrix while removing the target link.Source: §F.2 · p. 27

F.3 LLM Fine-Tune Details

  • MiniLM, e5-large, and MPNet use frozen initial encoder layers, 768-dimensional features, and 250-epoch training, with model-specific batch sizes and stopping settings.ZO-MLP embeds text without training; FT-MLP adds an MLP, ZO-GCN separately embeds text and aggregates it with GCNs, and FT-GCN fine-tunes both stages.Source: §F.3 · p. 28
  • Bridge-LP reuses the stated MPNet, MiniLM, and e5-large fine-tuning settings and fixes the common-neighbor threshold at 2 and its mixing weight at 0.1 across datasets.Its GCN uses 1,433 input, 256 hidden, and 32 output channels, with one MLP layer and three graph-convolution layers; only optimizer learning rate, batch size, and weight decay are tuned.Source: §F.3 · p. 28

G Benchmark Result of all Models

The appendix presents benchmark tables by model family, a four-step link-prediction pipeline, and statistics describing graph structure and text attributes.

G Benchmark Result of all Models

  • Tables 9 and 10 organize benchmark results across heuristic, graph, GCN, language-model, zero-shot, and fine-tuned model categories, but the supplied captions report no outcome values.The captions distinguish local/global heuristics, graph embeddings, vanilla GCNs, GCN2LPs, LLM-Inf, LLM-FT, ZO, and FT.Source: Table 9 · p. 29, Table 10 · p. 30

H Pseudocode & Pipeline

  • The pipeline takes adjacency, node features and text, edge labels, training edges, and model parameters, then computes semantic, propagated, and structural proximity before binary classification.The pseudocode associates text embedding with semantic proximity, neighborhood aggregation with propagated proximity, and common-neighbor computation with structural proximity.Source: H Pseudocode & Pipeline · p. 31

I.1 Structure Statistics

  • The structure-statistics overview includes graph size and density, local connectivity, clustering and transitivity, and hierarchical measures based on k-core fractions, Gini, and coreness.Average degree is used to describe local connectivity, including the average degree in a central node’s second-order neighborhood.Source: §I.1 · pp. 31–32
  • The appendix characterizes scale-free structure through a power-law degree distribution and reports text-length and data-volume statistics for the benchmark datasets.It identifies PWC small, Cora, PubMed, Arxiv_2023, and PWC large as scale-free; Table 11 covers text-length ranges and textual data-point counts.Source: §I.1 · pp. 31–32, Table 11 · p. 32

I.2 Detailed Information about Datasets

The evaluation uses nine link-prediction datasets from Planetoid, Amazon, OGB, and other sources, spanning citation, shopping, research-artifact, and recommendation graphs.

I.2 Detailed Information about Datasets

  • The nine-dataset collection draws on Planetoid, Amazon, and OGB, with PWC small, PWC medium, and History listed outside those groups.The named datasets include Cora, PubMed, Photo, ogbn-arxiv, CitationV8, Arxiv_2023, PWC small, PWC medium, and History.Source: §I.2 · pp. 32–33
  • Cora and PubMed are publication citation graphs with word-vector features, while Photo links co-purchased products represented by 745-dimensional attributes.Cora has 2,708 publications and 5,429 links; PubMed has 19,717 publications and 44,338 links.Source: §I.2 · p. 33
  • The other citation datasets include ogbn-arxiv, Arxiv_2023 papers published from 2023 onward, and CitationV8, whose node text comes from paper titles and abstracts.ogbn-arxiv nodes have 128-dimensional features derived from title and annotation word embeddings; CitationV8 is extracted from DBLP.Source: §I.2 · p. 33
  • PWC medium uses paper titles and abstracts as node features, PWC small is a connected component extracted from it, and History models book-review preferences using book and user descriptions.History nodes represent book and reviewer metadata, with labels assigned by book category.Source: §I.2 · p. 33

Related papers

Loading 2610.40192v1…