acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Knowledge Graph, Knowledge Graph Foundation Model, Knowledge Graph Embedding, Knowledge Graph Representation Learning, Knowledge Graph Completion, Link Prediction, Message Passing Neural Network

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_upr1OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2(+1)
Soundness
1
Read review
Paper summary

This paper presents a knowledge graph foundation model (KGFM) called Muze for link and relation prediction. Generally, KGFMs aim to overcome the limitations of knowledge graph embeddings (KGE) by being able to support new entities and relations at inference time, including zero-shot prediction on a completely new KG.

I consider the positioning of this paper misleading, and recommend to reject the paper for this reason. At its heart, the approach trains a KGE model on the inference graph and uses it for prediction as in KGE models. The paper does not write it like this, however, but rephrases the gradient-based training process of KGE models with GNN-terminology (e.g., random initialization becomes random node embeddings, gradient computation becomes message computation/aggregation, optimizer step becomes embedding update) to make it look more like a KGFM. The relationship to KGE models and their training process is not clearly exposed.

Critical strengths

S1. The approach may add something valuable to KGE training (such as requiring less epochs or preventing overfitting).

S2. The approach suggests that KGE-style models are competitive for inductive LP, if one is willing to retrain on the inductive split.

Critical weaknesses

W1. Does not clearly state that it essentially fits a KGE model (or an ensemble of KGE models, if multiple runs are used). KGE model training with gradient descent works as follows:

  1. Initialize embeddings of all entities and relations randomly.
  2. Compute the gradient of each entity and relation embedding using negative sampling.
  3. Update each entity and relation embedding using an optimizer.
  4. Repeat for a certain number of epochs.
  5. Predict via ranking with scoring function.

The proposed method works as follows:

  1. Directly.
  2. Directly, as a_{x,t} matches exactly the KGE gradient.
  3. Using a custom "optimizer", which has momentum/adaptive LR terms (4), an LR schedule (eta, gamma, alpha), and normalization. The main difference to KGE training is that the optimizer uses a small trained model to determine the update.
  4. Directly, each layer corresponds to an epoch.
  5. Directly.

KGE models are typically trained using mini-batches of triplets; the proposed paper does the same (App B.2). Moreover, "MUZE encodes each KG once and reuses the embeddings across queries" also holds for KGE models. And like KGE models, MUZE needs to rerun everything as soon as anything in the KG changes (such as new entities, relations, triplets, ...).

This relationship is not clearly exposed in the paper, which is why I consider the paper misleading.

Questions for authors

None.

6 comments
AuthorsOpenReview ↗

Response to Reviewer upr1

We respectfully disagree with the review’s claim that we simply rephrase the KGE training process to make it look like a KGFM. The review’s central premise, that MUZE trains a standard KGE model on an inference graph, is factually incorrect.


MPNN Inference Is Not KGE Training

The approach of this paper is highly flawed/misleading: it's training a standard KGE model on the inference graph and uses it for prediction as usual.

Does not clearly state that it essentially fits a KGE model (or an ensemble of KGE models, if multiple runs are used).

MUZE is an MPNN that performs zero-shot inference on unseen KGs after pre-training. During pre-training, MUZE learns the parameterized scoring function (Lines 238-242) and MLP-based update functions (Eqs. (5)-(6)). At inference, it simply performs a forward pass on the input KG with the learned parameters (Lines 149-152). Computing representations via message passing with fixed, learned parameters is standard MPNN inference, not standard KGE training.

In Table 21 of Appendix D in the revised manuscript, we trained a KGE model with MUZE's scoring function on each of the 13 transductive KGs for K=12K = 12 epochs, matching the number of layers of MUZE. MUZE substantially outperforms the resulting KGE model: 0.331 (MUZE) vs. 0.022 (KGE) MRR for entity prediction and 0.886 (MUZE) vs. 0.236 (KGE) MRR for relation prediction. Note that MUZE performs zero-shot inference on these datasets. These results show that MUZE's inference is different from training a KGE model on the inference graph.


MUZE is a GNN-based KGFM

