A Foundation Model for Zero-shot Logical Query Reasoning

Problem setting

• CLQA combines relation projections with intersection, union, and negation to answer compositional queries over incomplete knowledge graphs.Queries are expressed in a subset of first-order logic with existential variables and constants.Source: §1 · p. 2

Research gap

• Existing CLQA methods usually learn graph-specific entity and relation embeddings, making them transductive and unable to generalize across graphs.Some approaches handle new entities but still require a fixed relation vocabulary.Source: §1 · p. 2

Inductive zero-shot setting

• ULTRAQUERY targets the hardest setting, where inference queries and graphs contain entirely new entities and relations, without target-graph training.The setup is illustrated as training and inference graphs with different vocabularies.Source: §1 · p. 2, Figure 2 · p. 2

Approach

• ULTRAQUERY uses an inductive GNN projection operator and non-parametric fuzzy logical operators that avoid graph-specific entity and relation embeddings.Its projection operator is initialized from a pre-trained inductive KG reasoning model.Source: §1 · p. 2

Empirical result

• A single ULTRAQUERY model trained on one dataset outperforms reported baselines by 50% relative MRR across 23 datasets on EPFO and negation queries.The evaluation spans a newly curated suite of 11 inductive datasets and 22 additional transductive and inductive datasets.Source: §1 · p. 2

Transductive CLQA

• Most CLQA methods, including GQE, BetaE, ConE, and MPQE, are transductive because they learn embeddings for fixed entity and relation vocabularies.CQD and QTO avoid learned logical operators but still require pre-trained entity and relation embedding matrices for projections.Source: §2 · p. 3

Inductive CLQA

• Existing inductive CLQA methods generally handle new entities only and remain bound to a fixed relation vocabulary.GNN-QE is described as the most effective inductive entity approach, but it cannot generalize to new relations.Source: §2 · p. 3

Positioning

• Table 1 identifies ULTRAQUERY as the first inductive CLQA method generalizing to queries over new entities and relations at inference time.The comparison distinguishes inductive generalization to entities (e) and relations (r).Source: Table 1 · p. 3

Inductive KG completion

• Inductive KG completion distinguishes entity-only methods from inductive (e, r) methods that generalize to arbitrary new entity and relation sets.Most earlier approaches belonged to the inductive (e) family because their featurization used learnable relation embeddings.Source: §2 · p. 3

Vocabulary-independent reasoning

• ULTRAQUERY uses ULTRA’s meta-graph relation representations, whose four meta-relations are independent of the KG’s relation vocabulary.This enables transferable graph representations without input features across arbitrary KGs.Source: §2 · p. 3

Knowledge graphs and inductive setup

• A knowledge graph is a tuple of entities, relations, and triples, with transductive inference using the same graph as training.Inductive inference instead uses a different graph, which may extend the training graph or be disjoint from it.Source: §3 · pp. 3–4

Inductive (e, r) setting

• The hardest inductive (e, r) setting has disjoint entity and relation sets between training and inference graphs, and no prior CLQA method addressed it.ULTRAQUERY is presented as the first method for this case.Source: §3 · p. 4

First-order logic queries

• FOL queries combine constants, existential variables, relation projections, and logical operators; answers are variable assignments satisfying the query in the complete graph.Hard answers require predicting at least one edge absent from the observed inference graph.Source: §3 · p. 4

Query answering

• CLQA predicts bindings for target variables, such as identifying Mark Knopfler from an intersection query involving BandMember and inverse Plays relations.Although easy answers are reachable by traversing the observed graph, evaluations focus on hard answers.Source: §3 · p. 4

Scope of the problem

• Transductive models can learn hardcoded entity and relation embeddings, while inductive entity models retain a fixed relation set and therefore cannot handle arbitrary KGs.The paper removes both vocabulary restrictions and still requires missing-link prediction for hard answers.Source: §3 · p. 4

Query execution

