Total: 1
Text-labeled graph databases combine symbolic graph structures with rich textual descriptions, enabling expressive representations for real-world data. However, answering queries over such databases remains challenging when queries require both precise logical constraints and flexible semantic text interpretation, especially under information incompleteness. We introduce the task of hybrid query answering (hybrid QA) over incomplete text-labeled graph databases, which requires joint reasoning over both symbolic and textual knowledge under incompleteness. To investigate this problem, we formalize a query language that integrates logical constraints with free-form textual descriptions and construct two new benchmark datasets from biological and e-commerce domains. We propose HybridQE, a hybrid query embedding framework that aligns with our query language via embedding and combining the symbolic and textual constraints in a unified embedding space. Experiments on the proposed benchmarks show that existing methods struggle with this setting, while HybridQE provides consistent improvements across diverse hybrid query types, highlighting both the difficulty of HybridQA and the promise of hybrid query embeddings for reasoning under incompleteness.