We sincerely thank the reviewer for the detailed review.

Preamble

Before addressing each specific point, we would like to briefly clarify the research problem our paper tackles and the corresponding contributions we aim to make. Understanding this framing helps contextualize the design choices and experimental methodology.

Research problem

Our work focuses on extracting knowledge from large-scale knowledge graphs (KGs) through embeddings, with the goal of enriching downstream tabular data to boost performance in supervised learning tasks (e.g., regression and classification). Unlike most prior work, centered on knowledge graph completion (KGC) via link prediction, we target a different application: downstream feature enrichment using KG embeddings.

Recent findings [1] have shown that strong performance on KGC does not correlate with improved performance on downstream predictive tasks. Despite this, most of the KGE literature continues to prioritize KGC as the sole benchmark, with limited attention to how the learned embeddings transfer to practical ML tasks beyond the KG itself.

Our aim is thus not to propose yet another KGC method, but rather to design a method tailored to the demands of downstream prediction tasks. In this context, scalability is not an end in itself, but a necessary requirement to unlock the predictive power of large general-purpose KGs in downstream analyses.

[1] Daniel Ruffinelli and Rainer Gemulla. Beyond link prediction: On pre-training knowledge graph embeddings. In Proceedings of the 9th Workshop on Representation Learning for NLP (RepL4NLP-2024), 2024.

Contributions

1. We theoretically argue why traditional KGE models, optimized for KGC via local contrastive learning, are not well-suited for downstream classification/regression tasks (see lines 266–270).
2. We show that KGC and downstream learning objectives are fundamentally misaligned: KGC emphasizes local discriminative contrasts, while downstream learning benefits from globally consistent embeddings across the graph.
3. We propose SEPAL, a method designed to maximize this global consistency, and we theoretically analyze its propagation step to support this claim.
4. Through an extensive experimental study across 7 large-scale KGs and 46 downstream tasks, we demonstrate that SEPAL outperforms standard KGE methods by a large margin (on average +30-35% in downstream performance).
5. Finally, we show that SEPAL can scale to ultra-large graphs (e.g., WikiKG90Mv2 with 91M nodes) using a single 32GB GPU, and that using such large KGs is beneficial for downstream tasks by enabling richer feature enrichment.

Specific points

We now address each of the reviewer’s concerns in detail.

W1. “Cost arguments not convincing”; “not clear if there is a need for another method”

Our goal is not to reduce cost for link prediction, but to introduce a method specifically optimized for downstream regression/classification, a setting largely unexplored by existing scalable KGE methods. This justifies the need for another method.

While some prior works (e.g., Marius) scale KGC efficiently, they still rely on local contrastive training (with negative sampling), which is ill-suited for learning globally consistent embeddings, a key requirement for downstream tasks.

SEPAL offers a new optimization procedure tailored for this setting, and we demonstrate that it scales easily to ultra-large KGs (e.g., WikiKG90Mv2) on a single GPU, without complex distributed setups or memory hierarchy tuning, unlike traditional KGE pipelines.

W2-1. Theoretical analysis of the propagation

Our theoretical analysis proves that, in the case of DistMult, SEPAL minimizes a metric of embedding alignment. Indeed, the proposed energy is a measure of the “amount of alignment” in the embedding space. The equivalence between SEPAL’s propagation and mini-batch projected gradient descent provides the guarantee of converging to a stationary point of this energy with embeddings constrained on the unit sphere.

This energy is indeed not a suitable objective for link prediction, but our theoretical analysis on the queriability of embeddings (lines 258-270) indicates that it is a suitable quantity to minimize in order to perform well on downstream regression/classification tasks. Indeed, downstream learners require globally aligned embeddings to be able to extract meaningful patterns even between the embeddings of distant nodes. Our experimental results show that SEPAL achieves top performance for downstream tasks, and thus confirm these theoretical insights.

For other base embedding models, our analogy to Arnoldi-like iterations (lines 254-257 and Appendix D.1) can be adapted, and suggests that the embeddings converge toward generalized eigenvectors of an operator that captures both global graph structure and relation embeddings.