• Figure 3 depicts projection scores being aggregated by fuzzy logical operators, with intermediate scores initializing the next projection hop.It also contrasts single-source pre-training with multi-source propagation in complex queries.Source: Figure 3 · p. 5

4.1 Inductive Relation Projection

• A single inductive projection operator uses relation interactions and graph neural networks to transfer across entity and relation vocabularies.ULTRA constructs a relation-interaction meta-graph with four vocabulary-independent meta-relations, then applies relation-level and entity-level message passing to score candidate tails.Source: §4.1 · pp. 5–6
• Multi-hop queries create a distribution shift because several intermediate nodes can propagate simultaneously, so ULTRAQUERY fine-tunes the operator or thresholds scores to limit sources.The main model uses short fine-tuning on complex queries; ULTRAQUERY LP instead freezes the pre-trained operator and zeroes scores below a threshold.Source: §4.1 · p. 6

4.2 Inductive Logical Operations

• ULTRAQUERY implements conjunction, disjunction, and negation with non-parametric product fuzzy logic over bounded fuzzy sets, avoiding embedding-space-specific neural operators.Product logic uses element-wise multiplication for conjunction, x + y − x ⊙ y for disjunction, and 1 − x for negation; later-hop node states are weighted by prior probabilities.Source: §4.2 · p. 6

4.3 Training

• The model is trained on complex queries with binary cross entropy using final answer probabilities, while ULTRAQUERY LP remains a frozen KG-completion checkpoint.A_q denotes the query-answer set, and p(a|q) is the final fuzzy-set probability assigned to entity a.Source: §4.3 · p. 6

5.1 Setup and Datasets

• ULTRAQUERY is evaluated in zero-shot mode across 23 CLQA datasets spanning transductive, inductive-entity, and inductive entity-and-relation settings.The evaluation trains on one FB15k237 dataset and runs inference on other graphs with different entity and relation vocabularies.Source: §5.1 · pp. 6–7, §5.2 · p. 7
• The model uses filtered MRR and Hits@10 for EPFO and negation queries, alongside faithfulness, ROC AUC, and MAPE analyses.The qualitative metrics assess recovery of easy answers, ranking of easy over hard answers, and answer-set cardinality.Source: §5.1 · p. 7, §5.2 · p. 8

5.2 Main Experiment: Zero-shot Query Answering

• Averaged across 23 datasets, ULTRAQUERY improves relative MRR and Hits@10 by 50% on EPFO and 70% on negation queries over available baselines.The reported examples are 0.31 versus 0.20 MRR for EPFO and 0.178 versus 0.105 for negation queries; gains are largest on inductive entity-and-relation datasets.Source: §5.2 · p. 8, Table 2 · p. 8

5.3 Analysis

• Training on complex queries mitigates multi-source propagation: ULTRAQUERY sacrifices some 1p performance for better negation and many EPFO queries, including 3i.The LP variant performs better on 1p queries but struggles when several intermediate nodes propagate messages.Source: §5.3 · pp. 8–9, Figure 4 · p. 8, §5.2 · p. 8
• ULTRAQUERY nearly perfectly recovers easy answers across graph sizes, while its easy-versus-hard ranking trails GNN-QE because score distributions overlap.Despite weaker ROC AUC, score filtering prevents this ranking difference from directly harming overall ranking metrics.Source: §5.3 · p. 9, Figure 5 · p. 9
• ULTRAQUERY matches the larger QTO baseline for answer-set cardinality, whereas ULTRAQUERY LP remains vulnerable to high scores caused by multi-source propagation.Adding training graphs yields about 10% EPFO gains on 11 inductive entity-and-relation datasets, while the 2G model slightly reduces negation performance on average.Source: §5.3 · pp. 9–10, Figure 6 · p. 9, Table 3 · p. 10