The paper does not write it like this, however, but rephrases the gradient-based training process of KGE models with GNN-terminology (e.g., random initialization becomes random node embeddings, gradient computation becomes message computation/aggregation, optimizer step becomes embedding update) to make it look like a KGFM.

The paper rephrases well-known techniques using a different terminology and relabels it as something new. I consider this unethical behavior.

MUZE is a GNN-based KGFM, and thus, the GNN terminology describes its actual computations. MUZE is an MPNN that couples message passing with decoding via a KGE scoring function (Lines 16-22, 54-59, 70-71, 112-114, 142-145, and 184-199). Its message functions are analytically derived from the gradients of a KGE loss defined using a parameterized scoring function, while its MLP-based update functions compute the representations from the aggregated messages (Eqs. (4)-(6)). Together, these components form a neural architecture that serves as a KGFM, not a terminological rephrasing of the standard KGE training process. By using the same scoring function to derive the messages in encoding and to score the resulting representations in decoding, MUZE produces representations aligned with its decoder (Lines 197-199 and 228-229).


MUZE Makes Significant Progress Towards KGFMs

In short, the paper does not make any progress toward KGFMs and, in fact, does not even propose a new method.

Does not make any progress toward KGFMs and, in fact, does not even propose a new method.

MUZE is the first query-agnostic KGFM. While existing KGFMs re-encode the entire KG for every query (Lines 42-49 and 94-102), MUZE encodes each KG once and reuses the embeddings across queries (Lines 50-52 and 59-61). This architectural shift accelerates inference by 11x over the fastest baseline and 1389x over the most accurate baseline (Table 2), while achieving competitive performance in entity prediction and establishing new state-of-the-art performance in relation prediction (Table 1). On Wikidata-5M, with approximately 5 million entities and 20 million triplets, MUZE achieves an MRR of 0.291 in 9 minutes, whereas ULTRA achieves 0.174 in 120 minutes and TRIX and FLOCK do not finish within 24 hours (Table 3). Also, while existing KGFMs cannot be directly applied to tasks other than KG completion, MUZE can perform zero-shot entity alignment (Table 7 in the submitted version; Table 8 in the revised version), broadening the scope of tasks a KGFM can handle.


We hope this clarification resolves the misunderstanding about our paper.

We noticed that the review was updated. Below, we respond to the newly added comments.


The authors argued in the discussion that the use of a small, trained MLP in step 3 is the main novelty of this paper. This is at odds with the entire positioning of the paper;

We did not argue that a trained MLP is the main novelty of our paper. The discussion was not about novelty; we were simply explaining why the reviewer's claim that MUZE does "exactly the same thing" as KGE training does not hold. We chose the gated residual refinement in Eq. (6), which consists of multiple MLPs, as the most direct counterexample where the difference is immediately visible. Providing a simple counterexample to directly refute an equivalence claim does not mean we are claiming it as our main novelty.

The main novelty of MUZE lies in an architectural shift for zero-shot KG reasoning: from per-query encoding to query-agnostic encoding. Existing KGFMs support inference with unseen entities and relations but require per-query encoding, whereas classical KGE models utilize query-agnostic embeddings for scalable inference but require separate training on each KG. MUZE, the first query-agnostic KGFM, combines both strengths by using the gradients of a shared, learned KGE scoring function as messages in the encoder and the same function as the decoder.

This architectural shift provides concrete empirical benefits. Inference becomes substantially more scalable than in existing KGFMs (Lines 61-66; Tables 2-3), and a single pre-trained model supports both entity and relation prediction and transfers to entity alignment without additional training, whereas existing KGFMs are trained separately for each task (Lines 76-78 and 253-256). MUZE thus paves the way for scalable, general-purpose KGFMs.


it constitutes a form of learning to optimize for KGE models.

MUZE is not trained to optimize a given KGE objective but is formulated for end-to-end link prediction. Its scoring and update functions are learned jointly on triplets held out from message passing (Lines 238-242 and Appendix B.2), using a prediction loss distinct from the KGE loss that defines the encoder's messages (Eq. (1)).


We respectfully ask that the paper be assessed on its formulation and contributions, not on a claim we did not make.

I agree with the authors that their approach is not /exactly/ the same as learning KGE models, and I toned down the respective comments in the review. The approach also may add something valuable to KGE training (such as requiring less epochs or preventing overfitting).