W2-2: Comparison to Albooyeh et al.

Albooyeh et al. propose an aggregation that is similar to SEPAL’s aggregation during the propagation phase, however the two methods are in no way equivalent, as they optimize the embeddings in two very distinct ways:

• Albooyeh et al. introduce propagation within the standard link prediction pipeline: during training, for each triple $(v, r, u)$, they occasionally (with probability $p$) replace one entity’s embedding with an aggregated version (e.g., $\theta_u \cdot \theta_r$​) before computing the score. However, training still relies on negative sampling and a classic link prediction loss, so it continues to optimize for local triple-level contrasts.

• SEPAL, in contrast, explicitly separates the optimization objective: embeddings for a small core are trained with a classic KGE objective, and then relation-aware propagation is used across the rest of the graph, without negative sampling. This distinction is crucial: SEPAL removes the need for negative sampling on 95-99% of the graph, enabling both improved scalability and alignment properties beneficial for downstream regression/classification.

W2-3: Why BLOCS is needed

BLOCS enables GPU-based propagation, which is crucial for scalability. Without it, propagation must run on CPU and becomes prohibitively slow. To illustrate this, on YAGO4.5, we tried to run CPU-based propagation, which did not finish after 24 hours, while with BLOCS, the GPU version completes in 2.5 hours.

W3: Clarify experimental setup

We thank the reviewer for the opportunity to clarify this point. In the final version, we will include a table detailing the hyperparameter ranges explored for each dataset, along with the number of training configurations tested per KG. Regarding the underlying KGE method, we evaluated three standard training objectives: margin ranking loss, binary cross-entropy, and cross-entropy. We found cross-entropy to yield the best performance, and used it consistently for both SEPAL core training and the DistMult baseline in the reported results.

W4-1: Choice of baselines

We respectfully emphasize that our goal is not to improve link prediction performance or compete with recent KGE methods on that task. As stated in the preamble, SEPAL is designed specifically for downstream feature enrichment, where the goal is to generate embeddings that boost performance on regression/classification tasks, not link prediction.

We compare against DGL-KE and PyTorch-BigGraph because they are widely used, scalable KGE systems that represent the standard approach in real-world large-scale settings. While newer methods exist, they are generally optimized for link prediction and often rely on complex or resource-intensive training schemes (e.g., advanced negative sampling or query embedding). These methods are not optimized for our task and, as prior work [1] shows, strong link prediction does not necessarily translate to strong downstream performance.

W4-2: “no inductive method discussed nor compared to”

Our experiments already include NodePiece, an inductive method that can scale up to YAGO4.5 (32M entities).

Inductive capabilities can be valuable in continual learning scenarios (i.e., dynamically evolving KGs). In this use case, SEPAL already supports semi-inductive embedding computation (as noted in our response to Reviewer aZkD).

The method cited by the reviewer (Cui et al., NeurIPS 2024) does not scale to the size of the KGs we target, and to our knowledge, no existing inductive KGE method scales to the size of graphs we consider. We remain open to including such baselines should they exist.

W4-3: SEPAL performs better on downstream tasks than link prediction

We emphasize that the goal of SEPAL is not to cheaply optimize link prediction, but to learn embeddings that are better suited for downstream regression/classification (see preamble and response to W2-1). The propagation step is designed to maximize embedding consistency across the graph, which we argue and show benefits downstream tasks more than traditional KGE objectives.

Thank you for your response.

New experiments

First, we bring more empirical evidence of SEPAL’s advantages over prior methods.

Comparison to SOTA link prediction methods for large-scale KGs

To strengthen our empirical evaluation, we added two strong large-scale baselines:

• GraSH [2], an efficient hyperparameter optimization framework for large-scale KGEs.

• SMORE [3], a scalable KGE method supporting single-GPU training and multi-hop reasoning.

Both were trained with DistMult as the base embedding method, on Freebase, using the authors’ released configurations. We report the normalized $R^2$ scores on four real-world regression tasks, along with total training time.

