Skip to content

Bridging Text and Structure via Latent Query Refinement for Knowledge Graph Completion

Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Reasoning
Keywords: Knowledge Graph Completion, Latent Query Refinement, Pretrained Language Models, Graph Neural Networks, Pseudo-edge Augmentation

TL;DR

LQ-KGC establishes an EM-inspired alternating refinement framework between a dual-encoder language model and a relation-aware GNN over a semantically compatible, degree-balanced latent query set, enabling mutual reinforcement via pseudo-edge message passing and structural soft-label distillation.

Background & Motivation

Knowledge graphs (KGs) encode structured human knowledge as collections of factual triples \((h, r, t)\), forming the cornerstone for numerous knowledge-intensive systems including conversational question answering, factual information retrieval, precision recommendation, and domain-specific LLM reasoning. Nonetheless, realistic KGs suffer from substantial incompleteness where a vast fraction of true relational facts remain unobserved, necessitating the task of knowledge graph completion (KGC). State-of-the-art KGC methodologies traditionally bifurcate into two distinct schools: structure-based methods (such as translational models TransE/RotatE and relational graph neural networks like CompGCN) learn entity and relation embeddings strictly from observed graph topology and local neighborhoods, excelling at capturing structural connectivity but faltering severely on low-degree sparse entities and long-tail relations; on the other hand, text-based methods (e.g., SimKGC, GHN) exploit rich natural language descriptions of entities and relations via pretrained bi-encoder language models, offering strong semantic generalization to rare entities while completely overlooking global graph topology and relational pathways.

While textual semantics and graph structure provide inherently complementary inductive biases, existing hybrid frameworks couple the two modalities in a predominantly static or unidirectional fashion. Typical joint-objective methods (such as KEPLER and StAR) align text and KG embeddings via fixed training objectives or score-level fusion, and parameter-efficient prompt/adapter pipelines (such as CSProm-KG and KoPA) feed shallow structural hints into language models without feedback loops. Consequently, high-confidence semantic predictions derived from language models are rarely incorporated into graph reasoning as structural context, while global topological constraints from GNNs fail to dynamically regularize the dense ranking distributions of language models. Directly treating all missing relational triples as latent variables under a standard Expectation-Maximization (EM) formulation would cause severe combinatorial explosion and drown optimization in uncontrolled pseudo-label noise across the skewed unobserved space.

To resolve this bidirectional disconnect without incurring noise collapse, this paper introduces LQ-KGC, an alternating latent-query refinement framework that operates over a restricted, semantically verified, and distributionally balanced query set. By restricting latent queries to those supported by semantic cluster priors and balancing them against node degree and relation frequency, the framework establishes a stable two-way exchange: the language model predicts candidate tail distributions from textual descriptions and contributes high-confidence completions as typed pseudo-edges to enrich graph message passing, while the structure model provides soft probability distributions that supervise and regularize the language model. Core idea: Restricting latent variable inference to a type-aware and degree-balanced query set enables an EM-inspired alternating refinement loop where text-derived pseudo edges augment graph message passing and graph-induced soft distributions regularize semantic ranking.

Method

Overall Architecture

LQ-KGC addresses the fundamental trade-off between local semantic matching and global structural inference in knowledge graph completion. The architecture integrates two pretrained backbones: a bi-encoder language model \(q_\phi\) (based on SimKGC) acting as the variational semantic branch, and a multi-relational GNN \(p_\theta\) (CompGCN with a ConvE score decoder) acting as the pseudo-likelihood structural branch. Inspired by the EM principle, the model alternates between semantic refinement (E-step) and structural refinement (M-step) over a bounded latent query set \(\mathcal{Q}\).

The end-to-end pipeline consists of four major stages: First, a type-aware, frequency- and degree-balanced latent query set \(\mathcal{Q}\) is constructed from LM entity representations and observed training priors. Second, in the E-step, the graph model is frozen and provides soft structural teacher distributions via KL divergence to regularize the LM's contrastive ranking distribution on \(\mathcal{Q}\). Third, in the M-step, the LM is frozen and its top-1 confident completions over \(\mathcal{Q}\) are filtered and inserted as typed pseudo-edges into the graph, over which CompGCN executes message passing and is optimized via binary cross-entropy. Finally, at test time, normalized semantic and structural scores are combined via adaptive convex fusion to produce the final filtered entity ranking.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input: Observed KG Triples and Entity/Relation Text Descriptions"] --> B["Type-Aware Balanced Latent Query Construction<br/>Cluster-prior compatibility filtering + degree/frequency reweighting"]
    B --> C["Structure-Supervised Semantic Refinement (E-step)<br/>Bi-encoder contrastive learning + GNN soft distribution KL distillation"]
    C --> D["Pseudo-Edge Augmented Relation-Aware Graph Reasoning (M-step)<br/>LM pseudo edges enrich KG topology + CompGCN message passing & BCE"]
    D --> E["Dual-Perspective Normalized Predictor Fusion<br/>Convex combination of normalized LM and GNN score distributions"]
    E --> F["Output: Final Filtered Candidate Entity Ranking"]
    C -.->|High-confidence filtered pseudo triples| D
    D -.->|Temperature-normalized logits as soft teacher| C