• ULTRAQUERY’s limitations and improvement opportunities stem from the projection operator and its interaction with the multi-hop query-answering framework.Source: §6 · p. 10
• Scaling to very large KGs could be improved with more scalable entity-level GNN predictors such as A*Net or AdaProp.Source: §6 · p. 10
• ULTRAQUERY performs comparably to or better than strong baselines trained specifically on each graph while retaining faithfulness and answer-cardinality estimation.Source: §6 · p. 10
• Multi-source message propagation is the key challenge when adapting pre-trained projection operators to multi-hop query answering.Source: §6 · p. 10
• The work identifies future extensions including richer query patterns, queries without anchor nodes, hyper-relational, numerical-literal, and temporal queries.Source: §6 · p. 10

• The appendix provides graph details for three transductive, nine inductive-entity, and eleven inductive entity-and-relation datasets.Source: §A.1 · p. 14, Table 4 · p. 14, Table 5 · p. 14
• Transductive dataset tables list training, validation, and test triples with inverse triples and edge types included in the splits.Source: Table 4 · p. 14
• Inductive-entity datasets use validation and test inference graphs that extend training graphs with new nodes and missing edges to predict.Source: Table 5 · p. 14
• WikiTopics-CLQA supplies newly sampled graphs for the fully inductive entity-and-relation setting, with triples reported for training, validation, and test graphs.Source: Table 6 · p. 14, §A.1 · p. 14

• WikiTopics-CLQA evaluates zero-shot performance when test-time inference graphs contain new entities and new relations unseen during training.Source: §A.2 · p. 14
• The dataset covers topic-specific knowledge graphs spanning domains such as art, education, health care, and sport.Source: §A.2 · p. 15
• The evaluation trains on one topic’s graph and tests on an unseen topic’s inference graph, with validation and test performance evaluated on missing triples.Source: §A.2 · p. 15
• For each topic, training and validation queries use the training graph, while test queries use the inference graph.Source: §A.2 · p. 15
• WikiTopics-CLQA follows BetaE’s 14 query patterns and generates training, validation, and test query-answer sets for each topic.Source: §A.2 · pp. 15–16, Table 9 · p. 15
• Training queries contain only easy answers, whereas validation and test sets distinguish traversal-reachable easy answers from full answer sets that include hard answers.Source: §A.2 · p. 16

• ULTRAQUERY and ULTRAQUERY LP use the pretrained ULTRA checkpoint, share GNN architectures, and each contain 177k parameters.Source: B Hyperparameters and Baselines · p. 16
• ULTRAQUERY is trained for 10,000 steps on complex queries from FB15k237 after initialization from the pretrained checkpoint.Source: B Hyperparameters and Baselines · p. 16
• ULTRAQUERY LP thresholds intermediate fuzzy-set scores, generally using a threshold of 0.8, to alleviate multi-source propagation.Source: B Hyperparameters and Baselines · p. 16
• The transductive baseline is QTO, which requires graph-specific ComplEx embeddings and materializes a full V × V × R score tensor.Source: B Hyperparameters and Baselines · p. 16
• GNN-QE is the inductive-entity baseline, but its graph-specific relation embeddings make its parameter count depend on the number of relation types.Source: B Hyperparameters and Baselines · p. 16
• For inductive entity-and-relation datasets, evaluation compares against a non-parametric relation-type heuristic that provides a sanity-check ranking without training.Source: B Hyperparameters and Baselines · p. 16

C More Results

• Figure 7 provides complete results for 9 entity-inductive datasets and 14 query types, including EPFO and negation averages.The comparison includes ULTRAQUERY, ULTRAQUERY LP, and the best baseline.Source: C More Results · p. 16, Figure 7 · p. 18
• Full results compare ULTRAQUERY, ULTRAQUERY LP, and the best baseline using MRR and Hits@10 across 9 EPFO and 5 negation query types.The evaluation covers transductive, entity-inductive, and fully inductive datasets, with ULTRAQUERY fine-tuned only on FB15k237 queries.Source: C More Results · p. 16, Table 11 · p. 17
• ULTRAQUERY trades some 1p-query performance for substantially better average performance on complex EPFO and negation queries.The gains are especially noticeable for intersection and 2in, 3in queries.Source: Figure 7 · p. 18