Encode to Decode: Scalable Knowledge Graph Foundation Models from Embedding Models

Knowledge Graph Foundation Models (KGFMs) have emerged to enable zero-shot generalization to unseen knowledge graphs (KGs). However, existing KGFMs typically incur a significant computational overhead by executing message passing over the entire KG for every single query. We introduce MUZE, a scalable KGFM whose encoder constructs query-independent entity and relation embeddings from random initialization through recursive message passing. At each layer, MUZE computes messages using the gradients of a Knowledge Graph Embedding (KGE) scoring function and aggregates them to update entity and relation representations. The link prediction decoder directly applies the same scoring function to the resulting embeddings to rank candidates for each query. This principled coupling unifies KGE-based decoding and message-passing-based encoding by incorporating the KGE scoring function into the encoder’s recursive computation. Crucially, since KGE scoring functions operate directly on query-independent embeddings, MUZE encodes each KG once and reuses the resulting embeddings across queries, thereby substantially reducing inference time. We theoretically prove that, on a finite set of KGs, MUZE can recover arbitrary target embeddings and serve as a fully expressive encoder for KG tasks solvable via entity and relation embeddings. Experiments show that MUZE is 11x faster than the fastest baseline and over 1389x faster than the most accurate baseline, all while delivering comparable or superior accuracy.