I disagree with the positioning of the paper, however, as the relationship to KGE training is not clearly exposed. The authors were unwilling to clearly acknowledge this relationship in the discussion, too. If one accepts the proposed method as a KGFM for inductive link prediction, one would have to accept other transductive link predictions methods as well.

PS: App B.2, which the authors mention in the response, is also puzzling: According to B.2, the training process actually uses mini-batch GD instead of GD. The latter corresponds to the GNN interpretation given in the main paper, whereas the former corresponds to KGE training.

Reviewer_WV8kOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the inference latency of zero-shot Knowledge Graph Foundation Models (KGFMs) due to computationally expensive, query-dependent message passing. The proposed method decouples encoding from decoding by formulating the forward pass as a gradient optimization step, generating query-agnostic embeddings for unseen graphs. This approach has achieved a considerable speedup in inference over the baselines.

Critical strengths
  • Formulating the message-passing step as a gradient descent step on a KGE scoring function is an innovative architectural choice, and this allows constructing query-independent embeddings for any unseen graph.

  • The decoupling of query-agnostic KG encoding from KGE-based decoding effectively resolves a major latency bottleneck in scalable graph models.

  • MUZE allows both zero-shot entity prediction and relation prediction using a single pre-trained model, unlike the baselines that require maintaining separate weights for different graph tasks.

Critical weaknesses

1- Theorem 1 lacks theoretical novelty, as it simply recontextualizes the classical universal approximation theorem [1] for MLP within a KG framework. The proof bypasses the gradient-based message-passing mechanism entirely and uses a single MLP. Proving that an MLP can memorize a continuous mapping over a finite, discrete set of distinguishable points is a known mathematical triviality.

2- The claim that embedding relations and representing them as a graph is a primary novelty of MUZE is factually incorrect. Prior work in scalable GFMs, specifically ULTRA [2], does this exact approach by building relational representations conditioned on their interactions.

3- The authors' claim that all previous KGFMs focus exclusively on knowledge graph completion is false. Recent prompt-based GFMs and systems like the KGFR [3] explicitly target a diverse array of tasks.

4- While inference is highly optimized, the training process requires backpropagating through a computational graph that itself consists of gradient operations. Computing these second-order derivatives requires retaining massive intermediate activation buffers across all KK layers, creating a severe GPU memory bottleneck during pre-training that is completely excluded from the complexity analysis.

5- The ablation studies are critically narrow in scope. Although the paper evaluates scaling behavior with respect to embedding dimensions and the number of pre-training datasets, it omits structural ablations entirely. There is no empirical analysis that justifies the necessity of the Adam-style moment statistics over standard message aggregation. Also, there is no evaluation of the sensitivity of performance to the number of recursive layers (KK).

6- The paper's claims regarding inference scalability are incomplete because they focus solely on wall-clock latency and ignore the substantial memory overhead of the decoupled encode-decode architecture. For fast decoding, MUZE must store the generated dense embeddings for all entities and relations in active memory. For large-scale knowledge graphs, caching this large embedding matrix requires immense memory, which limits the maximum graph size it can evaluate, compared to query-dependent baseline models that compute local representations on the fly.

[1] Hornik, K., Stinchcombe, M., & White, H. (1989). Multilayer feedforward networks are universal approximators. Neural Networks, 2(5) [2] Galkin, Mikhail, et al. "Towards foundation models for knowledge graph reasoning." ICLR 2024 [3] Yuanning Cui, et al. "KGFR: A Foundation Retriever for Generalized Knowledge Graph Question Answering." IEEE Transactions on Knowledge and Data Engineering, 2026

Questions for authors

1- Given that the proof for Theorem 1 requires bypassing the core message-passing updates entirely, how does this theoretical result validate the specific architectural contributions of MUZE rather than just validating the presence of an MLP?

2- Can the authors provide a transparent breakdown of the wall-clock time and peak memory consumption required for the pre-training phase of MUZE on the three base KGs, and how does this computational cost compare to training ULTRA or FLOCK?

3- Why is MOTIF excluded from the relation prediction evaluation in Table 1? A complete and rigorous comparison against all capable baselines is required.