Key Designs

1. Type-Aware Balanced Latent Query Construction: Taming Combinatorial Space and Pseudo-Label Noise

Treating the entire complement of unobserved entity-relation pairs as missing variables is intractable and introduces rampant noise, as real-world graphs exhibit acute degree skewness and relations possess strict semantic domain constraints. To generate an effective, high-precision query set \(\mathcal{Q}\), this design applies two complementary criteria. The first is semantic plausibility: entity embeddings from the pretrained LM are \(L_2\)-normalized and grouped into coarse semantic regions via agglomerative clustering (for WN18RR) or K-Means (for FB15k-237); an empirical prior over these regions is computed from observed training triples for every relation \(r\), and candidate pairs \((h, r)\) are retained only if the head entity's semantic cluster falls within the admissible support of \(r\). The second is distributional balancing: candidate queries are reweighted inversely by relation frequency and head-entity degree, and allocated into multi-dimensional buckets indexed by relation and entity clusters. Strict caps are enforced—limiting each entity to at most 2 queries, restricting any single relation to no more than 5% of the total budget, and capping individual buckets at 200 items. Budgeted at 10% of training triples on WN18RR and 4.45% on FB15k-237, \(\mathcal{Q}\) provides a structurally sound and noise-resilient support for alternating refinement.

2. Structure-Supervised Semantic Refinement (E-step): Alleviating Semantic Overfitting via Topological Regularization

Standard bi-encoder language models for KGC encode the query text \((h, r)\) and entity description \(t\) independently, which can easily overfit to shallow lexical overlaps and surface synonymy while remaining oblivious to multi-hop relational path invariants. In the E-step, the graph model \(p_\theta\) is frozen and serves as a structural teacher. The LM parameterizes a variational distribution over candidates \(\mathcal{C}_q\): $\(q_\phi(z_q = t \mid q, \mathcal{D}) = \frac{\exp(s_\phi(h, r, t)/\tau)}{\sum_{t' \in \mathcal{C}_q} \exp(s_\phi(h, r, t')/\tau)}\)$ where \(s_\phi(h, r, t) = \text{sim}_\phi(h, r, t; \mathcal{D})\) denotes the dual-encoder cosine matching score. In addition to the supervised contrastive loss \(\mathcal{L}_q^{sup}\) on observed batches, the LM minimizes the Kullback-Leibler (KL) divergence against the temperature-scaled GNN prediction distribution \(\tilde{p}_\theta(\cdot \mid q_i, \mathcal{G}_{obs})\) over the latent queries in \(\mathcal{Q}\): $\(\mathcal{L}_q^{dist} = \frac{1}{|\mathcal{Q}|} \sum_{q_i \in \mathcal{Q}} \mathrm{KL}\Big(\tilde{p}_\theta(\cdot \mid q_i, \mathcal{G}_{obs}) \;\parallel\; q_\phi(\cdot \mid q_i, \mathcal{D})\Big)\)$ This structural supervision pulls semantic representations toward topologically coherent candidate subsets, sharpening top-ranked predictions without eroding textual discriminability.

3. Pseudo-Edge Augmented Relation-Aware Graph Reasoning (M-step): Relieving Structural Sparsity in GNNs