We trained SMORE for 1 million iterations on one GPU, following the authors’ configuration. Its relatively low performance here suggests that longer training could improve results, but under a 6-hour budget, SEPAL is substantially better.

GraSH optimizes hyperparameters for link prediction using successive halvings to discard unpromising configurations at low cost. Results show that, after 33 hours of hyperparameter search on one GPU, GraSH produces better embeddings than other baselines. However, SEPAL remains the best performer on all tasks, and also the fastest method. We will include these new results in the final version of the paper.

[2] Adrian Kochsiek, Fritz Niesel, and Rainer Gemulla. Start small, think big: On hyperparameter optimization for large-scale knowledge graph embeddings. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2022.

[3] Hongyu Ren, Hanjun Dai, Bo Dai, Xinyun Chen, Denny Zhou, Jure Leskovec, and Dale Schuurmans. Smore: Knowledge graph completion and multi-hop reasoning in massive knowledge graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.

Comparison to Albooyeh et al. (DistMult-ERAvg)

To show the novelty of our approach compared to Albooyeh et al. we run their DistMult-ERAvg on Mini YAGO3 (129k entities, 1.1M triples). DistMult-ERAvg is not optimized for large graphs and fails with out-of-memory errors on larger graphs.

The table above reports performance and runtime on Mini YAGO3, showing that SEPAL is 32 times faster than DistMult-ERAvg while achieving consistently better scores. This is not surprising since DistMult-ERAvg follows the classic optimization loop with negative sampling, gradient computations, and parameter updates, and therefore inherits the limitations of traditional KGE methods. The strength of DistMult-ERAvg lies in out-of-sample embedding computation, which SEPAL also supports (see experiment conducted in response to Reviewer aZkD), but with much greater scalability.

If accepted, we will:

• Add a brief discussion of Albooyeh et al. in Section 2.1 (page 3)
• Include a detailed comparison of the two methods in Appendix G, together with the empirical results above.

Discussion

More explanations on propagation

• Why not apply this to the core?

We need negative sampling for the core training because otherwise the embeddings could collapse to a single point (e.g., in DistMult, all entity embeddings identical and all relation embeddings as vectors of ones would minimize the objective). However, once we have learned representations for the relations and the core entities, we can use them to propagate without negative sampling: they act as (fixed) boundary conditions and prevent collapse in the rest of the graph (lines 241-244).

• On quality vs. scalability

Propagation presents both advantages of being good for downstream tasks and computationally efficient. For this reason, in the paper, quality and scalability arguments are sometimes mixed. Section 4, however, is dedicated solely to explaining the quality aspect.

Why we need BLOCS

Indeed, our propagation algorithm is message-passing-based, like a GNN, but with no learnable weights. BLOCS is specifically tailored for the requirements of our method.

• Why not apply prior GNN scaling techniques?

Prior large-scale GNN methods (e.g. MariusGNN) scale by partitioning the graph and processing partitions one by one. Real-world large-scale graphs are power-law graphs, and for these graphs, standard partitioning methods either produce partitions with multiple connected components or with no size control (Appendix E.3., Figure 11, page 32).

For classic GNNs, operating on several connected components during training is not a problem: it is still possible to sample neighborhoods for each vertex, and use the nodes’ vector representations to train the GNN.

In SEPAL, however, 95 to 99% of nodes are outer entities with zero-initialized embeddings, and the only source of signal during propagation is the core. Therefore, if a connected component contains only outer entities, no propagation is possible.

BLOCS addresses this by producing subgraphs that are connected, bounded in size (to fit in GPU memory), and well connected to the core (Appendix E.5, Figure 14, page 35).

• Why is CPU propagation slower?

On YAGO4.5, CPU propagation took 37 hours vs. 2.5 hours on GPU with BLOCS. Each propagation step processes millions of triples, requiring elementwise multiplication (DistMult) and normalization per embedding. These operations are heavily parallelizable and far faster on GPU than CPU.

Conclusion