2 comments
AuthorsOpenReview ↗

Response to Reviewer WV8k (1/2)

An MLP Alone Is Insufficient for Theorem 1

W1. Theorem 1 lacks theoretical novelty, as it simply recontextualizes the classical universal approximation theorem [1] for MLP within a KG framework. The proof bypasses the gradient-based message-passing mechanism entirely and uses a single MLP. Proving that an MLP can memorize a continuous mapping over a finite, discrete set of distinguishable points is a known mathematical triviality.

The key condition in Theorem 1 is not only the MLP but also the distinguishability of the initial representations. MUZE satisfies this condition almost surely via random initialization, whereas ULTRA, MOTIF, and TRIX, which also use MLPs, have limited distinguishability by design [4,5,6]. Thus, although Theorem 1 follows directly from the universal approximation theorem [1] (stated explicitly in Section 5.1 of the revised manuscript), it provides a meaningful distinction in expressivity between MUZE and these KGFMs. Note that simply adding random features is not always helpful in practice; we discuss this and the architectural implications of Theorem 1 in our response to Q1.


Theorem 1 Provides a Theoretical Basis for Random Initialization

Q1. Given that the proof for Theorem 1 requires bypassing the core message-passing updates entirely, how does this theoretical result validate the specific architectural contributions of MUZE rather than just validating the presence of an MLP?

Theorem 1 requires distinguishable initial representations, providing a theoretical basis for random initialization in MUZE. Since the proof does not involve message passing, we validate its role empirically. In our new ablation (added in Section 6.5 of the revised manuscript), replacing MUZE’s random initialization with a shared learnable vector for all entities and another for all relations reduces entity prediction MRR from 0.401 to 0.296 and relation prediction MRR from 0.919 to 0.856. Note that simply adding random features is not always helpful: in ULTRA’s ablation study, random initial features do not outperform all-ones features (Table 3 in [2]). These results indicate that, while Theorem 1 justifies random initialization, MUZE’s message passing is what makes it effective in practice.


MUZE Performs Query-Agnostic Encoding Without Relation Graphs

W2. The claim that embedding relations and representing them as a graph is a primary novelty of MUZE is factually incorrect. Prior work in scalable GFMs, specifically ULTRA [2], does this exact approach by building relational representations conditioned on their interactions.

We do not claim that a primary novelty of MUZE is to embed relations and represent them as a graph. A novelty of MUZE is that it computes query-agnostic representations for entities and relations, which can be reused across queries once computed. Also, unlike ULTRA or TRIX, which explicitly construct a relation graph and compute representations on it, MUZE does not construct the relation graph. MUZE directly performs message passing over both entities and relations and updates them simultaneously, with messages derived from the gradients of a KGE scoring function. For further clarification, we have revised Section 5.1, changing “Existing KGFMs ... do not produce embeddings” to “Existing KGFMs ... do not produce embeddings agnostic to KG completion queries”.


Our Scope Is KGFMs That Rely Solely on KG Structures

W3. The authors' claim that all previous KGFMs focus exclusively on knowledge graph completion is false. Recent prompt-based GFMs and systems like the KGFR [3] explicitly target a diverse array of tasks.

Following prior work [2,4,5,6], we use the term “KGFMs” for models whose predictions depend only on the graph structure, not on the names or identities of entities and relations. Under this definition, existing KGFMs, including ULTRA, TRIX, MOTIF, FLOCK, and KG-ICL[7], are designed only for KG completion. Models using LLMs, such as KGFR, require textual information, e.g., LLM-generated relation descriptions, so their predictions can draw on the knowledge that language models store, rather than solely on the graph structure. Thus, we do not compare with models using LLMs. Nevertheless, we have added the integration of LLMs with MUZE as a future direction in Section 7 of the revised manuscript, with a reference to KGFR[3].