Relational GNNs like CompGCN fail dramatically when head entities have few or no incoming/outgoing edges, as message passing cannot propagate informative representations across disconnected subgraphs. In the M-step, the language model \(q_\phi\) is frozen, and its rich entity representations are mapped through a lightweight MLP adapter \(\mathrm{MLP}_\psi\) to initialize GNN node features \(x_e = \mathrm{MLP}_\psi(v_e^{LM})\), providing semantic cold-start grounding. Next, for each latent query \(q = (h, r) \in \mathcal{Q}\), the LM infers its top-1 tail candidate \(\tilde{z}_{h,r}^q\). Predictions already observed are discarded, candidates with confidence under 0.05 are pruned, and the top 90% most confident predictions are retained to form typed pseudo-edges: $\(\mathcal{G}_{aug} = \mathcal{G}_{obs} \cup \{(h, r, \tilde{z}_{h,r}^q) \mid (h, r) \in \mathcal{Q}\}\)$ CompGCN executes multi-layer compositional message passing directly over \(\mathcal{G}_{aug}\), aggregating information across both observed and semantically inferred bridges, before computing ConvE tail logits evaluated against observed and pseudo multi-hot targets. This injects fresh topological highways for low-degree nodes.

4. Dual-Perspective Normalized Predictor Fusion: Bridging Complementary Inductive Biases at Test Time

After alternating refinement, both branches retain their distinct strengths: the LM branch excels at fine-grained textual semantic discrimination, while the GNN branch excels at relational pattern deduction and multi-relational path consistency. To leverage both without complex re-ranking overhead, LQ-KGC employs score-normalized convex fusion. For any test query \((h, r, ?)\), the raw semantic score vector \(s_\phi^{LM}(h, r) = [u_{h,r}^\top v_t]_{t \in \mathcal{E}}\) and the graph score vector \(s_\theta^{GNN}(h, r) = [\mathrm{ConvE}_\theta(h_h^{(K)}, h_r^{(K)}, h_t^{(K)})]_{t \in \mathcal{E}}\) are mapped onto comparable scales using min-max normalization \(\mathcal{N}(\cdot)\), and blended via: $\(s(h, r, t) = (1 - \lambda)\mathcal{N}(s_\phi^{LM}(h, r, t)) + \lambda\mathcal{N}(s_\theta^{GNN}(h, r, t))\)$ The balance factor \(\lambda \in [0, 1]\) is tuned on validation splits (e.g., \(\lambda = 0.1\) for text-dominant WN18RR, and \(\lambda = 0.5\) for structure-dense FB15k-237), ensuring flexible adaptation across diverse graph topologies.

Loss & Training

The training workflow comprises independent pretraining followed by alternating latent-query refinement. LM pretraining runs for 50 epochs on WN18RR (10 on FB15k-237) under contrastive loss, while CompGCN pretraining runs for 500 epochs.

During the alternating stage: 1. Semantic Refinement (E-step) Objective: $\(\mathcal{L}_q^E = \lambda_q^{sup}\mathcal{L}_q^{sup} + \lambda_q^{dist}\mathcal{L}_q^{dist}\)$ with \(\lambda_q^{sup} = 1.0\) and \(\lambda_q^{dist} = 0.2\). Each round executes 1 semantic update and 1 distillation step. 2. Structural Refinement (M-step) Objective: Using binary cross-entropy (BCE) over multi-hot ground truth \(y_{h,r}\) and pseudo label vectors \(\tilde{y}_{h,r}\): $\(\mathcal{L}_p^M = \lambda_p^{sup} \sum_{(h,r) \in \mathcal{T}_{tr}} \sum_{e \in \mathcal{E}} \mathrm{BCE}\big(y_{h,r}[e], \sigma(s_\theta(h, r, e))\big) + \lambda_p^{PL} \sum_{(h,r) \in \mathcal{Q}} \sum_{e \in \mathcal{E}} \mathrm{BCE}\big(\tilde{y}_{h,r}[e], \sigma(s_\theta(h, r, e))\big)\)$ On WN18RR, \(\lambda_p^{sup} = 0.6, \lambda_p^{PL} = 0.4\) over 25 alternating rounds; on FB15k-237, \(\lambda_p^{sup} = 0.9, \lambda_p^{PL} = 0.1\) over 5 alternating rounds. Each M-step trains for 1 full epoch over \(\mathcal{G}_{aug}\).

Key Experimental Results

Main Results

Evaluated under the standard filtered ranking protocol on WN18RR and FB15k-237, LQ-KGC is compared against canonical structure-based embedding models, state-of-the-art text-based bi-encoders, and representative hybrid text-structure frameworks.