We hope this discussion has at least partly resolved your concerns regarding our method and increased your confidence in its originality and ability to perform significantly better than prior work on downstream tasks.

We thank you for your thoughtful feedback, which prompted us to further demonstrate SEPAL’s capabilities in its target domain (downstream regression/classification tasks from large-scale knowledge graphs).

Evaluation on prior benchmark (Ruffinelli et al. [1])

Ruffinelli et al. [1] propose a benchmark for evaluating KGE methods on downstream classification and regression. It includes several KGE baselines and the state-of-the-art GNN KE-GCN for entity classification. For each KG (FB15k-237, YAGO3-10, Wikidata5M), they evaluate embeddings on downstream tasks created from entity attributes of the KG.

We originally did not include this benchmark because our goal was to evaluate external, real-world tasks (Fig. 2, p. 8) that are independent of a specific KG, to compare the benefits of diverse KGs. In contrast, the Ruffinelli et al. tasks are artificially created and associated with specific KGs that are orders of magnitude smaller than those in our main study.

However, we agree that evaluating SEPAL on these datasets complements our main experiments and enables direct comparison with prior work. We used 128-dimensional embeddings to match one of the dimensions in Ruffinelli et al.’s hyperparameter search space. We also used the authors’ released evaluation script for comparable results. In each table, we report:

1. The best KGE method for classification from [1]
2. The best KGE method for regression from [1]
3. KE-GCN results from [1]
4. SEPAL results

Table 1: Regression results on Wikidata5M (4.8M entities, 21M triples)

---

Table 2: Classification and regression results on YAGO3-10 (123k entities, 1M triples)

---

Table 3: Classification and regression results on FB15k-237 (14k entities, 272k triples)

The results show that, on YAGO3-10 and Wikidata5M, SEPAL achieves the best performance for both regression and classification, consistent with our main results on much larger KGs. On FB15k-237, SEPAL has weaker results, but this is not surprising given that FB15k-237 is very small (14k entities, 185 to 6500 times smaller than the graphs considered in our paper). For these tiny graphs, which fall outside SEPAL’s intended scope, our method is not adapted because the core becomes too small to learn good representations for the relations and core entities.

Thank you for your response!

We are currently finalizing additional experiments that directly address the points you raised, including comparisons to more baselines. The results will be ready and posted in the discussion within the next few hours. We wanted to ensure you are aware, so you have the opportunity to review them before finalizing your evaluation. Thank you for your understanding.

We thank the reviewer for their thoughtful and positive assessment of our work.

We are glad the review acknowledges the significant improvement in downstream task performance and the ability of SEPAL to scale to massive knowledge graphs using a single 32GB GPU.

Below, we address the reviewer’s comments in more detail.

1. Experimental design and task focus

In this work, our primary focus is on downstream feature enrichment, a setting where the goal is to learn entity embeddings from a knowledge graph and incorporate them as features into tabular datasets for regression or classification tasks. This setup enables the integration of external knowledge into practical ML pipelines (e.g., incorporating knowledge about cities to better predict housing prices).

This task differs substantially from link prediction and logical query answering, and requires different optimization objectives. Specifically, while link prediction focuses on distinguishing positive triples from corrupted negatives, encouraging local contrasts, downstream enrichment tasks benefit from global consistency across the graph, so that entities located far apart can still have semantically meaningful and comparable embeddings from which a downstream predictor can learn shared patterns. This distinction is discussed in detail in our analysis of embedding "queriability" (Section 4, page 7), where we provide theoretical justification for why long-range consistency is essential in our setting.

We also argue that SEPAL is well-suited to this objective. In Section 4 (lines 239–257), we provide theoretical arguments showing how our propagation-based approach fosters this global consistency. In contrast, traditional KGE methods rely on negative sampling during training, which increases optimization complexity and can distort long-range consistency by overemphasizing local contrast [1, 2].

To validate these theoretical insights, we conduct a large-scale empirical study spanning 46 downstream tasks over 7 large-scale KGs, and show that SEPAL consistently outperforms baselines, achieving 35% higher average performance than PBG and 30% higher than DGL-KE.