[1] Multilayer feedforward networks are universal approximators, Neural Networks 1989.
[2] Towards foundation models for knowledge graph reasoning, ICLR 2024.
[3] KGFR: A Foundation Retriever for Generalized Knowledge Graph Question Answering, TKDE 2026 October.
[4] TRIX: A More Expressive Model for Zero-shot Domain Transfer in Knowledge Graphs, LoG 2024.
[5] How Expressive are Knowledge Graph Foundation Models?, ICML 2025.
[6] Flock: A Knowledge Graph Foundation Model via Learning on Random Walks, ICLR 2026.
[7] A Prompt-Based Knowledge Graph Foundation Model for Universal In-Context Reasoning, NeurIPS 2024.

AuthorsOpenReview ↗

Response to Reviewer WV8k (2/2)

MUZE Has a Lower Training Cost than FLOCK

W4. While inference is highly optimized, the training process requires backpropagating through a computational graph that itself consists of gradient operations. Computing these second-order derivatives requires retaining massive intermediate activation buffers across all KK layers, creating a severe GPU memory bottleneck during pre-training that is completely excluded from the complexity analysis.

Q2. Can the authors provide a transparent breakdown of the wall-clock time and peak memory consumption required for the pre-training phase of MUZE on the three base KGs, and how does this computational cost compare to training ULTRA or FLOCK?

As reported in Appendix B.2, pre-training MUZE on the three KGs takes 13.5 hours with 20GB of peak GPU memory on a single 24GB RTX 3090 GPU, whereas FLOCK typically takes about three days with 28GB on a 48GB A6000 GPU (Appendix D, E in [6]). Note that MUZE can perform both entity and relation prediction with a single 13.5-hour training run, while FLOCK requires a separate training run for each task. Since the gradients of MUZE's scoring function admit closed-form expressions, we implement the messages as explicit functions of entity and relation representations, as in standard MPNNs. Thus, training MUZE uses first-order differentiation of its closed-form message functions, without explicitly constructing Hessian matrices of the underlying scoring function.


We Added the Suggested Ablation and a Layer Sensitivity Analysis

W5. The ablation studies are critically narrow in scope. Although the paper evaluates scaling behavior with respect to embedding dimensions and the number of pre-training datasets, it omits structural ablations entirely. There is no empirical analysis that justifies the necessity of the Adam-style moment statistics over standard message aggregation. Also, there is no evaluation of the sensitivity of performance to the number of recursive layers (KK).

Section 6.5 of the submitted manuscript includes structural ablations: (i) removing MLPscale\text{MLP}_\text{scale} (ii) removing MLPgate\text{MLP}_\text{gate} and (iii) removing the entire gated residual refinement. We have added the suggested ablation in our revised manuscript. Removing the Adam-style moment statistics drops entity prediction MRR from 0.401 to 0.349 and relation prediction MRR from 0.919 to 0.896.

Also, we have added a sensitivity analysis to the number of recursive layers (KK), from 8 to 14 in steps of 2, in Section 6.3 of the revised manuscript. The results are as follows:

8101214
Entity prediction0.3890.3930.4010.390
Relation prediction0.9140.9160.9190.920

The performance is robust to the recursive depth. Across the tested depths, the average entity prediction MRR remains competitive with the best baseline (0.391), while the average relation prediction MRR exceeds the best baseline (0.881).


Reported Memory Includes Embeddings

W6. The paper's claims regarding inference scalability are incomplete because they focus solely on wall-clock latency and ignore the substantial memory overhead of the decoupled encode-decode architecture. For fast decoding, MUZE must store the generated dense embeddings for all entities and relations in active memory. For large-scale knowledge graphs, caching this large embedding matrix requires immense memory, which limits the maximum graph size it can evaluate, compared to query-dependent baseline models that compute local representations on the fly.

Query-dependent baselines also require the large embedding matrix for all entities and relations, as their predictions rely on decoders that operate directly on query-specific entity and relation embeddings. Additionally, they require computing the large embedding matrix for every query, whereas MUZE only needs to compute it once. Our time and memory comparisons in Tables 2 and 3 include the cost required for computing embeddings, where we show MUZE requires less memory and significantly less time for inference. For example, on Wikidata-5M containing approximately 5M entities and 20M triplets, MUZE requires 92GB of memory to compute the entity and relation representations and use them for inference, achieving 0.291 MRR, while ULTRA requires 101GB to achieve 0.174 MRR.


