Logic Meets Language: Hybrid Query Answering over Incomplete Text-Labeled Graphs¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/RoyaHe/HybridQE---
Area: Graph Learning
Keywords: Hybrid Query Answering, Text-Labeled Knowledge Graphs, Query Embedding, Logical Reasoning, Graph Incompleteness
TL;DR¶
Addressing the challenge of answering queries requiring both discrete logical constraints and flexible textual semantics over incomplete text-labeled graphs, this paper formalizes a hybrid query language and introduces HybridQE, an end-to-end framework that unifies query-conditioned entity representations with neural logical operators in a shared embedding space.
Background & Motivation¶
Text-labeled graph databases combine relational symbolic structures with rich unstructured textual descriptions, providing a flexible and expressive data model for real-world applications such as e-commerce product catalogs and biomedical knowledge graphs. However, real-world user retrieval requests often exhibit a dual demand: they require precise logical constraints (e.g., Boolean intersections, unions, and negations such as "black or white tennis racket that is not Wilson") while simultaneously depending on nuanced, context-dependent free-form textual concepts (e.g., "very lightweight", which cannot be straightforwardly mapped to fixed discrete symbolic attributes). Existing information retrieval engines, graph-based RAG frameworks, and symbolic query reasoning systems typically address only a single modality, or rely on loose modular cascades that struggle to preserve logical precision while interpreting textual semantics.
A more critical bottleneck arises from information incompleteness. Due to high manual curation costs and rapid updates, relational graph edges are inherently sparse, noisy, or missing, while textual descriptions are frequently fragmentary. Conventional complex query embedding techniques (such as BetaE and GammaE) support reasoning over missing relational edges but discard textual descriptions entirely. Conversely, LLM-driven graph traversal methods and dense text retrieval fail when relational paths are incomplete, and translating exact symbolic queries into natural language questions introduces substantial semantic ambiguity and loss of logical rigor.
To overcome the compounded challenges of logical precision, semantic flexibility, and structural incompleteness, this work posits that symbolic logic and free-form text must be directly represented and jointly reasoned over without one-way translations. The core idea is to formalize a hybrid query language extending description logics with text nominals and textual relational existentials, and propose HybridQE, which projects both modalities into a shared embedding space using query-conditioned cross-attention on entity tokens alongside neural logical operators, enabling textual evidence to compensate for missing graph relations while symbolic constraints prune irrelevant textual candidates.
Method¶
Overall Architecture¶
HybridQE models hybrid query answering over a text-labeled knowledge graph \(G = (V, R, E, T, \tau)\) by embedding both the hybrid query \(Q = \{t\} \sqcap \phi\) and candidate entities \(e \in V\) into a shared latent vector space \(E^d\), ranking entities based on their geometric distance to the query embedding. The reasoning pipeline consists of three primary stages: first, text descriptions of relations and text nominals are encoded using a pretrained language model; second, a Query-Conditioned Similarity (QCS) mechanism dynamically derives contextualized entity embeddings by attending to entity tokens using both textual and symbolic query vectors; third, a unified symbolic query encoder recursively processes logical operators (projection, intersection, union, and complement) to form the composite query representation, directly evaluating entity plausibility via geometric distance.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
In["Input: Hybrid Query Q = {t} โ ฯ and Candidate Entity e<br/>Free text t, symbolic formula ฯ, entity text te"] --> QCS["1. Query-Conditioned Entity Embedding (QCS)<br/>Cross-attention over entity tokens guided by query vectors and gating fusion"]
QCS --> Rel["2. Relation and Text Nominal Mapping<br/>Project relation descriptions and text nominals into shared space"]
Rel --> SymEnc["3. Unified Neural Logical Encoder (Symbolic Query Encoder)<br/>Recursively apply projection, intersection, union, complement to fuse Emb{t} and Embฯ"]
SymEnc --> Rank["4. Distance Metric and Graph-Wide Entity Ranking<br/>Compute KL divergence / geometric distance Dist(EmbQ, eQ) for hard answer evaluation"]
Key Designs¶
1. Query-Conditioned Entity Embedding: Dynamically focusing on query-relevant tokens in entity descriptions Traditional knowledge graph embeddings assign a single static vector to each entity, failing to adapt when long textual descriptions contain diverse attributes that are only selectively relevant to a specific query. To resolve this, HybridQE introduces the Query-Conditioned Similarity (QCS) mechanism. For each candidate entity \(e \in V\) with textual description \(t_e = \tau(e)\), a pretrained language model generates token-level representations \(E \in \mathbb{R}^{n \times d}\) and a mean-pooled summary \(\bar{e} \in \mathbb{R}^d\). Given the hybrid query \(Q = \{t\} \sqcap \phi\), two query vectors are derived: \(q_t = \xi(t)\) for the explicit text nominal, and \(q_\phi = \xi(t_\phi)\) as an auxiliary attention vector verbalizing the symbolic formula \(\phi\). Token-level attention weights are computed via normalized dot products: $\(\alpha_t = \text{softmax}(E q_t) \in \mathbb{R}^n, \quad \alpha_\phi = \text{softmax}(E q_\phi) \in \mathbb{R}^n\)$ yielding query-conditioned context vectors \(\tilde{a}_t = E^\top \alpha_t\) and \(\tilde{a}_\phi = E^\top \alpha_\phi\). Adaptive gating functions modulate the modality contributions: $\(g_t = \sigma(W_t [\bar{e}; \tilde{a}_t]), \quad g_\phi = \sigma(W_\phi [\bar{e}; \tilde{a}_\phi])\)$ The final contextualized entity representation is computed via an MLP projection \(e_Q = P_E(\bar{e} + g_t \odot \tilde{a}_t + g_\phi \odot \tilde{a}_\phi)\), ensuring that entity embeddings actively emphasize the textual attributes most pertinent to both constraints in \(Q\).
2. Cross-Modal Neural Logical Operators in Shared Space: Preserving exact logical semantics alongside textual evidence Translating symbolic logic to natural language causes operator distortion, while parsing text into fixed schemas suffers from severe parsing errors. HybridQE introduces a hybrid query language based on \(\mathcal{SROI}^-\) description logic augmented with text nominals \(\{t\}\) and textual relational existentials \(\exists t.Q\). The symbolic encoder maintains the exact compositional structure of \(\phi\) while evaluating in a continuous vector space \(E^d\). Relation descriptions are projected via \(r = P_R(\xi(t_r))\), and text nominals are embedded as \(\text{Emb}_{\{t\}} = \text{Nominal}(P_E(\xi(t)))\). The conjunction between text and symbolic constraints is executed directly as an intersection operation: $\(\text{Emb}_Q = \text{Intersect}(\text{Emb}_{\{t\}}, \text{Emb}_\phi)\)$ The architecture is model-agnostic: in the BetaE instantiation, concepts are modeled as Cartesian products of Beta distributions with intersections computed via weighted PDF products; in the GammaE instantiation, concepts are represented by Gamma distributions with unions modeled through self-attention Gamma mixture models. This allows textual evidence to seamlessly compensate for missing relational edges while symbolic constraints sharply filter out textually ambiguous entities.
3. Graph-Structure Augmentation and Margin-Based Contrastive Training: Optimizing multi-hop inference under structural incompleteness To test reasoning over missing edges, evaluation strictly targets the hard answer set \(A_{\text{hard}}(Q) = Q^{G_{\text{test}}} \setminus Q^{G_{\text{train}}}\). Training solely on complex hybrid queries risks under-representing the underlying graph topology. HybridQE mitigates this by augmenting the training data with the entire training graph formulated as 1p hybrid queries with empty textual components, compelling the model to learn latent relational transition patterns. The model is optimized end-to-end using a negative sampling margin-based objective: $\(\mathcal{L}(Q) = \sum_{a \in Q^G} \frac{1}{|N_a|} \sum_{b \in N_a} \left[ \log \sigma(\gamma - \text{Dist}(\text{Emb}_Q, \text{Emb}_{\{b\}})) - \log \sigma(\gamma - \text{Dist}(\text{Emb}_Q, \text{Emb}_{\{a\}})) \right]\)$ where \(a\) is a valid positive answer, \(b \in N_a\) are sampled negative entities, \(\text{Dist}(\cdot)\) is the distribution-specific KL divergence, and \(\gamma\) is the margin hyperparameter.
A Worked Example¶
Consider a 3i hybrid query from ProdHybridQA, \(Q = \phi \sqcap \{t\}\):
- Symbolic formula: \(\phi = \exists \text{category}.\{\text{Baby\_Bottle}\} \sqcap \exists \text{material\_type}.\{\text{BPA free}\} \sqcap \exists \text{color}.\{\text{Pink}\}\)
- Text query: \(t =\) "Could you help locate a bottle categorized as a baby product with a capacity measured in milliliters?"
- Ground-truth hard answer entity: B078TGQHQQ (Putti Atti Silicone Baby Bottle), whose symbolic edges are entirely absent from \(E_{\text{train}}\) (belonging to \(E_{\text{missing}}\)).
- Execution trace:
1. The symbolic encoder alone ranks B078TGQHQQ at rank 2 by utilizing latent relational patterns across the training graph.
2. The text encoder alone ranks B078TGQHQQ at rank 4, as its description explicitly contains "BPA Free" and "Pink" along with fluid capacity indicators.
3. HybridQE fuses both modalities through the intersection operator, elevating B078TGQHQQ to rank 1.
4. In contrast, distractor entity B07RR2BRHD has a strong text rank (rank 3) but weak symbolic rank (rank 5), resulting in demotion to rank 2; entity B00DBFXG1Q lacks volume indicators in text, dropping its text rank to 8 and overall hybrid rank to 3. The joint mechanism cleanly filters out partial-evidence false positives.
Key Experimental Results¶
Main Results¶
HybridQE was extensively evaluated on two benchmarks: ProdHybridQA (e-commerce hyperedge graph) and BioHybridQA (biomedical triple graph derived from PrimeKG). Evaluation focuses exclusively on the hard answer set \(A_{\text{hard}}(Q)\) across standard retrieval metrics (MRR, Hits@1, Hits@3).
| Dataset | Metric (Avg MRR) | HybridQE (GammaE) | HybridQE (BetaE) | Best Baseline (BM25) | Runner-up (HybGRAG / ANCE) | Gain (vs BM25) |
|---|---|---|---|---|---|---|
| ProdHybridQA | MRR | 14.65 | 11.18 | 9.23 | 7.73 (HybGRAG) | +58.7% |
| BioHybridQA | MRR | 6.38 | 5.76 | 6.25 | 5.48 (ANCE) | +2.1% (Overall) / Substantial gain on complex queries |
Across specific query families, performance gains are particularly pronounced on structurally complex queries (2i, 3i): - On ProdHybridQA 3i queries, HybridQE (GammaE) achieves an MRR of 28.61, outperforming BM25 (11.96) and HybGRAG (15.28) by over 13 points. - On BioHybridQA 3i queries, HybridQE (GammaE) reaches an MRR of 16.31, substantially higher than BM25 (10.87) and ANCE (9.01). - The modular pipeline QE+LM completely fails (achieving only 0.24 average MRR on ProdHybridQA), demonstrating that post-hoc score intersection is incapable of handling severe structural incompleteness.
Ablation Study¶
Ablations on model components were conducted on both benchmarks using the BetaE backbone (measuring Avg MRR):
| Configuration | Mechanism | Graph Augmentation | ProdHybridQA Avg | BioHybridQA Avg | Findings |
|---|---|---|---|---|---|
| QCS with graph (Full Model) | Query-Conditioned Similarity | Yes (1p augmentation) | 11.18 | 5.76 | Achieves consistent top performance across all query types |
| QCS w/o graph | Query-Conditioned Similarity | No | 8.92 | 4.63 | Omitting graph topological augmentation reduces inference accuracy |
| MLP with graph | Static MLP (replacing QCS) | Yes | 9.45 | 4.88 | Lacks adaptive attention over description tokens |
| MLP w/o graph | Static MLP | No | 7.31 | 3.95 | Double degradation confirms the necessity of joint modeling |
Query formulation ablations further confirm the advantage of the hybrid paradigm: - On ProdHybridQA, translating hybrid queries into pure natural language questions (Text Only) causes GammaE MRR to drop from 15.90/20.15/28.61 to 8.18/15.83/16.57 across 1p/2i/3i queries. - Translating queries into pure symbolic representations (Symbolic Only) drops MRR to 10.29/10.61/14.42, underscoring that forcing single-modality conversions sacrifices critical information.
Key Findings¶
- Complementary inference pathways: Cross-modal interaction allows missing relational edges to be recovered via unstructured textual descriptions, while precise symbolic constraints restrict the candidate space and eliminate semantic drift.
- Error distribution characteristics: A stratified error analysis on BioHybridQA reveals that negation queries (1n, 2in, 3in) are dominated by negation failures (Type IV, 56.9%โ78.8%), largely due to hidden negation violations where violating edges are unobserved in the training graph. For multi-hop projections (2p, 3p), path-composition failure (Type VI) accounts for 63.7%โ72.5% of errors.
- Entity frequency dynamics: In few-shot analysis, performance follows a non-monotonic curve: moderate-frequency entities (2โ50 occurrences) achieve the highest MRR (22.40), while ultra-high-frequency hub nodes (\(\ge 2000\)) degrade to 6.47 MRR due to generic descriptions and high connectivity. Frequency-1 entities maintain an average MRR of 17.36, demonstrating robust cold-start reasoning via query-conditioned textual matching.
Highlights & Insights¶
- Unified latent space integration: Unlike agentic RAG methods that verbalize graph subgraphs into text prompts, or modular pipelines that intersect candidate lists post-hoc, HybridQE directly computes algebraic logical operations across text and structure inside a continuous probability embedding space.
- Effective long-tail knowledge recovery: Pretrained cross-attention enables the model to salvage missing attribute facts (such as product material or color) directly from raw text descriptions, bypassing the need for manual graph completion.
- Rigorous benchmark design: Benchmark generation enforces non-empty hard answer sets (\(A_{\text{hard}} \neq \emptyset\)) and employs LLM-driven semantic abstraction to ensure text queries express qualitative concepts without trivial lexical overlap (mean token F1 \(\le 0.34\)).
Limitations & Future Work¶
- Neural complement operator fragility: Continuous geometric representations struggle to establish sharp boundaries for logical negation under incomplete data, especially when conflicting edges are missing from the graph.
- Transductive evaluation scope: While preliminary few-shot experiments show promising results, the current framework primarily addresses the transductive setting, leaving fully inductive hybrid query answering over unseen test entities as an open problem.
- Domain specialization of text encoders: Generic pretrained language models may exhibit degraded representation capacity in highly specialized technical domains without task-specific continual pretraining.
Related Work & Insights¶
- vs BM25 / ANCE: Lexical and dense text retrieval systems excel at surface-level similarity but cannot enforce Boolean constraints or traverse graph structures; HybridQE handles complex compositional logic while traversing incomplete relational graphs.
- vs ToG / HybGRAG: Graph RAG frameworks rely on LLM agentic traversal, suffering from beam search truncation when edges are missing and encountering high query latency; HybridQE executes in tens of milliseconds per query via batched matrix operations.
- vs BetaE / GammaE: Classical neural query embedding models are restricted to discrete symbolic graphs and discard node text entirely; HybridQE preserves their logical reasoning strengths while infusing contextualized text semantics.
Rating¶
- Novelty: โญโญโญโญโญ First systematic formalization of hybrid query answering over incomplete text-labeled graphs, featuring a native multi-modal description logic grammar and embedding framework.
- Experimental Thoroughness: โญโญโญโญโญ Comprehensive evaluation across hyperedge and triple graphs, accompanied by rigorous ablations, error taxonomy, scalability benchmarks, and few-shot analyses.
- Writing Quality: โญโญโญโญโญ Exceptionally rigorous mathematical formulation, structured problem definitions, and intuitive case study breakdowns.
- Value: โญโญโญโญโญ Provides a foundational blueprint for bridging neural logical query answering with unstructured text retrieval over modern semi-structured knowledge bases.