We agree with the reviewer that multi-hop inference is a compelling and valuable research direction. However, we believe that it falls outside the scope of this paper. Such settings typically require explicit modeling of logical queries during training and dedicated architectures for reasoning [3, 4], which are fundamentally different from our goal of scalable feature enrichment for general-purpose downstream tasks. We chose to focus our contributions on this under-explored setting, and we believe our results demonstrate strong practical relevance and theoretical grounding. Nevertheless, we agree that ideas from SEPAL could be adapted for multi-hop inference in future work.

If the paper is accepted, we will further clarify this distinction in the introduction and conclusion to avoid confusion regarding task scope.

[1] Erik Arakelyan, Pasquale Minervini, Daniel Daza, Michael Cochez, and Isabelle Augenstein. Adapting neural link predictors for data-efficient complex query answering. Advances in Neural Information Processing Systems, 2023.

[2] Pedro Tabacof and Luca Costabello. Probability calibration for knowledge graph embedding models. In International Conference on Learning Representations, 2020.

[3] Hamilton, W., Bajaj, P., Zitnik, M., Jurafsky, D., & Leskovec, J.. Embedding logical queries on knowledge graphs. Advances in Neural Information Processing Systems, 2018.

[4] Ren, H., & Leskovec, J.. Beta embeddings for multi-hop logical reasoning in knowledge graphs. Advances in Neural Information Processing Systems, 2020.

2. Link Prediction Performance on WikiKG90Mv2

Following the initial submission, we were able to substantially improve SEPAL’s MRR from 0.195 to 0.5291. This improvement was achieved by increasing the number of core training epochs (from 15 to 20), enlarging the batch size (from 8,192 to 16,384), and increasing the number of propagation steps (from 10 to 15). In comparison, PBG achieves an MRR of 0.6325, and DGL-KE achieves 0.3202.

That said, we emphasize that link prediction is not the target task for which SEPAL was designed (see Section 4, page 7, lines 266–270). SEPAL’s optimization is geared toward producing globally consistent embeddings that are well-suited for downstream regression and classification tasks, rather than optimizing local triple contrast through negative sampling, as in traditional KGE methods. As a result, as explained above, SEPAL’s performance for downstream regression and classification tasks is unmatched.

We sincerely thank the reviewer for the insightful feedback.

We are pleased to see the reviewer highlight the clear problem formulation, the comprehensive empirical evaluation across diverse knowledge graphs and downstream datasets showcasing the benefits of SEPAL, and the theoretical analysis supporting our method.

Below, we answer the reviewer’s questions and concerns in detail.

Q1: SEPAL for continual learning

SEPAL does not require rerunning the entire process if the graph is updated with new entities. New embeddings can be computed via a few additional propagation steps, as long as the relations remain unchanged.

To demonstrate this, we conducted an additional experiment using two versions of the YAGO3 knowledge graph:

• YAGO3-2014 (original release),
• YAGO3-2022 (revived version).

The table below gives the statistics of these datasets.

In the continual learning setting (SEPAL-CL), we:

• Initialized the embeddings of YAGO3-2022 using embeddings precomputed on YAGO3-2014,
• Propagated embeddings for just 5 steps to update existing nodes and embed new entities.

The table below compares the performance and runtimes of SEPAL-CL, SEPAL trained from scratch, and DistMult trained from scratch. We also include the performance obtained by SEPAL trained on the older YAGO-2014 dataset to show the benefit of updating the knowledge graph.

Table: Results of the continual-learning experiment, on the real-world downstream tasks.

We see that:

• For downstream applications, YAGO3-2022 brings value compared to YAGO3-2014 (for all methods, scores are higher than the strongest method on YAGO3-2014, SEPAL).
• SEPAL from scratch is 10$\times$ faster than DistMult.
• SEPAL-CL is 57$\times$ faster than SEPAL from scratch, and 587$\times$ faster than DistMult.
• SEPAL-CL clearly outperforms DistMult, and almost matches the performance of SEPAL trained from scratch, even in this very challenging scenario (8 years between the two versions of the graph), where the size of the graph has doubled in terms of entities, and tripled in terms of triples. In a real-life application, we could imagine embeddings recomputed monthly at very low cost.