MOTIF Is Designed for Entity Prediction, Not Relation Prediction

Q3. Why is MOTIF excluded from the relation prediction evaluation in Table 1? A complete and rigorous comparison against all capable baselines is required.

MOTIF is excluded from the relation prediction evaluation because it does not perform relation prediction in its original paper[5]. MOTIF is designed for predicting a missing entity in a query, not a missing relation.


[5] How Expressive are Knowledge Graph Foundation Models?, ICML 2025.
[6] Flock: A Knowledge Graph Foundation Model via Learning on Random Walks, ICLR 2026.

Reviewer_ntq2OpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper propose a new method for Knowledge graph foundation models. Authors notice that previous knowledge graph foundation models as a significant computational overhead, because they have to execute message passing over the entire knowledge graph for a very single query. Inspired by the high efficiency of knowledge graph embedding methods, Authors propose To construct query independent entity and relation embeddings from random initialization through recursive message passing, during which the gradient from knowledge graph embedding score function are regarded as one of the components of the message during aggregation. Designed in this way, the knowledge graph foundation model is much more efficient than existing solutions. The proposed method is called MUSE. Experiments show that MUSE is much faster than the baselines.

Critical strengths
  1. The motivation of the paper is quite strong. Improving the efficiency of existing knowledge graph foundation models is a worthwhile research direction.
  2. Experiment results show that USE is much faster than baselines on entity predictions over many knowledge graphs, especially large scale knowledge graphs such as Wikidata-5M.
  3. The average performance of MUSE on the zero-shot entity and relation prediction over 54 knowledge graphs is better than baselines.
Critical weaknesses
  1. The solution of MUSE that regarding the gradient of knowledge graph embedding score function to form the message during graph aggregation is interesting. But as I understand, one layer of graph aggregation in MUSE is approximately equal to do one iteration of training over the whole KG according to knowledge graph embedding score function, since during each aggregation layer, the representation of entities and relations will be updated according to the score function gradient. Thus, it would be better to compare the results of directly training the knowledge graph embedding for K iterations on each knowledge graph, where k is the number of layers in MUSE.

  2. After getting the entity embedding and relation embedding for the whole knowledge graph, The influence of muse is quite fast. But I would suppose it will take some time to get the entity embedding and relation embeddings, even though these computation only contact for once.

Questions for authors
  1. Is it possible to compare the results of directly training the knowledge graph embedding for k iterations on each knowledge graph?

  2. How long it would take to get the entity embedding and relation embeddings for each dataset?

  3. In table 3, it is reported that MUSE takes 9 minutes to finish the prediction on wikidata-5M, is the 9 minutes only include the inference time, which means using the entity embedding and relation embeddings to do entity prediction? Is the time of pre-computing the entity embedding and relation embeddings included in 9 minutes?

1 comment
AuthorsOpenReview ↗

Response to Reviewer ntq2

We Added the Suggested Comparison with KGE Training

W1. The solution of MUSE that regarding the gradient of knowledge graph embedding score function to form the message during graph aggregation is interesting. But as I understand, one layer of graph aggregation in MUSE is approximately equal to do one iteration of training over the whole KG according to knowledge graph embedding score function, since during each aggregation layer, the representation of entities and relations will be updated according to the score function gradient. Thus, it would be better to compare the results of directly training the knowledge graph embedding for K iterations on each knowledge graph, where k is the number of layers in MUSE.

Q1. Is it possible to compare the results of directly training the knowledge graph embedding for k iterations on each knowledge graph?

Following the reviewer’s suggestion, we train a KGE model with MUZE’s scoring function for K=12K=12 epochs. We conduct this comparison on the 13 transductive evaluation KGs, training the KGE baseline on each dataset’s training split. MUZE is evaluated in a zero-shot manner using its pre-trained checkpoint with K=12K=12 encoder layers, without dataset-specific finetuning.

The average MRRs show a substantial gap: 0.022 (KGE) vs. 0.331 (MUZE) for entity prediction, and 0.236 (KGE) vs. 0.886 (MUZE) for relation prediction. This indicates that one layer of MUZE goes beyond one iteration of KGE training. While MUZE’s messages are derived from KGE gradients, MUZE learns update functions that utilize the aggregated messages to effectively update the representations. The per-KG results are provided in Table 21 in Appendix D of the revised manuscript.