Category Method WN18RR MRR WN18RR H@1 WN18RR H@3 WN18RR H@10 FB15k-237 MRR FB15k-237 H@1 FB15k-237 H@3 FB15k-237 H@10
Structure-based TransE (Bordes et al., 2013)† 24.3 4.3 44.1 53.2 27.9 19.8 37.6 44.1
Structure-based DistMult (Yang et al., 2014)† 44.4 41.2 47.0 50.4 28.1 19.9 30.1 44.6
Structure-based ComplEx (Trouillon et al., 2017)† 44.9 40.9 46.9 53.0 27.8 19.4 29.7 45.0
Structure-based RotatE (Sun et al.)† 47.6 42.8 49.2 57.1 33.8 24.1 37.5 53.3
Structure-based ConvE (Dettmers et al., 2018)† 43.0 40.0 44.0 52.0 32.5 23.7 35.6 50.1
Structure-based CompGCN (Vashishth et al., 2019) 47.0 43.7 48.2 53.4 35.1 26.1 38.5 53.3
Text-based KG-BERT (Yao et al., 2019)† 21.6 4.1 30.2 52.4 – – – 42.0
Text-based SimKGC (Wang et al., 2022a) 67.1 58.5 73.1 81.7 33.6 24.9 36.2 51.1
Text-based GHN (Qiao et al., 2023) 67.8 59.6 71.9 82.1 33.9 25.1 36.4 51.5
Fusion methods StAR (Wang et al., 2021a)† 40.1 24.3 49.1 70.9 29.6 20.5 32.2 48.2
Fusion methods CSProm-KG (Chen et al., 2023) 57.5 52.2 59.6 67.8 35.8 26.9 39.3 53.8
Fusion methods Memory-KGC (Li et al., 2026) 68.0 59.8 72.6 81.2 34.0 25.4 37.1 51.4
Ours (Branch) \(\text{LQ-KGC}_{\text{LM}}\) 68.5 62.1 71.8 80.4 33.9 24.7 37.2 52.4
Ours (Branch) \(\text{LQ-KGC}_{\text{GNN}}\) 54.1 47.9 56.9 65.5 36.8 27.6 40.2 55.2
Ours (Full) LQ-KGC 68.6 62.4 71.8 80.5 38.3 29.1 42.0 56.7

(Note: Baselines marked with † are cited from SimKGC; other baselines are reproduced via official codebases or quoted from original papers.)

Ablation Study

Systematic component removals and query sampling comparisons illustrate how each design contributes to performance across the two benchmarks.

Variant Branch WN18RR MRR WN18RR H@1 WN18RR H@3 WN18RR H@10 FB15k-237 MRR FB15k-237 H@1 FB15k-237 H@3 FB15k-237 H@10
Full Model LM Branch 68.5 62.1 71.8 80.4 33.9 24.7 37.2 52.4
Full Model GNN Branch 54.1 47.9 56.9 65.5 36.8 27.6 40.2 55.2
Full Model Fused 68.6 62.4 71.8 80.5 38.3 29.1 42.0 56.7
w/o LM initialization LM Branch 68.2 61.7 71.8 80.3 33.8 24.5 37.0 52.4
w/o LM initialization GNN Branch 47.1 44.0 48.0 53.6 35.0 25.9 38.4 53.2
w/o LM initialization Fused 68.5 62.3 71.8 80.4 38.0 28.6 41.6 56.9
w/o LM pseudo edges LM Branch 68.4 62.0 71.8 80.5 33.8 24.6 37.2 52.3
w/o LM pseudo edges GNN Branch 52.5 46.3 55.1 64.4 36.3 27.2 39.8 54.9
w/o LM pseudo edges Fused 68.5 62.0 71.8 80.6 38.2 28.9 41.7 56.6
Fusion-only (No refinement) Fused 67.9 61.3 71.5 79.9 37.9 28.6 41.5 55.6
Random queries GNN Branch 53.3 47.0 56.1 65.0 36.2 26.9 39.8 54.4
Random queries Fused 68.6 62.2 71.8 80.5 38.3 29.2 41.5 56.4