We sincerely thank the reviewer for this insightful question, which motivated us to conduct this additional experiment. We genuinely believe that this study increased the impact of our method by demonstrating its applicability to continual learning settings.

Q2: Dependency on connectedness and connectivity

We thank the reviewer for raising this important question. SEPAL requires the input knowledge graph to be connected, but this is not a limiting assumption in practice: as shown in Table 2 (Appendix A, page 17), the largest connected component in real-world KGs typically accounts for nearly the entire graph.

Regarding graph density, SEPAL can handle a wide range. Table 2 (Appendix A, page 17) shows that we applied SEPAL to KGs with densities spanning several orders of magnitude (from $6 \times 10^{-8}$ to $1 \times 10^{-4}$). Across this spectrum, SEPAL consistently achieved the best performance on downstream tasks.

The primary impact of higher density is computational: denser graphs lead to denser core subgraphs, which can increase the time required for the core training phase. In such cases, it can be beneficial to slightly reduce the size of the core subgraph to maintain efficiency without significantly affecting performance.

W1-2: Reliance on the Appendix

Due to the strict 9-page limit, we moved detailed descriptions and ablations to the appendix to keep the main narrative focused and accessible. That said, we fully agree that improved self-containment in the main paper would aid readability.

Therefore, if the paper is accepted, we will use the additional page allowed to move the paragraph “High-level principle” of Appendix E.2 (pages 30-31), which describes BLOCS, to the end of section 3.1 in the final version of our paper. We will also summarize extra evaluation results in the main text to minimize back-and-forth. We believe these changes will significantly improve the clarity and accessibility of our contributions.

Paper formatting

We will address the paper formatting concerns raised by the review in the final version of the paper, and thank the reviewer for pointing them out.

We thank the reviewer for the thoughtful review, insightful suggestions, and positive feedback.

We are glad that the review recognizes the practical significance of the problem we address, the clarity and readability of our paper, and the effectiveness of our method, both empirically and theoretically.

Below, we address the specific comments made by the review.

1. BLOCS in the appendix

Due to space constraints, we placed the full description of the BLOCS algorithm in the appendix. However, we agree that including a high-level overview in the main paper would improve clarity and accessibility. If the paper is accepted, we will use the additional page to move the "High-level principle" paragraph from Appendix E.2 (pages 30–31) into the main body, specifically at the end of Section 3.1, to give readers a clearer understanding of BLOCS without needing to refer to the appendix.

2. Considering other centrality measures for core selection

Following the reviewer’s suggestion, we conducted an additional experiment where we replaced degree with PageRank for core selection (keeping all other hyperparameters unchanged). In our original design, we used node degree as the centrality measure because it is extremely efficient to compute, aligning with our emphasis on scalability. However, PageRank can also be computed very efficiently using sparse matrix multiplications.

The table below reports results on the real-world downstream tasks using normalized R² scores and training time (in parentheses).

Performance

Regarding performance, it seems that the difference between degree and PageRank depends on the graph’s structure. Specifically, we observe that for YAGO4, YAGO4+T, Freebase, and WikiKG90Mv2, PageRank improves the performance. This echoes the results of Figure 14 (Appendix E.5, page 35), which show that in these four specific KGs, contrary to the others, the degree-based core selection yields cores that are connected through fewer edges to some outer subgraphs. We can therefore conjecture that for these KGs, PageRank improves information flow and mitigates issues like oversquashing during propagation, ultimately increasing performance.

Cost

Regarding computational cost, we see that SEPAL with PageRank usually runs slightly faster than with degree. This is because PageRank yields slightly sparser cores, leading to faster core training.

We will include these findings, along with a brief analysis and discussion, in the final version of the paper.