Encoding Time Is Included in Reported Inference Times

W2. After getting the entity embedding and relation embedding for the whole knowledge graph, The influence of muse is quite fast. But I would suppose it will take some time to get the entity embedding and relation embeddings, even though these computation only contact for once.

Q2. In table 3, it is reported that MUSE takes 9 minutes to finish the prediction on wikidata-5M, is the 9 minutes only include the inference time, which means using the entity embedding and relation embeddings to do entity prediction? Is the time of pre-computing the entity embedding and relation embeddings included in 9 minutes?

Q3. How long it would take to get the entity embedding and relation embeddings for each dataset?

All reported times of MUZE, including those for entity prediction on the 54 KGs (Table 2) and on Wikidata-5M (Table 3), include the time for computing the entity and relation embeddings. MUZE’s speedups over the fastest baseline, 11x on the 54 KGs and over 13x on Wikidata-5M, already account for the encoding time. Across the 54 KGs, encoding takes 2 minutes 49 seconds in total, and the per-KG times are provided in Table 18 in Appendix C of the revised manuscript.

Comments on the paper

2 comments

Thank you for your reply. We first summarize our responses to the three points in your comment:

  • MUZE differs from KGE training in how the representations are updated, and the valid connections between them are already stated throughout the paper.
  • Reusing embeddings across queries is a KGE property that MUZE is designed to retain.
  • Recomputing representations when a KG changes is naturally required for any KG model.

Below, we address each point in detail.


The proposed method does exactly the same thing: [...] This relationship is not exposed in the paper, which is why I consider the paper misleading.

Sharing the five-step structure does not imply that MUZE "does exactly the same thing" as KGE training. At a high level, standard MPNNs also follow this five-step structure: initialization, message aggregation, representation update, iteration over layers, and decoding. Therefore, MUZE and KGE training should be compared not by this high-level structure alone but by how each step is actually computed.

Random initialization (step 1) and iteration over layers or epochs (step 4) are common to MUZE and KGE training, but they are also well-established GNN techniques. Since MUZE is designed to derive its messages from the gradients of the KGE loss and decode with the same scoring function used in that loss, message computation (step 2) and decoding (step 5) are common to MUZE and KGE training.

The key difference lies in the representation update (step 3), which determines how the messages are used to compute the entity and relation representations. In KGE training, each update is an optimization step on the KGE loss. In MUZE, on the other hand, the KGE loss defines only the messages, and the MLP-based update functions determine how these messages are used to update the representations (Eqs. (5)-(6)). For example, Eq. (6) applies a learned, gated nonlinear transformation to the intermediate representation. This transformation takes only the intermediate representation as input, using neither the KGE loss nor its gradient, and therefore does not correspond to a KGE optimization step. The reviewer's argument nevertheless treats the entire update, including Eq. (6), as a "custom optimizer", which oversimplifies the computation that MUZE performs.

Taken together, MUZE is related to KGE training mainly through the message computation and the shared scoring function that bridges encoding and decoding (steps 2 and 5), rather than through the procedure as a whole. These connections are already described throughout the paper (Lines 16-22, 54-59, 112-114, 142-145, 156-161, and 196-198). Describing the whole procedure as KGE training would obscure how MUZE computes the representations used for prediction.


Finally, observe that "MUZE encodes each KG once and reuses the embeddings across queries" also holds for KGE models if one treats MUZE forward inference = KGE training.

KGE models reuse embeddings across queries, and this is the property MUZE is designed to retain (Lines 87-92). Sharing this property does not imply that MUZE's forward inference is KGE training.


And in fact, MUZE needs to rerun everything as soon as anything in the KG changes.

When the KG changes, MUZE only needs to rerun its forward pass; none of its parameters is retrained. Such recomputation is naturally required for any KG model.


We hope this clarifies the difference between MUZE and KGE training, and we are happy to discuss any remaining points you may have.

Dear reviewers,

The authors have submitted their rebuttals. Please take a look and interact with the authors if necessary.

Thanks a lot.

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.