Key Findings

  • Asymmetric Structural Gains via Text-to-Graph Injection: The primary empirical beneficiary of alternating refinement is the GNN branch. Removing pseudo-edge augmentation causes the GNN MRR to drop from 54.1 to 52.5 on WN18RR and from 36.8 to 36.3 on FB15k-237. Omitting LM feature initialization completely cripples the GNN on WN18RR, causing MRR to collapse from 54.1 back down to 47.1 (matching vanilla CompGCN).
  • Substantial Breakthrough on Low-Degree Entities: Head-entity degree stratification shows that \(\text{LQ-KGC}_{\text{GNN}}\) consistently improves over CompGCN across all degree buckets, with the sharpest gains in degree intervals \([0, 1)\) and \([1, 2)\). LM-derived representations and pseudo-edges compensate for graph sparsity where observed topological neighbors are virtually non-existent.
  • Alternating Optimization Outperforms Static Late Fusion: The Fusion-only baseline yields 67.9 MRR on WN18RR and 37.9 MRR on FB15k-237, trailing full LQ-KGC by 0.7 and 0.4 points respectively. This demonstrates that alternating iterative exchange fosters mutual representation adaptation during training rather than functioning as a mere post-processing score blend.
  • Query Construction Curbs Pseudo-Label Contamination: Full type-aware balanced sampling improves GNN MRR by 0.8 on WN18RR and 0.6 on FB15k-237 over naive random query selection, proving that type compatibility and degree caps effectively suppress noisy pseudo-edge propagation.

Highlights & Insights

  • Tractable EM Surrogacy via Bounded Latent Queries: Instead of succumbing to combinatorial explosion over all unobserved triples, LQ-KGC formulates a computationally tractable EM surrogate restricted to a carefully curated, type-compatible subset \(\mathcal{Q}\), rendering bidirectional pseudo-label exchange feasible in multi-relational graphs.
  • Asymmetric Synergy in Multimodal Graph Refinement: The analysis provides clear conceptual insight into text-structure synergy: text-to-graph pseudo-edge injection provides concrete relational connectivity for sparse subgraphs, while graph-to-text distillation provides soft regularizing constraints that sharpen ranking precision.
  • Zero Additional Latency at Inference Time: Despite incorporating iterative EM-style cycles during training (which add only 1.1~1.7 hours on an A100 GPU), test-time inference requires only standard parallel forward passes through the LM dual-encoder and GNN-ConvE decoder, followed by scalar score normalization and addition.

Limitations & Future Work

  • Multi-Stage Training Overhead: While the refinement stage itself is relatively fast, the framework relies on fully pretrained LM and GNN checkpoints, resulting in a complex pipeline compared to unified end-to-end models.
  • Dependency on Informative Entity Text: The framework's ability to cluster entity spaces and formulate type priors relies heavily on descriptive text; performance is expected to deteriorate on graphs featuring synthetic, hashed, or uninformative entity tokens.
  • Scope Restricted to Transductive Benchmarks: The evaluation is confined to standard transductive settings. Investigating inductive KGC (where unseen entities emerge during testing) and conducting granular breakdowns across specific relation topologies (e.g., 1-to-N, N-to-1, symmetric) remain important avenues for future study.
  • vs. SimKGC (Wang et al., 2022a): SimKGC relies strictly on contrastive dual-encoder text matching, achieving high performance on lexical graphs like WN18RR but lacking global multi-hop topological reasoning on dense relational graphs like FB15k-237; LQ-KGC incorporates GNN topological distillation and score fusion, boosting FB15k-237 MRR from 33.6 to 38.3.
  • vs. CompGCN (Vashishth et al., 2019): CompGCN operates on observed relational edges and suffers severely from structural sparsity; LQ-KGC initializes node features with text embeddings and expands the graph with confident pseudo-edges, yielding a 9.1% relative MRR boost on FB15k-237.
  • vs. StAR / CSProm-KG (Wang et al., 2021a; Chen et al., 2023): These approaches utilize static one-way structural prompts or fixed joint objectives; LQ-KGC is the first to introduce an alternating EM-style pseudo-edge and distillation feedback loop for KGC.
  • vs. GLEM (Zhao et al., 2023): GLEM applies variational pseudo-label exchange for node classification on text-attributed graphs; LQ-KGC generalizes alternating refinement to multi-relational knowledge graph completion with typed pseudo-edges and relation-aware candidate ranking.

Rating

  • Novelty: ⭐⭐⭐⭐ Elegant adaptation of EM-style latent variable refinement to multimodal text-structure knowledge graph completion.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive evaluation across benchmarks, degree-bucketed analyses, component/sampling ablations, multi-seed variance checks, and training dynamics.
  • Writing Quality: ⭐⭐⭐⭐⭐ Rigorous mathematical formulation, clear narrative structure, and insightful interpretation of asymmetric empirical dynamics.
  • Value: ⭐⭐⭐⭐ Offers a highly practical and transferable semi-supervised refinement paradigm for knowledge-intensive reasoning and sparse graph completion.