Knowledge graph (KG) foundation models (KGFMs) are zero-shot generalizers: trained once, they can predict links on unseen graphs without retraining. However, understanding when and how they can robustly generalize across KGs is still an open question. In this paper, we shed some light on their generalization mechanisms highlighting how their performance on unseen KGs is not uniform when it comes to partially seen links, which we call *half-links*. In fact, we show that to predict a test triple (h,r,t) it might suffice in practice to have observed the half-link (h,r) or (r,t) in the inference graph. This yields a taxonomy of four scenarios when combinations of these half-links are observed or not. In a rigorous stratified analysis over these scenarios, we reveal that SoTA KGFMs use seen half-links for predictions, while unseen half-links pose different challenges. As such, our finer-grained taxonomy can be a diagnostic protocol for robust KGFM generalization and highlights where novel KGFMs can improve.

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.

Uncertainty quantification in Knowledge Graph Embedding (KGE) methods is crucial for ensuring the reliability of downstream applications. A recent work applies conformal prediction to KGE methods, providing uncertainty estimates by generating a set of answers that is guaranteed to include the true answer with a predefined confidence level. However, existing methods provide probabilistic guarantees averaged over a reference set of queries and answers (marginal coverage guarantee). In high-stakes applications such as medical diagnosis, a stronger guarantee is often required: the predicted sets must provide consistent coverage per query (conditional coverage guarantee). We propose CondKGCP, a novel method that approximates predicate-conditional coverage guarantees while maintaining compact prediction sets. CondKGCP merges predicates with similar vector representations and augments calibration with rank information. We prove the theoretical guarantees and demonstrate empirical effectiveness of CondKGCP by comprehensive evaluations.