Scalable Feature Learning on Huge Knowledge Graphs for Downstream Machine Learning
Authors: Félix Lefebvre
Gaël Varoquaux
Venue: NeurIPS 2025 poster ()
Keywords: Knowledge graph
Downstream tasks
Scalable
Feature learning
Primary area: general_machine_learning

Abstract: Many machine learning tasks can benefit from external knowledge. Large knowledge graphs store such knowledge, and embedding methods can be used to distill it into ready-to-use vector representations for downstream applications. For this purpose, current models have however two limitations: they are primarily optimized for link prediction, via local contrastive learning, and their application to the largest graphs requires significant engineering effort due to GPU memory limits. To address these, we introduce SEPAL: a Scalable Embedding Propagation ALgorithm for large knowledge graphs designed to produce high-quality embeddings for downstream tasks at scale. The key idea of SEPAL is to ensure global embedding consistency by optimizing embeddings only on a small core of entities, and then propagating them to the rest of the graph with message passing. We evaluate SEPAL on 7 large-scale knowledge graphs and 46 downstream machine learning tasks. Our results show that SEPAL significantly outperforms previous methods on downstream tasks. In addition, SEPAL scales up its base embedding model, enabling fitting huge knowledge graphs on commodity hardware. Our code is available at: <https://github.com/soda-inria/sepal>.

Scalable Feature Learning on Huge Knowledge Graphs for Downstream Machine Learning
Félix Lefebvre
Gaël Varoquaux SODA Team, Inria Saclay Probabl
SODA Team, Inria Saclay felix. felix. Jeiebreifevvr.iiiia.ffff
Abstract
Many machine learning tasks can benefit from external knowledge. Large knowl- edge graphs store such knowledge, and embedding methods can be used to distill it into ready-to-use vector representations for downstream applications. For this purpose, current models have however two limitations: they are primarily opti- mized for link prediction, via local contrastive learning, and their application to the largest graphs requires significant engineering effort due to GPU memory limits. To address these, we introduce SEPAL: a Scalable Embedding Propagation ALgo- rithm for large knowledge graphs designed to produce high-quality embeddings for downstream tasks at scale. The key idea of SEPAI. is to ensure global embedding small core of entities, and then
consistency by optimizing embeddings only propagating them to the rest of the graph with message passing. We evaluate SEPAL on large-scale knowledge graphs and 46 downstream machine learning tasks. Our results show that SEPAL significantly outperforms previous methods on downstream tasks. In addition, SEPAL scales up its base embedding model, enabling fitting huge knowledge graphs on commodity hardware. Our code is available at: htttps://github.ccm www.oooooooooaaooooooeoo
Introduction: embedding knowledge for downstream tasks
External knowledge for machine learning Bringing general knowledge to a machine-learnin task revives old promise of making it casier via this knowledge [Lenat and Feigenbaum, 2000] Indeed, data science is often about entities of the world -persons, places, organizations- that are well characterized in general-purpose knowledge graphs. These graphs carry rich information, including numerical attributes and relationships between entities, and can be connected to string values in tabular data through entity linking techniques [Mendes et al.) 2011 |Foppiano and Romary 2020 Delpeuch 20119). A thorny challenge, however, to transform this relational information into features for downstream tabular machine learning [Kanter and Veeramachaneni 2015 Cappuzzo et al. 2025
Robinson et al. 2024). To that end, scalable solution offered by graph embedding methods that distill the graph information into node features readily usable by any downstream tabular learner
Grover and Leskovec 2016 Cvetkov-Iliev et al. 2023
Ruiz et al. 2024].
Knowledge graphs as general knowledge sources The rapid growth of general-purpose knowleder graphs brings the exciting prospect of very general feature enrichment. Indeed, richer knowledge graph provides more comprehensive coverage and context, thereby bringing greater value to the downstream analysis [Ruiz et al. 2024). ConceptNet pioncered the distribution of general-knowledeee embeddings, building on a graph of 8 million entities [Speer et al. 2017]. Since then, knowledge graphs have continued to expand rapidly. For instance, as of 2025, Wikidata (Vrandečié and Krötzsch 2014] describes 115M entities and gains around 15M yearly [Wikimedia), and YAGO4 [Pellissier Tanon et al. 2020 gives curated view 67M entities.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Optimizing embeddings for the right task In parallel, the sophistication of knowledge-grapp embedding (KGE) models is increasing (Bordes al. 2013 Yang et al. all] | Balazevic et al. [2019a] capturing better the relational aspect of the data, important for downstream tasks [Cvetkov- -liev et al.
2023]. However, most of the KGE literature prioritizes link prediction as the primary benchmark, despite recent findings showing that strong performance on this task does not correlate with improved performance on downstream predictive tasks [Ruffinelli and Gemulla [024]. One reason may be that, for link prediction, models typically optimize for local contrasts, resulting in embeddings that are not calibrated [Tabacof and Costabello, 2020 Arakelyan et al. 2023]. While prior work has explored multi-hop reasoning to capture more complex graph patterns [Hamilton et al. 2018 Ren and Leskovec 2020], the standard evaluation paradigm for KGEs still revolves around internal tasks, rather than how the learned embeddings can transfer knowledge to practical machine-learning tasks beyond the knowledge graph itself.
The importance of scalability To leverage the full potential of very large knowledge graphs, embedding methods must be highly scalable. While many methods have been proposed to scale KGE models, doing so is not trivial. Sophisticated KGE models are typically demonstrated on small datasets like FB 15k (15k entities) or WN18 (40k entities), which are orders of magnitude smaller than modern ceneral-purpose or industrial knowledge graphs (Sullivan, 2020 The common solution to this scalability challenge is either distributed computation across multiple GPUs or machines [Lerer et al., 2019 Zhu et al. 2019 Zheng et al.) 20200] Dong al.) 2022 Zheng et al. (222), or leveraging the full memory hierarchy (disk, CPU, and GPU) on a single machine [Mohoney et al.) 2021 Ren ct al.) 2022]. These approaches require significant engineering effort to manage data partitioning, optimize data movement, and minimize synchronization overheads.
Contributions In this paper, we aim to bridge the gap between advances in embedding methods and the goal to create large and reusable -nowlll-n embeddings for downstream applications. We introduce SEPAL, scalable algorithm that applies wrapper to many embedding models. Our contributions are:
1. We propose new embedding optimization strategy that enforces global consistency among positive triples. Instead of optimizing all embeddings with local contrastive learning. SEPAL first processes small but dense core of the graph, to learn relation and core-entity embeddings. It then propagates these embeddings to the remaining entities using relation-awarr message passing. The absence of negative sampling at this propagation stage accelerates the embedding computation and makes them better suited for downstream tasks.
2. We provide a theoretical analysis showing that SEPAL's propagation step, combined with DistMult, implicitly maximizes the alignment of embeddings within positive triples.
3. We introduce BLOCS, scalable graph-splittngg algorithm that partitions huge, scale-free graphs into manageable, overlapping subgraphs. This enables fitting the embedding process on a single GPU, avoiding the engineering complexity of distributed systems. Here, the challenge lies in the seale-free and connectivity properties of large knowledge graph: some nodes are connected to a significant fraction of the graph, while others are hard to reach.
4. We conduct an extensive empirical study on 7 large knowledge graphs and 46 downstream tasks. Results show that SEPAL significantly outperforms standard methods on downstream tasks and generally faster than existing angeesccae systems. Moreover, it scales to ultra-large graphs with little computational resources: we embed WikiKG90Mv2 -91M entities, 601M triples- with a single 32GB V100 GPU. Our experimental results also highlight that using such large knowledge graphs is beneficial for downstream tasks in real-world feature enrichment scenarios.
We start by reviewing related work in section 2 Then, section 3 describes our contributed method and (section 4 gives a theoretical analysis. In |section 5| we evaluate SEPAL's performance on knowledge graphs of increasing size between YAGO3 [2.6M entities, MMaddisoltani et al. 2014] and WikikG90Mv2 [91M entities, Hu et al., 2020]; we study the use of the embeddings for feature enrichment on 46 downstream machine learning tasks, showing that SEPAL makes embedding methods more tractable while generating better embeddings for downstream tasks. Finally,/section /section discusses the contributions and limitations of SEPAL.

---

Table 1: Expression of Φ in some embedding models. @ denotes the Hadamard product, @ the Hamilton product, and x; the tensor product along mode i. The models we list here are all compatible with our pro-
Model
Relational operator
TransE
Bordes al.
2013
0 +
MuRE
Balazevic ct al.
201 7019a
1 ② P. W.
RotatE
Sun ct al. 20199
P C Wr
QuatE Zhang el at. 2019
0, @ WB
DistMult Yang el a 2015
Ox O
posed SEPAL approach.
ComplEx Trouillon
2016
0n Wyy
TuckER Balazeiic ct al.
20196
X1
0y X2 Wp
2 Related work: embedding optimization and scalability
Knowledge graphs are multi-relational graphs storing information as triples (h, r, (), where h the head entity, is the relation, and / is the tail entity. We denote V and RR respectively the set of entities and relations, and the set of triples of a given knowledge graph (IC C. x)...
2.1 Optimizing knowledge-graph embeddings
Here, we provide overview of approaches to generate din-dimnsioonl (typically d 100) vector representations for the entities, that can be used downstream applications. These include both graph-embedding techniques, that leave aside the relations, and KGE methods accounting for relations.
Graph embedding first simple strategy to get very cost-effective vector representations is to compute random projections. This avoids relying on -potentially costly- optimization, and provides embeddings preserving the pairwise distances to within an epsilon (Dasgupta and Guptal 2003). FastRP (Chen et al. 2019a] proposes scalable approach, with a few well-chosen very sparse random projections of the normalized adjacency matrix and its powers.
Another family of methods performs explicit matrix factorizations on matrices derived from the adjacency matrix, for instance GraREP [Cao al. 2015 or NetMF (Qiu et al. 2018). These methods output close embedding vectors for nodes with similar neighborhoods.
Similarly, Skip-Gram Negative Sampling (SGNS), behind word2vec Mikolov et al. 2013a performs an implicit factorization [Levy and Goldberg [014]. has been adapted to graphs: DeepWalk (Perozzi et al. (2014) and node2vec [Grover and Leskovec 2016) use random walks on the graph to generate "sentences" fed to word2vec. LINE [Tang et al. [2135] explores a similar strategy varying edge sampling. Here, the loss function is typically binary logistic regression objective:
LSGNS - log 10goo(0,, ow.) Σ log (1 a0 Ow.)
with ow, and Ow, the embeddings of the target and context nodes (or words), wy the i-th negative sample drawn from a noise distribution, p the number negative samples, and the sigmoid function.
Knowledge-graph embedding RDF2vec (Ristoski and Paulheim, 2016 adapts SGNS to multi- relational graphs by simply adding the relations to the generated sentences.
More advanced methods model relations geometric transformations in the embedding space. These triple-based methods, inspired by SGNS, represent the plausibility of a triple given the embeddings On, wr, O, of the entities and relation with scoring function f(,, t) often written as
Scoring function
f(h, r, t) -sim( (O0n,, wr), 0,)
where & is model-specific relational operator, and sim similarity function. The embeddings are optimized by gradient descent to maximize the score of positive triples, and minimize that of negative ones. A possible loss function is the binary cross-entropy loss [Ali et al. 202
LECE = - log o (f(h,r, Σ log (1 ofhhk,
(3)
3

---

which boils down to SGNS for r,t, = = 0, These models strive to align, for positive triples. the tail embedding 0₂ with the "relationally" transformed head embedding Φ(0n. w,). The challenge is to design clever & operator to model complex patterns in the data, like hierarchies, compositions, or symmetries. Indeed some relations are one-to-one (people only have one biological mother), well represented by a translation [Bordes et al.) 2013). while others are many-to-one (for instance many person were In Paris), calling for & to contract distances [Wang et al. 2017]. Many models explore different parametrizations, among which MuRE [Balazevic et al. 2019a| RotatE (Sun et al.
2019]. or QualE (Zhang et al.) 2019] have good performance [Ali et al. 202 al. This framework
also includes models like DistMult Yang et al. 2015], ComplEx [Trouillon et al. 2016 or TuckER
Balazevic et al. 2019b], that implicitly perform tensor factorizations.
Embedding propagation To smooth computed embeddings, CompGCN (asshishhh et al. 2020) introduces the idea of propagating knowledge-grape embeddings using the relational operator ø, but couples it with learnable weights and non-linearity. REP [Wang al. 2022) simplifies this
framework by removing weight matrices and non-linearities. Rossi et al. [2022] also use Feature Propagation, but to impute missing node features in graphs. Albooyeh et al. [2020] incorporate propagation within the standard link prediction pipeline, with negative sampling and gradient descent on standard KGE loss functions.
2.2 Techniques for scaling graph algorithms
Various tricks help scale graph algorithms to the sizes we are interested in -millions of nodes.
Graph partitioning Scaling up graph computations. for graph embedding or more generally, often relies on breaking down graphs in subgraphs. Appendix E.1 presents corresponding prior work.
Local subsampling Other forms of data reduction can help to scale graph algorithms (e.g. based on message passing). Algorithms may subsample neighborhoods, as GraphSAGE (Hamilton et al.) 2017) that selects a fixed number of neighbors for each node on each layer, or GraphSAINT [Zeng al. 2020) that samples overlapping subgraphs through random walks, for supervised GNN train- ing via node classification. Cluster-GCN [Chiang et al. 2019] restricts the neighborhood search within clusters, obtained by classic clustering algorithms, to improve computational efficiency. Mar- iusGNN (Waleffe et al., [023) uses an optimized data structure for neighbor sampling and GNN aggregation. TIGER [Wang al., 2024 proposes slice-and-cache procedure optimize the subgraph extraction for large-scale inductive GNN training on knowledge graphs.
Multi-level techniques Multi-level approaches, such HARP [Chnn et al. 2018 GraphZoom Deng et al., [0200 or MILE [Liang et al., [202T], coarsen the graph, compute embeddings on the smaller graph, and project them back to the original graph.
2.3 Scaling knowledge-graph embedding
Parallel training Many approaches scale triple-level stochastic solvers by distributing training across multiple workers, starting from the seminal PyTorch-Bii BogghhB (PBG) [Lerer et al.) 2019 that splits the triples into buckets based on the partitioning of the entities. The challenge is then to limit overheads and communication costs coming from 1) the additional data movement incurred by embeddings of entities occurring in several buckets 2) the synchronization of global trainable parameters such as the relation embeddings. For this, DGL-KE [Zheng al. 2020) reduces data movement by using sparse relation embeddings and METIS graph partitioning Karypis and Kumar 1997 distribute the triples across workers. HET-KG [Dong et al. 2022) further optimizes distributed training by preserving copy of the most frequently used embeddings on each worker, to reduce communication costs. These "hot-embeddings" are periodically synchronized to minimize inconsistency. SMORE [Ren et al.] 2022) leverages asynchronous scheduling to overlap CaU--baedd data sampling, with GaU-based embedding computations. Algorithmically. contributes a rejection sampling strategy to generate the negatives at low cost. Graph Vite (Zhu et al. 2019 accelerates SGNS for graph embedding by both parallelizing random walk sampling on multiple CPUs, and negative sampling on multiple GPUs. Marius (Mohoney et al. [021] reduces synchronization overheads by opting for asynchronous training of entity embeddings with bounded staleness, and minimizes IÖ with partition caching and buffer-aware data ordering. GE2 [Zheng et al. 2024 improves data swap

---

1.a. Core selection
2. Core embedding
o B
with traditional KGE
core embleddings O relation embedddings W.
subrraph
3. Embedding propagation with message passing
Imput graph
outer
1.b. BLOCS
subgraphs.
decomposition
outer
embeddings 0,
Figure SEPAL's embedding pipeline. First, a core subgraph is extracted from the input knowledge graph (step I.a). BLOCS then subdivides this input knowledge graph into outer subgraphs (step 1.b). Next, the core subgraph is embedded using traditional KGE models, which generate vector representations for both core entities and relations (step 2.). Finally, these embeddings are propagated with message passing to each outer subgraph successively (step 3.).
between CPU and multiple GPUs. Finally, the LibKGE Broscheit et al. 2020 Python library also supports parallel training and includes GraSH [Kochsick al. 2022 an efficient hyperparameter optimization algorithm for large-scale KGE models.
Parameter-efficient methods Other approaches reduce GPU memory pressure by limiting the
number of parameters. NodePiece [Galkin et al. [2022] and EARL [Chen et al. 2023 embed a subset of entities and train an encoder to compute the embeddings of the other entities. However, their tokenization step is costly, and they have not been demonstrated on graphs larger than 2.5M nodes.
SEPAL: revisiting knowledge-graph embedding optimization
Most work on scaling knowledge-graph embedding has focused on efficient parallel computing to speed up stochastic optimization. We introduce a different approach, SEPAL, which changes how embeddings are computed, enforcing a more global structure, beneficial for downstream tasks, while avoiding much of the optimization cost. To that end, SEPAL proceeds in three steps (Figure I):
1. separates the graph in a core and a set of connected overlapping outer subgraphs that cover the full graph;
2. uses a classic KGE model to optimize the embeddings of the core entities and relations;
3. propagates the embeddings from the core the outer subgraphs, using message -aagggngasinngggg strategy preserving the relational geometry and ensuring embedding alignment within positive triples, with further training.
SEPAL's key idea is to allocate more computation time to the more frequent entities and then use message passing propagate embeddings at low cost to regions of the graph where they have been computed yet. It departs from existing embedding propagation methods [Vashishth et al. 22200] Wang al. 2022] that compute embeddings on the full graph and propagation post-processing to smooth them. SEPAL is compatible with any embedding model whose scoring function has the form given by Equation 2, examples of which are provided Table
3.1 Splitting large graphs into manageable subgraphs
Breaking up the graph into subgraphs is key to scaling up our approach memory-wise. Specifically, we seek a set of subgraphs that altogether cover the full graph but are individually small enough fit on GPUs, to enable the subsequent GPU-based message passing.
5

---

Core subgraph SEPAL first defines the core of a knowledge graph. The quality of the core embed- dings is particularly important, as they serve as (fixed) boundary conditions during the propagation phase. Good relation embeddings are also key to structuring the propagation. To optimize this quality, two key factors must be considered during core selection: 1) ensuring dense core subgraph by selecting the most central entities and 2) achieving full coverage of relation types. Yet, there can be trade-off between these two objectives, hence, SEPAL offers two core selection procedures:
Degree-based selection: This simple approach selects the top entities by degree -with proportion Th E (0,1)- and keeps only the largest connected component of the induced subgraph. The resulting core is dense, which boosts performance for
tasks like feature enrichment (Appendix ).p2.. However, it does not necessarily contain all the relation types.
Hybrid selection: To ensure full relational coverage, this method combines two sampling strategies. First, it selects entities with the highest f)n degrees. Second, for each relation type, it includes entities involved in edges with the highest 7/e degrees (where degree is the sum of the head and tail nodes' degrees). The union of these two sets forms the core, and if disconnected, SEPAL reconnects by adding the necessary entities (details in Appendix F.2.2). Hyperparameters Th E (0, 1) are proportions of nodes and edges that control the core size.
Compared to degree-basee selection, hybrid selection benefits tasks relying on relation embeddings, such as link prediction. However, its additional celation--pecifii edge sampling and reconnection steps can be computationally expensive for knowledge graphs with many relations. For disconnected input graphs, all connected components other than the largest one added to the core subgraph.
Outer subgraphs The next class of subgraphs that we generate -the outer subgraphs- aim at covering the rest of the graph. The purpose of these subgraphs demands the following requirements:
RI: connected the subgraphs must be connected, to propagate the embeddings;
R2: bounded size the subgraphs must have bounded sizes, fit their embeddings in GPU memory;
R3: coverage the union of the subgraphs must be the full graph, to embed every entity:
R4: scalability extraction must run with available computing resources, in particular memory.
Extracting such subgraphs is challenging on large knowledge graphs. These are scale-free graphs with millions of nodes and no well-defined clusters [Leskovec et al. 2009]. They pose difficulties to partitioning algorithms. For instance, algorithms based on propagation, eigenvalues, or power iterations of the adjacency matrix (Raghavan et al.] 2007 Shi and Malik 22000] Newman [0066] struggle with the presence of extremely high-degree nodes that make the adjacency matrix ill- conditioned. None of the existing partitioning algorithms satisfy our full set of constraints, and thus we devise our own algorithm, called BLOCS and described in detail in Appendix E To satisfy the requirements despite these challenges, BLOCS creates overlapping subgraphs.
We contribute BLOCS, an algorithm designed to break large graphs into Balanced Local Overlapping Connected Subgraphs. The name summarizes the goals: 1) Balanced: BLOCS produces subgraphs of comparable sizes. m, the upper bound for subgraph sizes, is a hyperparameter. 2) Local: the subgraphs have small diameters. This locality property important for the efficiency of SEPAL's propagation phase, as it reduces the number of propagation iterations needed to converge to the global embedding structure. 3) Overlapping: a given node can belong to several subgraphs. This serves our purpose because it facilitates information transfer between the different subgraphs during the propagation. 4) Connected: all generated subgraphs are connected.
BLOCS uses three base mechanisms to grow the subgraphs: diffusse (add all neighboring entities to the current subgraph), merge (merge two overlapping subgraphs), and dilate (add all unassigned neighboring entities to the current subgraph). There are two different regimes during the generation of subgraphs. First, few entities are assigned, and the computationally effective diffusion quickly covers large part of the graph, especially entities that are close to high-degree nodes. However, once these close entities have been assigned, the effectiveness of diffusion drops because it struggles to reach entities farther away. For this reason, BLOCS switches from diffusion to dilation once the proportion of assigned entities reaches certain threshold (a hyperparameter chosen & .6, depending on the dataset). By adding only unassigned neighbors to subgraphs, dilation drives subgraph growth towards unassigned distant entities. However, the presence of long chains can drastically slow down this regime because they make it add entities one by one. Some knowledge graphs have long chains, for

---

instance YAGO4.5 (see Diameter in Table 2). To tackle them, BLOCS switches back to diffusion for few steps, with seeds taken inside the long chains.
BLOCS works faster on graphs that have small diameters, where most entities can be reached during the diffusion regime and fewer dilation steps required (Appendix F.T..
3.2 Core optimization with traditional KGE models
Once the core subgraph is defined, SEPAL trains on GPU any compatible triple-based embedding model (DistMult, TransE, ...). This process generates embeddings for the core entities and relations, including inverse relations, added to ensure connectedness for the subsequent propagation step.
3.3 Outside the core: relation-aware propagation
Key to SEPAL's global consistency embeddings and to computational efficiency is that it does not use contrastive learning and gradient descent for the outer entities. Instead, the final step involves an embedding propagation that is consistent with the KGE model (multiplication for DistMult, addition for TransE, ...) and preserves the relational geometry of the embedding space. To do so, SEPAL leverages the entity-relation composition function ø (given by Table I) used by the KGE model, and the embeddings of the relations w, trained the core subgraph. From Equation one a given triple (h, 1), the closed-form expression of the tail embedding that maximizes the scoring function arg maxg, [h, = d(0,, w, SEPAL uses this property to compute outer embeddings as consistent with the core as possible, by propagating from core entities with message passing.
derive, for
(u.. entity u belongs the core subgraph, 0, otherwise.
First, the embeddings are initialized with
(0)
Then, each outer subgraph S C K is loaded on GPU, merged with the core subgraph C, and SEPAL performs T steps of propagation (T' is hyperparameter), with the following message-passing equations:
Message:
m ((+1)
Σ
(( w.)
Aggregation:
a
((+1)
Σ (1+1)
(5)
vEN(u)
( aa,
((+1)
Update:
@((+1)
(6)
( + aa [f+1)
where (u)) denotes the set of neighbors of outer entity K. the set of positive triples of the graph, and a hyperparameter similar to a learning rate. During updates, &2 normalization projects embeddings on the unit sphere. With DistMult, this accelerates convergence by canceling the effect of neighbors that still have zero embeddings. Normalizing embeddings common practice in knowledge- graph embedding [Bordes et al. 2013 Yang et al., 2015), and SEPAL acts accordingly. During propagation, the core embeddings remain frozen.
4 Theoretical analysis: embedding alignment
SEPAL minimizes a global energy via gradient descent Proposition 4.1 shows that SEPAL with DistMult minimizes energy that only accounts for the positive triples. The more aligned the embeddings within positive triples, the lower this energy. In self-supervised learning, negative sampling needed to prevent embeddings from collapsing to single point (Hafidi al. 2022) However, in our case, this oversmoothing is avoided thanks to the boundary conditions of fixed core-entities and relations embeddings, which act "anchors" in the embedding space. Proposition 4.1 (Implicit Gradient Descent). Let & be the "alignment energy" defined as
E =
Σ (0,, o00,, w)))
(KTT.)jK
with (00,, w.,) = 0 & un being the DistMult relational operator. Then, SEPAL's propagation step amounts mini-batch projected gradient step descending E under the following conditions:
7

---

1. SEPAL uses DistMult as base KGE model:
2. the embeddings of relations and core entities remain fixed, and serve as boundary conditions;
3. the outer subgraphs act as mini-batches.
As a consequence, SEPAL converges towards a stationary point of & on the unit sphere.
Proof sketch. For outer entity u, the gradient update of its embedding (((+11) boils down to SEPAL's propagation equation, for a learning rate = a. See Appendix D.2 for detailed derivations.
@00) -11 !
30
Analogy to eigenvalue problems Appendix Dppendix[D.IIshooot shh]ssows that SEPAL's propagation, when combined with DistMult, behaves like an Arnoldi iteration. This suggests that outer entity embeddings align with the dominant eigenvectors of an operator that captures both the graph structure and relational semantics (via fixed relation embeddings). In spectral graph theory, the eigenvectors of the Laplacian define the graph Fourier transform, and the leading ones correspond to the low frequencies. Similarly, in the SEPAL framework, the propagation computes 'low- fow-frequency' representations for the outer entities, with the boundary conditions of fixed core embeddings.
Queriability of embeddings Assume that each entity E V is associated with set of scalar features F. E IRmm, such that æ.,,; denotes the i-th property of u. We say that the embeddings support queriability with respect to property E 1,..., m if,
3ft E F such that f(,)) = Tu.i.
(8)
where denotes a class of functions from R.d to R constrained by some regularity conditions. This queriability property is key to the embeddings' utility to downstream machine learning tasks.
In knowledge graphs, properties F. that explicitly represented by triples (u, r;; v:) can be recov- ered via the scoring function 6 used in the model, under the condition of well-aligned embeddings. Specifically, when such relation ri exists, natural querying function is fi x p(ar, w.;). ). where w,, is the embedding of relation r3 (we assume scalar embeddings for simplicity). This property holds only if the score of positive triples is maximized, implying that the corresponding facts have successfully been captured by the embeddings.
Proposition 4.1 shows that SEPAL minimizes energy promoting alignment between embeddings within positive triples, which we argue leads to high queriability, since the scores of positive triples are maximized. In contrast, classic KGE methods use negative sampling to incorporate supplementary constraint of local contrast between positive and negative triples. This adds discriminative power to the model, useful for link prediction, but can hinder queriability, minimizing the score of negative triples may come at the expense of maximizing that of positive ones.
5 Experimental study: utility to downstream tasks
Knowledge graph datasets To compare large knowledge graphs of different sizes, we use Freebase [Bollacker et al. 2008 WikiK [(an extract of Wikidata) Hu et al., 2020). and three gener- ations of YAGO: YAGO3 Mahdisoltani et al. 2014], YAGO4 [Pelissier Tanon et al., 2020). and YAGO4.5 [Suchanek et al. 2024 We expand YAGO4 and YAGO4.5 into larger version containing also the taxonomy, Lee. types and classes -which algorithms will treat as entities- and their relations. We discard numerical attributes and keep only the largest connected component (Appendix A.I) To perform an ablation study of SEPAL without BLOCS for which we need smaller datasets, we also introduce Mini YAGO3, a subset of YAGO3 built with the 5% most frequent entities. Knowledge graph sizes are reported in Figure 6
Hu
On real-world downstream regression tasks We evaluate the embeddings as node features in downstream tasks [Grover and Leskovec 2016 Evetkov-lliev et al.] 2023 Robinson et al.] 2024 Ruiz et al., 2024). Specifically, we incorporate the embeddings in tables as extra features and measure the prediction improvement of standard estimator in regression tasks. This setup allows us to compare the utility of knowledge graphs of varying sizes. Indeed, for task, a suboptimal embedding of larger knowledge graph may be more interesting than high-quality embedding of
8

---

smaller knowledge graph because the larger graph brings richer information, on more entities. We benchmark 4 downstream regression tasks [adapted from Cvetkov-Iliev 2023): Movie revenues,
US accidents, US elections, and housing prices. Details are provided in Appendix A.2
Larger knowledge graphs do bring value (Fig- ure 2), as they cover more entities of the down- stream tasks (Figure 4). For each source graph, SEPAL provides the best embeddings and is much more scalable (details in Figure 6). Consider- ing performance/coss Pareto optimality across methods and source graphs (Figure 24), SEPAL achieves the best performance with reduced cost, the simple baseline FastRP also gives Pareto- optimal results, for smaller costs. Although Fas- tRP discards the type of relation, it performs better than most dedicated KGE methods. Its iterations also solve a more global problem, like SEPAL (Appendix D.I.
a) Performance/cost Pareto frontier
1.0
Mean R2 score (normalized)
SEPAL
FastRP
0.8
DGL-KE
0.7
DistMult
0.5
NodePiece
0.4
1min
1h
Embedding computation time
We used DistMult as base model as it is classic and good performer [Ruffinlll et al. [2200] Kadlec
Embeddings computed on:
al. 2017 Jain al.] 2020]_ Figure 24 shows
YAGO3
YAG04.5
Freebase
YAG04
YAG04.5+T
WikekG90Mv2
that SEPAL can speed up DistMult over 20 times
YAG04+T
for given training configuration. For other scor- ing functions like RotatE and TransE, |Figure 8 shows that SEPAL also improves the downstream performance of its base model.
For each source:
best
not best
b) Critical difference diagram (28 tasks)
On WikiDBs tables We also evaluate SEPAL tables from WikiDBs |Vogel et al. 2024). j a corpus of databases extracted from Wikidata. We build 42 downstream tables (26 classification tasks, and 16 regression tasks), described in Appendix A.2 Four of them are used as validation tasks, to tune hyperparameters, and the remaining 38 are used test tables. FFigure presents the aggregated results these 38 test tables, showing that, here also, applying SEPAL to very large graphs provides the best embeddings for downstream node regres- sion and classification, and that SEPAL brings decreased computational cost. Regarding the performance-cost tradeoff, FastRP is once again Pareto-optimal for small computation times, high- lighting the benefits of global methods.
PBG DGL-KE
SEPAL
Figure Statistical performance on real- world tables. a) Pareto frontiers of averaged normalized prediction scores with respect to em- bedding times (log-scale). b) Critical differ- ence diagrams [Terpilowski 2019) of average ranks among the three methods (SEPAL, PBG and DGL-KE) that scale to every knowledge- graph dataset. The ranks are averaged over all tasks; a task being defined as the combination of downstream table and source knowledge graph. SEPAL gets the best average downstream performance for each of the 7 source knowledge graphs. [Figure 6) gives the detailed results for each table. Appendix B.I details the metric used.
Discussion and conclusion
Benefits of larger graphs We have studied how to build ceneral-knowledge feature enrichment from huge knowledge graphs. For this purpose, we have introduced a scalable method that captures more of the global structure than the classic KGE methods. Our results show the benefit of embedding larger graphs. There are two reasons to this benefit: (1) larger knowledge graphs can result in larger coverage of downstream entities (another important factor for this is the age of the dataset: recent ones have better coverage) (2) for two knowledge graphs with equal coverage, the larger one can result richer representations because the covered entities have more context to learn from.
Limitations
Our work focuses on embeddings for feature enrichment of downstream tables, an
active research field [Cvetkov-Ilies et al. 2023 Ruiz et al. 2024 Robinson et al.) 2024 Another popular use case for embeddings knowledge graph completion. However, this task fundamentally different from feature enrichment: embeddings optimized for link prediction may not perform well

---

WikiDBs regression (98 tasks)
WikiDBs classification (168 tasks)
a) Critical difference diagrams
PBG
SEPAL
DGL-KE KE
SEPAL
DGL-KE
PBG
b) Performance/ccost Pareto frontiers
Mean weighted F1 score (normalized)
SEPAL
Embeddings computed
FastRP
Mean R2 score (normalized)
FastRP
0.6
PBG
YAGO4
PBG
YAGO4+T
DGL-KE
0.6
DGL-KE
YAG04,5
0.4
YAG04,5+T
NodePiece
NodePiece
Freebase
WikiKG90Mv2
0.2
DistMult
0.2
DistMult
For each source:
best
1min
1h
1d
1min
1h
1d
not best
Embedding computation time
Embedding computation time
Figure 3: Statistical performance on WikiDBs tables. a) Critical difference diagrams of scalable methods. Black lines connect methods that not significantly different. b) Pareto frontiers of averaged normalized prediction scores with respect to embedding times (log-scale). |Figure 7 Appendix C.2 provides the detailed results for each of the 38 test tables.
for feature enrichment, and vice versa [Ruffnnlli and Gemulla 2024 Nevertheless, we also evaluate SEPAL on knowledge graph completion, for which we expect lower performances given that SEPAL does not locally optimize the contrast between positive and negative triples scores. Results reported in Appendix [.6 that SEPAL sometimes performs lower than existing methods (DGL-KE, PBG) on this task, although no method consistently better than the others for datasets, and statistical tests show no significant differences (Figure 9).
Conclusion: embeddings for downstream machine learning In this paper, we show how to optimize knowledge-gras embeddings for downstream machine learning. We propose highly scalable method, SEPAL, and conduct a comprehensive evaluation on 7 knowledge graphs and 46 downstream tables showing that SEPAL both: (1) markedly improves predictive performance on benefits -multiple-fold decreased train
downstream tasks and (2) brings caapuutational-peffrmmaa times and bounded memory usage- when embedding large-scale knowledge graphs. Our theoretical analysis suggests that SEPAL's strong performance on downstream tasks stems from its global optimization approach, resulting in better-aligned embeddings compared classic methods based on negative sampling. SEPAL improves the quality of the generated node features when used for data enrichment in external (downstream) tasks, setting that can strongly benefit from pre-training embeddings on knowledge bases as large as possible. It achieves this without requiring heavy engineering, such as distributed computing, and can easily be adapted most KGE models.
Insights brought by our experiments go further than SEPAL. First, the method successfully exploits the asymmetry of information between "central" entities and butions are indeed present on many types of objects, from words [Piantadosi] 2014] to geographical entities [Giesen and Südekum, 201 I and should probably be exploited for general-kknwleed sentations such as knowledge- gegggg embeddings. Second, and related, breaking up large knowledge graphs in communities is surprisingly difficult: some entities just belong in many (all?) communities, and others are really hard to reach. Our BLOCS algorithm can be useful for other graph engineering tasks, such as scaling pessage-passing algorithms simply generating partitions. Finally, the embed- ding propagation in SEPAL appears powerful, and we conjecture it will benefit further approaches. First, it can combined with much the prior art to scale knowledge- -baee embedding- Second, it can naturally adapt to continual learning settings [Van de Ven et al. 2022 Hadsell et al. 2020 Biswas al. 2023), which are important mnwwledge-graph applications since knowledge graphs, such Wikidata, are often continuously updated with new information (Appendix G.3
peripheral ones. Power-law distri-
repre-
G.3
10

---

Acknowledgements
GV acknowledges support from ANR via grant TaFoMo (ANR-25-CE23-1822) This work is partly supported by Hi! PARIS and ANR/France 2030 program (ANR-23-1ACI-0005))
References
Douglas Lenat and Feigenbaum. On the thresholds of knowledge. Artificial Intelligence: Critical Concepts, 2:298, 2000.
Pablo N Mendes, Max Jakob, Andrés Gareía-Silva, and Christian Bizer. Dbpedia spotlight: shedding light on the web of documents. In Proceedings of the 7th international conference on semantic systems, pages 1 1-8, 2011.
Luca Foppiano and Laurent Romary. patity-fishing a dariah entity recognition and disambiguation service. Journal of the Japunese Association Digital Humanities, 5(1):22-60, 2020.
Antonin Delpeuch. Opentapioca: Lightweight entity linking for wikidata. arXiv preprint
arXiv: 133,,, 2019.
James Max Kanter and Kalyan Veeramachaneni, Deep feature synthesis: Towards automating data science endeavors. 2015 IEEE international conference on data science and advanced analytics (DSAA), pages 1-10. IEEE, 2015.
Riccardo Cappuzzo, Aimee Coelho, Felix Lefebvre, Paolo Papotti, and Gael Varoquaux. Retrieve, merge, predict: Augmenting tables with data lakes. TMLR, 2025.
Joshua Robinson, Rishabh Ranjan, Weihua Hu, Kexin Huang, Jiaqi Han, Alejandro Dobles, Matthias Fey, Jan Eric Lenssen, Yiwen Yuan, Zecheng Zhang, et al. Relbench: A benchmark for deep learning on relational databases. Advances Neural Information Processing Systems, 37:21330- 21341, 2024.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
Alexis Cvetkov-lliev, Alexandre Allauzen, and Gaël Varoquaux. Relational data embeddings for feature enrichment with background information. Machine Learning, 1 12(())687-720, 2023.
Camilo Ruiz, Hongyu Ren, Kexin Huang, and Jure Leskovee. High dimensional, tabular deep learning with an auxiliary knowledge graph. Advances in Neural Information Processing Systems, 36, 2024.
Robyn Speer, Joshua Chin, and Catherine Havasi. Conceptnet 5.5:
An open multilingual graph of general knowledge. Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
Denny Vrandečić and Markus Krötzsch. Wikidata: free collaborative knowledgebase. Communica- tions of the ACM, 57(10)778-85, 2014.
Wikimedia. Wikidata growth. https://wikitechi www.eeed..wiimmiia....m. www.i/eniie..oggg/...//////////e wttt///////////iiaaaaaa//a/aa CroothhHiuubrr_o__ffttttttttsset
[Online; accessed in January 2025].
Thomas Pellissier Tanon, Gerhard Weikum, and Fabian Suchanek. Yago 4: A reason-able knowledge base. In European Semantic Web Conference, pages 583-596. Springer, 2020.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 26, 2013.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Deng. Embedding entities and relations for learning and inference in knowledge bases. In Proceedings of the 3rd International Conference on Learning Representations (ICLR), 2015. URL https:: htaps:://axiiv www.vi..orggaaae www./ogg///bboo...oo.ooo 1412
6575

---

Ivana Balazevic, Carl Allen, and Timothy Hospedales. Multi- Multi-relational poincaré graph embeddings. Advances in Neural Information Processing Systems, 32, 2019a.
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 (RepLANLP. 2024), pages 136-162, 2024.
Pedro Tabacof and Luca Costabello. Probability calibration for knowledge graph embedding models. In International Conference on Learning Representations, 2020. URL |ttLsss////ppeereeii.e net/ het/ffruumidd=SggKiI0
Erik Arakelyan, Pasquale Minervini, Daniel Daza, Michael Cochez, and Isabelle Augenstein. Adapt- ing neural link predictors for data-efficient complex query answering. Advances Neural Infor- mation P Processing Systems, 36:27069-2700000 27091, 2023.
Will Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. Advances in neural information processing systems, 31, 2018.
Hongyu Ren and Jure Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. Advances in Neural Information Processing Systems, 33:19716-19726, 2020.
Danny Sullivan. A reintroduction to our knowledge graph and knowledge panels. https
//blog.googles www.gooooggggg.ooo pttp:ppoouussseeeee wttpcctsseeeeaaraabbataaat.t.eee haaarchhabbutt-noooeeeeeee. wrapeeeggeg--phhhhoo and- -nwwledge-paneess 2020. Accessed: 2025-01-26.
Adam Lerer, Ledell Wu, Jiajun Shen, Timothee Lacroix, Luca Wehrstedt, Abhijit Bose, and Alex Peysakhovich. Pytorch- hrigrah-iiggraph: A large scale graph embedding system. Proceedings of Machine Learning and Systems, 1:1 1:120-131, 2019.
Zhaocheng Zhu, Shizhen Xu, Jian Tang, and Meng Qu. Graphvite: A high-performance cpu-gpu hybrid system for node embedding. In The World Wide Web Conference, pages 2494-2504, 2504, 2019.
Da Zheng, Xiang Song, Chao Ma. Zeyuan Tan, Zihao Ye. Jin Dong, Hao Xiong, Zheng Zhang, and George Karypis. Dgl-ke: Training knowledge graph embeddings at scale. In Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval, pages 739-748, 2020.
Sicong Dong, Xupeng Miao, Pengkai Liu, Xin Wang, Bin Cui, and Jianxin Li. Het-kg: Communication-effiieenn knowledge graph embedding training via hotness-awar aware cache. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 1754 1766. IEEE, 2022.
Chenguang Zheng, Guanxian Jiang, Xiao Yan, Peiqi Yin, Qihui Zhou, and James Cheng. Ge2: general and efficient knowledge graph embedding learning system. Proceedings of the ACM on Management of Data, 2(3):1 2024.
Jason Mohoney, Roger Waleffe, Henry Xu, Theodoros Rekatsinas, and Shivaram Venkataraman. Marius: Learning massive graph embeddings on single machine. 15th {USENIX) Symposium Operating Systems Design and Implementation ((OSDI) 21), pages 533-549, 2021.
Hongyu Ren, Hanjun Dai, Bo Dai, Xinyun Chen, Denny Zhou, Jure Leskovee, 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, pages 1472-1482, 2022.
Farzaneh Mahdisoltani, Joanna Biega, and Fabian Suchanek. Yago3: A knowledge base from multilingual wikipedias. In 7th biennial conference innovative data systems research. CIDR Conference, 2014.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benehmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18-22133, 2020.
12

---

Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithms, 22(():60-66 65, 2003.
Haochen Chen, Syed Fahad Sultan, Yingtao Tian, Muhao Chen, and Steven Skiena. Fast and accurate network embeddings via very sparse random projection. In Proceedings of the 28th ACM international conference on information and knowledge management, pages 399 408, 2019a.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM international on conference on information and knowledge management, pages 891 1000, 2015.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pages 459 467, 2018.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representa- tions in vector space. arXiv preprint arXiv: 1301.3781, 2013a.
Tomas Mikolov, llya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013b.
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. Advances in neural information processing systems, 27, 2014.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference on world wide web, pages 1067-1077, 2015.
Zhiqing Sun, Zhi-Hong Deng, Jian Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In International Conference Learning Representations, 2019. URL
Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embeddings. Advances in neural information processing systems, 32, 2019.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International conference on machine learning, pages 2071-2080. PMIR, 2016.
Iaana Balazevic, Carl Allen, and Timothy Hospedales. TuckER: Tensor factorization for knowledge graph completion. In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan, editors, Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (FMNL.P-JCNIP),, pages 5185- 5194, Hong Kong, China, November 2019b. Association for Computational Linguistics. doi: 10. 10.18663/1//D1111522 URL http.htttp://allantttleo wrw.:/9-1rDDD111112220
Petar Ristoski and Heiko Paulheim. Rdf2vec: Rdf graph embeddings for data mining, In The Semantic Web-ISWC 2016: 15th International Semantic Web Conference, Kobe, Japan, October 17-21, 2016, Proceedings, Part 15, pages 498-514. Springer, 2016.
Mehdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Mikhail Galkin, Sahand Shar- ifzadeh, Asja Fischer, Volker Tresp, and Jens Lehmann. Bringing light into the dark: A large-scale evaluation of knowledge graph embedding models under unified framework. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(12):88258883 8845, 2021a.
Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and applications. IEEE transactions on knowledge and data engineering, 29(12): 2724-2743, 2017.
13

---

Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition baapps based multi- relational graph convolutional networks. In International Conference on Learning Representations. 2020. Utt.ttttps://ooeeeeeeee
wwt.w/ruuweermmem//// idd-ByAA C4tPr
Huijuan Wang, Siming Dai, Weiyue Su, Hui Zhong, Zeyang Fang, Zhengjie Huang, Shikun Feng. Zeyu Chen, Yu Sun, and Dianhai Yu. Simple and effective relation-based embedding propagation for knowledge representation learning. In IJCAI-ECAI, 2022.
Emanuele Rossi, Henry Kenlay, Maria I Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features. In Learning on graphs conference, pages I 11-1. PMLR, 2022.
Marjan Albooyeh, Rishab Goel, and Seyed Mehran Kazemi. Out-of-sample representation learning for knowledge graphs. In Findings of the association for computational linguisties: EMNLP 2020, pages 2657-26666 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Hanqing Zeng. Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. International Conference on Learning Representations, 2020. URL httpssts/////peeree////
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 257-266, 2019.
Roger Waleffe, Jason Mohoney, Theodoros Rekatsinas, and Shivaram Venkataraman. Mariusgnn: Resource- out-of-core training of graph neural networks. In Proceedings of the Eighteenth European Conference on Computer Systems, pages I 144-161, 2023.
Kai Wang, Yuwei Xu, and Siqiang Luo. Tiger: Training inductive graph neural network for large-scale knowledge graph reasoning. Proceedings of the VLDB Endowment, 17(10):249--247) 2024.
Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. Harp: Hierarchical representation learning for networks. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng. Graphzoom: A multi- level spectral approach for accurate and scalable graph embedding. In International Conference on Learning Representations, 2020. URL
Jionggian Liang, Saket Gurukar, and Srinivasan Parthasarathy. Mile: A multi-level framework for scalable graph embedding. In Proceedings of the International AAAI Conference on Web and Social Media, volume 15, pages 361-372, 2021.
George Karypis and Vipin Kumar. Metis: software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. 1997.
Samuel Broscheit, Daniel Ruffinelli, Adrian Kochsiek, Patrick Betz, and Rainer Gemulla. LibKGE A knowledge graph embedding library for reproducible research. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Prucessing: System Demonstrations, pages
165-174, 2020. URL. https::///// /wwp//wwc..ooo aclweb. org/ anthologyhhoyyyoo 200p
2020 emnlp-demoe 22
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, pages 138-154. Springer, 2022.
Mikhail Galkin, Etienne Denis, Jiapeng Wu, and William L. Hamilton. Nodepiece: Compositional and parameter-efficient representations of large knowledge graphs. International Conference on Learning Representations, 2022. URL https: ptttps://openreeeee wwwp:/neeeeeeeeeeeeeee http://foummmddxx___oe
14

---

Mingyang Chen, Wen Zhang, Zhen Yao, Yushan Zhu, Yang Gao, Jeff Z Pan, and Huajun Chen. aagiit-agnostic representation learning for parameter-efficiet knowledge graph embedding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 4182-4190, 2023.
Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, ((1):29-123, 2009.
Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. Near linear time algorithm detect community structures in large-scale networks. Physical review E, 76(3):036106 2007.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888 900889905521000 2000.
Mark EJ Newman. Finding community structure in networks using the eigenvectors of matrices. Physical review E, 74(3):036104, 2006.
Hakim Hafidi, Mounir Ghogho, Philippe Ciblat, and Ananthram Swami. Negative sampling strategies for contrastive cul--uupeeeiee learning of graph representations. Signal Processing. 190:108310, 2022.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collabora- tively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 1247-1250. 2008.
Fabian M Suchanek, Mehwish Alam, Thomas Bonald, Lihu Chen, Pierre Herri- Paris, and Jules Soria. Yago 4.5: A large and clean knowledge base with rich taxonomy. In Proceedings of the 47th International ACM SIGIR Conference on Reseurch and Development in Information Retrieval, pages 131 130- 2024.
Maksim A Terpilowski. scikit-posthoes: Pairwise multiple comparison tests in python. Journal of Open Source Software, 4(36): 169, 2019.
Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. You can teach an old dog new tricks! on training knowledge graph embeddings. In International Conference on Learning Representations, httt:/forumiiddBBosstt
2020. URL /
Rudolf Kadlec, Ondrej Bajgar, and Jan Kleindienst. Knowledge base completion: Baselines strike back. Rep4NLP@ACL, 2017. URL https:/ts://ppl semanticscholar orw.arruusrCCCCCII
7557552
Prachi Jain, Sushant Rathi, Soumen Chakrabarti, et al. Knowledge base completion: Baseline strikes back (again). arXiv preprint weXiv:2055.00800 2020.
Liane Vogel, Jan-Micha Bodensohn, and Carsten Binnig. Wikidbs: A large-scale corpus of relational databases from wikidata. Advances in Neural Information Processing Systems, 37:41 412- 2024.
Steven T Piantadosi. Zipf's s word frequency law in natural language: A critical review and future directions. Psychonomic bulletin & review. 21:1112-1133 2014.
Kristian Giesen and Jens Südekum. Zipf's law for cities in the regions and the country. Journal of economic geography, 11(4):667-666, 2011.
Gido M Van de Ven, Tinne Tuytelaars, and Andreas S Tolias. Three types of incremental learning. Nature Machine Intelligence, 4:1 4:1185-1197, 2022.
Raia Hadsell, Dushyant Rao, Andrei A Rusu, and Razvan Pascanu. Embracing change: Continual learning in deep neural networks. Trends cognitive sciences, 10(12):002--1044 2020.
Russa Biswas, Lucie-Aiméé Kaffee, Michael Cochez, Stefania Dumbrava, Theis Jendal, Matteo Lissandrini, Vanessa Lopez, Eneldo Loza Meneía, Heiko Paulheim, Harald Sack, et al. Knowl- edge graph embeddings: open challenges and opportunities. Transactions on Graph Data and Knowledge, 1(1):--1, 2023.
15

---

Fabian Pedregosa, Gaël Varoquaux. Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, al. Scikit-leam: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
Mehdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Sahand Sharifzadeh, Volker Tresp, and Jens Lehmann. PyKEEN 1.:: A Python Library for Training and Evaluating Knowledge Graph Embeddings. Journal of Machine Learning Research, 22(82):1-6, 2021b.
URL http
20-22220-25552 825. 20mm21.ttm1
Maintainer Gabor Csardi. Package 'igraph'. Last accessed, 3(09):2013, 2013.
William Jay Conover and Ronald I. Iman. Multiple-comparioons procedures. informal report. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 1979.
William Jay Conover. Practical nonparametric statistics. john wiley & sons, 1999.
Walter Edwin Amoldi. The principle of minimized iterations in the solution of the matrix eigenvalue problem. Quarterly of applied mathematics, 11):17-29, 1951.
Richard B Lehoueq, Danny Sorensen, and Chao Yang. ARPACK users guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods. SIAM, 1998.
the Dimitri P Bertsekas. Nonlinear programming. Journal the Operational Research Society, 48(3): 334-334, 1997.
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008
(10): 2008
Martin Rosvall and Carl T Bergstrom. Maps of random walks on complex networks reveal community structure. Proceedings of the national academy of sciences, 105(4):1118-113) 2008.
Vincent A Traag, Ludo Waltman, and Nees Jan Van Eck. From louvain to leiden: guarantecing well-connected communities. Scientific reports, 9(1):2233, 2019.
Isabelle Stanton and Gabriel Kliot. Streaming graph partitioning for large distributed graphs. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1222-12022 2012.
Charalampos Tsourakakis, Christos Gkantsidis, Bozidar Radunovic, and Milan Vojnovic. Fennel: Streaming graph partitioning for massive scale graphs. In Proceedings of the 7th ACM international conference on Web search and data mining, pages 333-342, 2014.
Cong Xie. Ling Yan, Wu-Jun Li, and Zhihua Zhang. Distributed power-law graph computing: Theoretical and empirical analysis. Advances in neural information processing systems, 27, 2014.
Fabio Petroni, Leonardo Querzoni, Khuzaima Daudjee, Shahin Kamali, and Giorgio lacoboni. Hdrf: Stream- based partitioning for power-lav graphs. In Proceedings of the 24th ACM international on conference on information and knowledge managemeni, pages 243-252. 2015.
Rong Chen, Jiaxin Shi, Yanzhe Chen, Binyu Zang, Haibing Guan, and Haibo Chen. Powerlyra: Differentiated graph computation and partitioning on skewed graphs. ACM Transactions on Parallel Computing (TOPC), 5(3):1-39, 2019b.
Onur Mutlu, Saugata Ghose, Juan Gómez-Luna, and Rachata Ausavarungnirun. A modern primer on processing memory. Emerging computing: from devices to systems: looking beyond Moore and Von Neumann, pages 171-243, Springer, 2022.
Joseph Reagle and Lauren Rhue. Gender bias wikipedia and britannica. International Journal of Communication, 5:21, 2011.
Tolga Bolukbasi, Kai- Wei Chang, James Y Zou, Venkatesh Saligrama, and Adam Kalai. Man is to computer programmer as woman is to homemaker? debiasing word embeddings. Advances in neural information processing systems, 29, 2016.
Joseph Fisher, Arpit Mittal, Dave Palfrey, and Christos Christodoulopoulos. Debiasing knowledge graph embeddings. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7332-7344 2020.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope. Both abstract and introduction clearly articulate the paper's contributions.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section
6 discusses limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
17

---

Answer: [Yes]
Justification: Appendix D.2 provides a complete proof of the main theoretical result, and discusses the full set of assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All the code necessary to reproduce the results is provided in an anonymized zip file.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
18

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the code provided an anonymized zip file. After publication, the code of the method has been released at this address: https:/giitab.com/sddddiiiiaaass
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
public/guides/ Staalees//ooeSSuusmsiiiiiie.i
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/ccpppllligggddeeeeeeeeeeee Coaee//dddeSebmmmcma ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental setting is presented in detail in appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Critical difference diagrams associated with statistical significance tests are provided with the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
19

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experimental setup is fully described appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research conducted in the paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Appendix G.4 discusses potential societal impacts of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
20

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All original papers are cited.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
21

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
22

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy buttps://neure wwwpariipp..ccoooeeeeeeeeeea /t/CCooffeeence///2222 for what should or should be described.
23

---

Appendix Table of Contents
Datasets
25
A.1 Statisties on knowledge graph datasets
25
A.2 Downstream tables
25
A.3
Entity coverage of downstream tables
26
Evaluation methodology
28
Downstream tasks
28
B.2
Knowledge graph completion
................................
29
B.3
Experimental setup
32
Additional evaluation of SEPAL
32
Table-level downstream results on real-world tables
32
Table-level downstteam results on WikiDBs tables
32
SEPAL combined with more embedding models
................................
32
More baselines on the Freebase dataset
................................
C.5
Evaluation on prior benchmark
35
C.6 Evaluation on knowledge graph completion
36
Theoretical analysis
36
D.I Analysis of SEPAL's dynamic and analogies to eigenvalue problems
37
D.2 Formal proof of Proposition 4.1
39
Presentation and analysis BLOCS
40
E. Prior work on graph partitioning
40
Detailed algorithm and pseudocode
41
Benchmarking BLOCS against partitioning methods
42
Effect of BLOCS' stopping diffusion threshold
44
E.5
How distant from the core are the outer entities?
44
Further analysis of SEPAL
45
Execution time breakdown
45
F2
SEPAL's hyperparameters
46
Ablation study: SEPAL without BLOCC
Speedup over base embedding model
51
Discussion
52
Comparison to prior work
52
Communication costs of SEPAL
53
G.3
Outlook continual learning
54
Broader impacts
55
24

---

Table 2: Additional statistics on the knowledge graph datasets used. MSPL stands for Mean Shortest Path Length. The LCC column gives the percentage of entities of the graph that are the largest connected component.
Maximum degree
Average degree
MSPL
Diameter
Density
LCC
Mini YAGO3
65 711
12.6
3.3
11
le-4
99.98%
YAGO3
934 599
4.0
4.2
23
2e-6
97.6%
YAGO4.5
6 434 121
4.5
5.0
502
le-7
99.7%
YAGO4.5+T
434 122
5.0
4.0
1e-7
100%
YAGO4
606 980
12.9
4.5
28
3c-7
99.0%
YAGO4+T
32 127 569
9.4
3.4
le-7
100%
Freebase
10 754 238
4.9
4.7
100
6e-8
99.1%
WikiKG90My2
37 254 176
12.8
3.6
98
le-7
100.0%
Table Number of rows in the downstream tables.
US elections
Housing prices
US accidents
Movie revenues
Number of rows
13 656
22 250
20 332
7 7,38
A Datasets
A.1 Statisties on knowledge graph datasets
Maximum and average degree figures highlight the scale-free nature of real-world knowledge graphs. The values for mean shortest path length (MSPL.) and diameter (the diameter is the longest shortest path) are provided for the largest connected component (LCC). They are remarkably small, given the number of entities in the graphs. Contrary to other datasets, YAGO4.5, Frecbase, and WikiKG90Mv2 contain 'long chains' of nodes, which account for their larger diameters.
More statistics the knowledge graph datasets given in Table 2
The density D is the ratio between the number of edges E| and the maximum possible number of edges:
E
D
VIO -1
where | denotes the number of nodes.
The LCC statisties show that for each knowledge graph, the largest connected component regroups almost all the entities.
A.2 Downstream tables
Real-world tables We use 4 real-world downstream tasks adapted from CCetkov-Iliev et al. [2023 who also investigate knowledge-grand embeddings facilitate machine learning. The specific target values predicted for each dataset are the following:
US elections: predict the number votes per party in US counties;
Housing prices: predict the average housing price in US cities;
US accidents: predict the number of accidents in US cities;
Movie revenues: predict the box-office revenues of movies.
For each table, a log transformation is applied to the target values as a preprocessing step. Table contains the sizes of these real-world downstream tables.
WikiDBs tables WikiDBs contains 100,000 databases (collections of related tables), which alto- gether include 1,610,907 tables. We extracted 42 those tables to evaluate embeddings. Here we describe the procedure used for table selection and processing.
25

---

Table 4: Regression tables from WikiDBs. The 'DB number' is the number of the database in WikiDBs from which the table was taken. Among these 16 regression tables, are used for validation, and 14 for test.
Table name
DB number
Value to predict
Nows
Set
Historical Figures
62 826
Birth date
3 000
Val
Geopolitical Regions
66 610
Land area
2 324
Val
Eclipsing Binary Star Instances
3.977
Apparent magnitude
Test
Research Article Citations
14.012
Publication date
3 000
Test
Drawings Catalog
14 976
Artwork height
3 000
Test
Municipal District Capitals
19 664
Population count
2 846
Test
Twinned Cities
28 146
Population
1 194
Test
Ukrainian Village Instances
28 324
Elevation (meters)
000
Test
Dissolved Municipality Records
46 159
Dissolution date
3 000
Test
Research Articles
53 353
Publication date
3 000
Test
Territorial Entities
82 939
Population count
3 000
Test
Artworks Inventory
88 197
Artwork width
3 000
Test
Business Entity Locations
89 039
Population count
3 000
Test
WWT Personnel Profiles
89 439
Birth date
3 000
Test
Registered Ships
90 930
Gross tonnage
3 000
Test
Poet Profiles
94 062
Death date
3 000
Test
Table selection: Most of the WikiDBs tables are very small -typically a few dozen samples- so our first filtering criterion was the table size, which must be large enough to enable fitting an estimator. Therefore, we randomly sampled 100 tables from WikiDBs with sufficient sizes (Nrows > 1, 000). Then we looked at each sampled table individually and kept those that could be used to define relevant machine learning task (either regression or classification). We ended up with 16 regression tasks and 26 classification tasks.
Table processing: We removed rows with missing values, and reduced the size of large tables keep evaluation tractable. For regression tables, we simply sampled 3,000 rows randomly (if the table had more than 3,000). We applied log transformation to the target values to remove the skewness of their distributions. Before that, dates were converted into floats (by first converting them to fractional years, and then applying the transform & + 2025 t). For classification tables, reduce the dataset sizes while preserving both class diversity and balance, we downsampled the tables with the following procedure:
1. Class filtering: we set a threshold r = m50, 0.9/2),, where N₂ is the cardinality of the second most populated class, and retained only the classes with more than occurrences.
2. Limit number of classes: if more than 30 classes remained after filtering, only the 30 most frequent were kept.
3. Downsampling: the resulting table contained more than 3,000 rows, we sampled rows such that: (a) if r Netasses S 3, 000, at least r rows were sampled per class, (b) Nolasses > 3. 000, we sampled an approximately equal number of rows per class, fitting within the 3,000-row limit.
The specifications of the 42 tables extracted are given in Table 4 and Table 5
A.3 Entity coverage of downstream tables
Entity coverage We define the coverage of table T by knowledge graph K as the proportion of downstream entities in T that are described in K. Figure 4lgives the empirically measured coverage of the 46 downstream tables by the 8 different knowledge graphs used in our experimental study. It shows that larger and more recent knowledge graphs yield greater coverage.
Entity matching Leveraging knowledge-gran embeddings to enrich downstream tabular predic- tion task requires mapping the table entries to entities of the knowledge graph. We call this process entity matching.
26

---

WikiDBs classification tables
Mini YAGO3
YAGO3
Freebase
YAG04
YAGO4
Lasonomny
YAGO4.5
YAG04.5
+ Lazonommy
WikUKG9OMYZ
Artist Copyright Representation
0.5
9.6
6.3
56.3
36.4
93366
99
99.7
100
Artworks Catalog
0.0
0.0
0.0
0.0
0.0
57.4
93.44
98.22
Creative Commons Authors
1.3
7.5
3.6
93.8
93.9
99.5
99.8
96.9
Decommissioned Transport Stations
0.2
2.3
2.4
45.6
69.1
81.8
94.11
77.9
Defender Profiles
10.9
27.6
13.4
78.5
78.5
99.
Forward Players
23.4
Geographer Profiles
0.6
16.1
11.4
72.4
72.7
95.9
96.1
80.0
Historic Buildings
0.0
1.4
0.7
56.3
63.7
90.8
91.6
76.3
Historical Pigures
2.7
71.4
26.5
99.5
99.5
98.7
98.7
99.7
Island Details
0.1
5.7
3.7
67.0
89.0
96.7
98.1
91.9
Kindergarten Locations
0.0
0.0
0.0
93.1
98.0
99.9
99.99
96.77
Magic Narralive Molifs
0.0
0.0
0.1
0.0
0.1
0.0
100.0
0.1
Published
Noble Individuals
12.3
46.5
52.1
95.7
95.7
94.5
97.66
Notable Trees Information
0.0
0.1
0.4
11.5
48.1
83.7
84.1
83.3
Parish Church Details
0.0
1.3
1.4
54.77
58.0
69.4
69.5
91.0
Philosopher Profiles
2.8
29.4
24.55
80.0
80.5
97.1
97.2
86.0
Rafael Individuals
1.8
11.6
7.8
87.1
87.3
96.5
96.7
93.6
Researcher Profile
4.6
22.8
8.0
92.4
93.7
98.7
100.0
100.0
Sculpture
Spring Locations
State School Details
0.0
2.0
0.0
12.7
14.4
23.1
23.5
21.6
Striatum Scientiftc Articles
0.0
0.0
0.0
100.0
100.0
0.7
1.0
100.0
Sub Post Office Details
0.0
0.0
0.0
100.0
100.0
100.0
100.0
100.0
Surname Details
0.0
0.2
0.1
97.4
98.4
0.4
0.4
99.4
Average
2.4
13.3
8.4
66.9
73.1
76.7
84.88
85.7
Coverage (%)
WikiDBs
regression tables
Artworks Inventory
100.0
Business Entity Locations
36.3
20.8
92.0
97.7
98.0
97.1
98.5
99.9
Dissolved Municipalily Records
0.0
1.4
2.0
9.6
82.1
99.9
99.9
99.8
Drawings Catalog-
0.0
0.0
0.0
60.1
60.5
91.6
96.6
69.1
Eclipsing Binary Star Instances
0.0
0.0
0.0
0.0
70.5
0.0
100.0
100.0
Geopolitical Regions
52.6
63.2
77.0
82.9
83.3
97.9
98.3
100.0
Historical Figures
0.5
14.0
9.7
B4.7
84.8
97.8
97.8
91.8
Municipal District Capitals
12.1
Profiles
23.9
Registered Ships- 0.0
0.0
0.3
38.8
60.6
Research Article Citations 0.0
0.0
0.0
97.3
98.1
9.3
10.9
99.9
Research Articles
0.0
0.0
0.0
64.9
A6.2
1.9
2.8
99.6
Territorial Entities
24.1
64.1
84.2
96.4
97.1
99.1
99.4
99.7
Twinned Cities
60.1
76.8
98.1
98.8 8
98.8
97.7
97.7
100.0
Ukrainian Village Instances
0.0
1.0
1.1
99.9
100.0
100.0
100.0
100.0
Personnel Profiles
36.9
93.3
Average
11.8
25.4
28.6
68.7
80.4
76.0
86.6
68.6
Real-world regression tables
Housing prices
19.1
92.2
85.6
99.1
99.8
99.7
99.7
99.8
Movie revenues
27.7
62.3
89.1
99.4
99.5
99.4
99.4
99.4
US accidents
21.1
67.3
78.6
96.8
98.0
97.6
97.6
97.9
US elec
74.1
99.3
98.3
99.1
99.1
99.0
99.0
98.1
Validation table
Test table
Average
Figure 4: Entity coverage of downstream tables. Over the 46 downstream tables 4 are used for validation (in blue), and 42 are used for test (in maroon).
27

---

Table 5: Classification tables from WikiDBs. The DDB number' is the number of the database in WikiDBBs from which the table was taken. Among these 26 classification tables, 2 are used for validation, and 24 for test.
Table name
DB number
Class to predict
N Nrws
Nlasses
Creative Commons Authors
510
Gender
2.999
Val
Historical Figures
73 376
Profession
004
5
Val
Historic Buildings
473
Country
2 985
30
Test
Striatum Scientific Articles
053
Journal name
2 2866
30
Test
Rescarcher Profile
136
Affiliated institution
237
7
Test
Decommissioned Transport Stations
730
Country 3983
30
Test
Artist Copyright Representation
7 900
Artist occupation
2 2986
27
Test
Forward Players
15 542
Team 2 985
30
Test
Rafael Individuals
29 832
Nationality
2
12
Test
Artworks Catalog
30 417
Artwork type
2991
17
Test
Magic Narrative Motifs
36 100
Cultural origin
2 2.993
12
Test
Geographer Profiles
42 562
Language
2 2.992
14
Test
Surname Details
47 746
Language
1 420
5
Test
Sculpture Instances
56 474
Material used
2 9885
30
Test
Spring Locations
63 797
Country 981
30
Test
Noble Individuals
64 477
Role
2 2987
30
Test
Defender Profiles
65 102
Defender position 2 2998
5
Test
Kindergarten Locations
66 643
Country 2
4
Test
Sub Post Office Details
67 195
Administrative territory
2986
30
Test
State School Details
70 780
Country 299
12
Test
Notable Trees Information
70 942
Tree species 2.992
19
Test
Parish Church Details
87 283
Country 2 2993
15
Test
Museum Details
90 741
Country 9866
30
Test
Island Details
92 415
Country 9986
30
Test
Philosopher Profiles
97 229
Language 2 2,95
29
Test
Music Albums Published in the US
97 297
Music Genre 2 989
30
Test
For the 4 real-world tables, we performed the entity matching 'semi-automatically" following Cvetkov-Iliev et al.] [2023). The entries of these tables are well formatted and small set of simple rules is sufficient to match the vast majority of entities. Human supervision was required for some cases of homonymy, for instance.
For the WikiDBs tables, we used the Wikidata Q identifiers (QIDs) included in the WikiDBs dataset to straightforwardly match the entities to WikikG90Mv YAGO4, and YAGO4.5, which all provide the QIDs for every entity. YAGO4 also offers a mapping the Freebase entities, which we used to match the Freebase entities to the WikiDBs tables. Additionally, both YAGO3 and YAGO4 provide mappings to DBpedia, which enabled us obtain the matching for YAGO3.
B Evaluation methodology
B.1 Downstream tasks
Setting For each dataset, we use scikit-learn's Histogram-based Gradient Boosting Regression (resp. Classification) Tree [Pedregosa et al.) 2011 as regression (resp. classification) estimator to predict the target value. The embeddings are the only features fed to the estimator, except for the US elections dataset for which we also include the political party. For embedding models outputting complex embeddings, such as RotatE, we simply concatenate real and imaginary parts before feeding them to the estimator. Figure Jilllsstrats our evaluation setting.
The rows of the tables corresponding to entities not found in the knowledge graph are filled with NaNs as features for the estimator. This enables to compare the scores between different knowledge graphs (see Figure 2) and Figure 3) of different sizes to see the benefits obtained from embedding larger graphs, with better coverage of downstream entities (Figure 4).
'Entity mapping for WikiKG90Mv2 is provided http::/ggrousseeooocccoo///////p bennchmaak/cRROSKt$QQyy..
28

---

100M+ entities 600M+ facts
KG embeddings
WIKIDATA
Movie embeddings
Year
Rating
Revenue
0.1, -0.3. 0.8
2009
7.9
2.985
Movie
Year
Rating
Revenue
2.965
-0.2, -0.3, 0.1
1993
8.2
??
-0.7, 0.4, ... -0.1
1982
7.9
??
Jurassic Park
1993
8.2
??
E.T.
1982
7.9
downstream estimator
Figure 5: Illustration of our evaluation setting for downstream tasks. Embeddings computed on an external knowledge graph are used enrich the features of a downstream table. The utility of these embeddings is measured by the improvement they bring to the predictions of a downstream estimator.
Metrics
The metric used for regression is the R2 score, defined as:
(y/ 0.)2 (ys g)²
R
where N is the number of samples (rows) in the target table, y is the target value of sample i, 9: is the value predicted by the estimator, and y is the mean value of the target variable. For classification, we use the weighted F1 score, defined as:
K
Fl weighted
F1;
where K is the number of classes, n; is the number of true instances for class N = Σ n2 is the total number of samples, and F1, the F1 score for class
To get the "Mean score (normalized)" reported on Figure 2 and Figure we proceed as follows:
1. Mean cross-validation score: for each mode and evaluation table, the scores (R2 or weighted F1, depending on the task) are averaged over 5 repeats of 5-fold cross-validations.
2. Normalized: for each evaluation table, we divide the scores of the different models by the score of the best-performing model this table. This makes the scores more comparable between the different evaluation tables.
3. Average: for each model, we average its scores across every evaluation table. The highest possible score for a model is 1. Getting score of I means that the model beats every other model on every evaluation table.
Validation/test split and hyperparameter tuning We use 4 of the 42 WikiDBs tables as validation data-2 for regression and for classification tasks (seeFigure 4). The remaining 38 WikiDBs tables, along with the 4 real-world tables, are used exclusively for testing.
The validation tables are used for each method and each knowledge graph. Unless otherwise specified, all reported results are obtained on the test tables using these optimized configurations.
hyperparameters and select the best-performing configuration
B.2 Knowledge graph completion
We detail our experimental setup for the link prediction task:
We define "model" the combination of method (e.g. DistMult, DGL-KE, etc.) and a knowledge graph which it is trained.
29

---

YAGO3 (2.6M entities, 5.6M triples)
SEPAL
15 min
FastRe
42
DGL-KE
21 min
DistMult
14 min
Py Torch-BigGrrat NidePiece
21 min
YAG04.5 (32M entities, 75M triples)
SEPAL FastRP
4
17 min
DGL-KE
NodePiece DistMult
4
17
Out of memory GPU 3268)
YAG04.5 + taxonomy (50M entities, 128M triples)
SEPAL FastRP DGL-KEI TyTorc--iggGaap DistMuit NodePiece
48 min
4
29
Out of memory GPU (> 32GB)
Out memory GPU (> 326B)
YAGO4 (38M entities, 250M triples)
SEPAL FastRP DGL-KE PoTorch-Big Biggrphh DistMult NodePiece
28 min
h
21
Out memory GPU 32GB) Out memory GPU 32GB)
YAG04 taxonomy (67M entities, 320M triples)
SEPAL
Porchch-Bigge BigGraph DGL FastRP DistMult NodePiece
55
17
memory
memory 32GB)
memory 32GB)
Freebase (85M entities, 338M triples)
SEPAL
PyTorch-Big Braaph
DGL-KE
FastRP
memory
DistMult
memory
NodePiece
memory 326B)
WikikG90Mv2 (91M entities, 601M triples)
SEPAL
PyTorch-Bla BigGraph
89
17
FastRP
Out memory CPU 400GB) Out GPU 32GB)
DislMult
NodePiece
Out memory GPU 32GB)
2
Cumulative normalized cross- validatai
Evaluation dataset
Movie revenues
US elections
US accidents
Housing prices
Figure Detailed results on real-world tables. The "Cumulative normalized mean cross-validation score" reported is obtained by summing the normalized mean cross-validation scores. For an evaluation dataset, corresponds to the best R2 score across all models; as there are 4 evaluation datasets, the highest possible score for model is 4 (getting score of 4 means that the model beats every model on every evaluation dataset). SEPAL, PyToorch-Bi PyTorch-BigGraph, DGL-KE, and NodePiece use DistMult base model. Embedding computation times provided on the right- hand side of the figure. Figure 8 eeetends this figure with other embedding models.
30

---

Regression (14 tables)
Classification (24 tables)
Ihe coverage tacliet
SEPAL (15min)
SEPAL (15min)
mean score
DistMult (14min)
PBG (2h)
YAGO3
FastRP (42s)
DGL KE (21min)
5.6M triples
FastiP
PBG (2h)
DistMult (14min)
NodePlece (21min)
NodePlece (21min)
SEPAL (7h)
SEPAL (7h)
YAG04
FastRP (28min)
FastPP (2 (28min)
38M entities
25 DM triples
(21h)
DGL KE (8h)
DGL KE (8h)
SEPAL (7h)
SEPAL (7h)
YAGO4+T 67M entities
(55h)
320M triples
DGL-KE
DGL-KE (17h)
SEPAL (4h)
PBG (17h)
YAG04.5
FastRP (17min)
SEPAL (4h)
32M entities
DGL-KE (2h)
FastRP (17min)
75M triples
(17h)
DGL-KE
NodePiece (4h)
NodePiece (4h)
SEPAL (3h)
SEPAL (3h)
YAG04,5+T S0M entities
FastRP (48min)
PBG (29h)
128B triples
DGL-KE (4h)
FastRP (48min)
PBG (29h)
DGL-KE (4h)
SEPAL (10h)
SEPAL (10h)
Freebase
85 entities triples
PBG (34h)
PBG (34h)
DGL-KE (11h)
(11h)
SEPAL (21h)
SEPAL (21h)
WikiKG90Mv2
PBG (89h)
PBG (89h)
triples
DGL-KE (17h)
DGL-KE (17h)
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Normalized
Normalized weighted F1
Figure 7: Detailed results on WikiDBs tables. Each black dot represents a downstream table. Red vertical lines indicate the mean score over all the tables. The methods appear in decreasing order of average score.
Setting: We evaluate models under the transductive setting: the missing links to be predicted connect entities already seen in the train graph. The task is to predict the tail entity of triple, given its head and relation.
Stratification:
We randomly split each dataset into training (90%), validation (5%), and test (5%) subsets of triples. During stratification, we ensure that the train graph remains connected by moving as few triples as required from the validation/test sets to the training set.
Sampling: Given the size of our datasets, sampling is required to keep link prediction tractable. For each evaluation triple, we sample 10,000 negative entities uniformly to produce 10,000 candidate negative triples by corrupting the positive.
Filtering: For tractability reasons, we report unfiltered results: we do not remove triples already existing in the dataset (which may score higher than the test triple) from the candidates.
Ranking: If several triples have the same score, report realistic ranks (i.e., the expected ranking value over all permutations respecting the sort order; see PyKEEN documentation [Ali et 2021b)).
31

---

Metrics:
We use three standard metrics for link prediction: the mean reciprocal rank (MRR). hits (for k {1, 10, 50}) and mean rank (MR). Given the rankings " In of the evaluation (validation or test) triples:
MRR
Σ 72
1
1
Hits@k
Σ 71
1
n
n MR
1
T
T2
B.3 Experimental setup
Baseline implementations In our empirical study, we compare SEPAL DistMult, NodePiece, PBG. DGL-KE, and FastRP. We use the PyKEEN [Ali et al. 2021b] implementation for DistMult and NodePiece, and the implementations provided by the authors for the others. PBG was trained on 20 CPU nodes, and DGL-KE was allocated 20 CPU nodes and 3 GPUs; both methods were run on single machine. The version of NodePiece we use for datasets larger than Mini YAGO3 is the ablated version, where nodes are tokenized only from their relational context (otherwise, the method does not scale on our hardware). For PBG, DGL-KE, NodePiece, and FastRP we used the hyperparameters provided by the authors for datasets of similar sizes. SEPAL and DistMult's s hyperparameters were tuned on the validation sets presented in Appendix B. and Appendix B.2
For all the baseline clustering algorithms, we used the implementations from the igraph pack- age [Csardi 2013) except for METIS, HDRF and Spectral Clustering. For METIS, we used the
torch-sparse implementation, for Spectral Clustering, the scikit-learn [Pedregosa et al. 2011] imple- mentation, and for HDRF, we used the C++ implementation from this repository
Computer resources For PBG and FastRP, experiments were carried out on a machine with 48 cores and 504 GB of RAM. DistMult, DGL-KE, NodePiece, and SEPAL were trained on Nvidia V100 GPUs with 32 GB of memory, and 20 CPU nodes with 252 GB of RAM. The clustering benchmark was run on a machine with CPU nodes and 504 GB of RAM.
C Additional evaluation of SEPAL
C.1 Table-level downstream results on real-world tables
Figure 6Jshows the detailed prediction performance on the downstream tasks. SEPAL not only scales well to very large graphs (computing times markedly smaller than Pytorch-BigGraph) but also creates more valuable node features for downstream tasks.
C.2 Table-level downstream results on WikiDBs tables
Figure 7
shows the detailed downstream tasks results for the WikiDBs test tables. For regression, SEPAL is the best performer on average for all of the knowledge graphs. For classification, SEPAL the best method 6 of knowledge graphs (narrowly beaten by PBG YAG04.5). Interestingly, FastRP, despite being very simple and not even accounting for relations, is a strong performer and beats more sophisticated methods like PBG and DGL-KE on many tasks. This is consistent with our queriability analysis in section 4 concluding that global methods, such as FastRP and SEPAL, are more suitable for downstream tasks, than local methods (such as PBG and DGL-KE).
For some knowledge graphs (especially Freebase and YAGO3), we can see two modes the scores distribution, corresponding the tables with low and high coverages (Figure 4).
C,3 SEPAL combined with more embedding models
Figure 8
extends the results of Figure 6 by adding TransE and RotatE, alone and combined with SEPAL, as well as ablation studies results combined with METIS or ablated from BLOCS.
These results show that SEPAL systematically improves upon its base model, whether be DistMult
RotatE or TransF. For a fair comparison, we ran RotatE with embedding dimension d = 50, as
outputs complex embeddings having twice many parameters, For other models, we use d 100.
32

---

YAGO3 (2.6M entities, 5.6M triples)
METIS FaSER
DistMult
15 min
42 6
SEPAL without
BLOCS
DistMult
SEPAL
11 min
14 min
DistMult PyTorch RotatE
Biggrap
17
12
Transe
21 min
DistMult NodePiece
YAG04.5 (32M entitles, 75M triples)
SEPAL METIS EastR RotatE SEPA
4h
17 min
h
DistMulE + DGL-KE
IransE SEPAL
DistMuult NodePiece DistMult +. Py forch Biggraa
4
SEPAL W Without BLOCS
memory GPU (> 32G81
17
DistMult
memory GPU (> 3268) Out of memory GPU (> 3208)
Ro
YAG04.5 + taxonomy (50M entities, 128M triples)
DistMult SEPAL
h
PastR
RotatE SEPA
3 h
DistMult
Poror
Biggrapn
29 h
TransE SEPAL
SEPAL without
GPU
DistMult Out memory GPU [> 32GB
TransE
Out of memory GPU (> 32GB)
DistMult
NodePicc
memory GPU [> 32G81
KolalE
SEPAL
memory CPU (- 10008)
YAGO4 (38M entities, 250M triples)
DistMult RotatE
SEPA
h
FastR
28
TransE SEPA
KE
B
DistMult PV Trrrch-
SEPAL W without BigGrapD
Torch-Blngrap
21
memory GPL 32G8)
DistMult
Out memory GPU [> 3268)
DistMult
NodePiece
Dut of memory GPU (> 32GB)
Rota
mimory
SEPAL METIS
CPU
YAGO4 + taxonomy (67M entitles, 320M triples)
DistMult
EAA
RotatE
SEPAL Biggrapi
DistMult Py Pyrcoc-- Distmult
Out memory CPU (> 400G8) 4000G8)
SEPAL without
B BLOCS
Out of memory GPU (> 32GB1
D Stsu
memory GPU [> 32G81
TransE
DistMult NodePicc Rola.E SEPAL METIS
Out memory GPU (> 3268)
Dut of memory GPU (> 32G81
memory
100G8]
Freebase (85M entities, 338M triples)
DistMult SEPAL IransE -orro--iiGrap Biggraph
DistMult
34
RotatE SEPAL
DistMult DGG-KE
11
SEPAL without BLOCS
memory GPU [> 32G81
DistMult TransE
Out of memory GPU (>- 32GB1
memory GPU 32G81
DistMult NodeFiece
memory GPU (> 32681
SEPAL METIS
Out of memory CPU (> 100G8)
WikIKG90Mv2 (91M entities, 601M triples)
DistMult SEPAL
21
Rotate
Iranse
SEPAL
52
DistMult Morch-Biggrap DistMult
89
DGL-K
17 h
FastRi
memory 400G8]
SEPAL without DistMult
memory GPU 32G81
Out of memory GPU 32GB1
DistMult
NodePiece
memory GPU (> 32G81
SEPAL KolatE
memory CPU (> 100G8)
0.0
0.5
3.5 Cumulative normalized mean cross-validation score
1.0
1.5
2.0
2.5
3.0
4.0
Evaluation dataset
Movie revenues
US accidents
US elections
Housing prices
Figure 8: Performance real-world downstream tables.
33

---

Table 6: Results for link prediction. Best in bold, second underlined.
YAG04.5+T
WikiK990M22
YAGO3
YAG04.5
YAGO4
YAGO4+T
Freebase
Average
a. MRR
DistMult
0.8049
NodePiece
0.2596
0.4456
PBG
0.5581
0.5539
0.5688
0.6406
0.6224
0.7389
0.6325
0.6165
DGL-KE
0.7284
0.6200
0.6469
0.2372
0.2570
0.3017
0.3202
0.4445
SEPAL
0.6501
0.5537
0.5646
0.4726
0.477
0.5378
0.5291
0.5407
Hits@1 1
DistMult
0.7400
NodePiece
0.1735
0.3449
PBG
0.5000
0.4939
0.4977
0.5494
0.5416
0.7015
0,5568
0.5487
DGL-KE
0.6663
0.5511
0.5733
0.1642
0.1892
0.2498
0.2416
0.3765
SEPAL
0,5412
0.4913
0.4922
0.3746
0.3755
0.4824
0,4502
0.4582
Hits@ 10
DistMult
0.9059
NodePiece
0,4388
0.6379
PBG
0.6562
0.6642
0.7021
0.803
0.7662
0.8053
0.7693
0.7380
DGI-KEE
0.8293
0.7446
0.7821
0.3786
0.3842
0.3964
0,4694
0.5692
SEPAL.
0.8394
0.6650
0.6871
0.6573
0.6778
0.6398
0.6739
0.6915
d. Hits @o 50
DistMult
0.9504
NodePiece
0.7358
0.8112
PBG
0.7259
0.7734
0.8136
0.8891
0.8514
0.8541
0.8531
0.8229
DGL-KE
0.8873
0.8171
0.8748
0.6037
0.5968
0.5547
0.654
0.7126
SEPAL
0.9204
0.7698
0.7786
0.7661
0.8068
0.7476
0.7805
0.7957
.RR
DistMult
64.19
NodePiece
154.7
263.2
PBG
820.9
408.0
300.3
117.1
203.5
243.4
227.3
331.5
DGL-KE
187.7
624.1
219.9
224.9
271.5
227.0
186
277.3
SEPAL
95.87
270.4
206.0
553.0
363.2
357.3
365.5
315.9
C.4 More baselines on the Freebase dataset
The Freebase dataset has been used in several previous works. To further validate SEPAL's perfor- mance, we compare additional baselines from the large-scale KGE literature: GraSH [Kochsiek] al. 2022), efficient hyperparameter optimization framework for large-scale KGEs, and SMORE [Ren al. 2022). a scalable KGE method supporting single-GPU training and multi-hop reasoning.
We train both of these baselines with DistMult as the base embedding method, on Freebase, using the authors' released configurations for this dataset, Table repprts the normalized scores four real-world regression tasks, along with total training time.
We trained SMORE for I million iterations relatively low performance here suggests that longer training could improve results, but under a 6-hour budget, SEPAL substantially better.
GPU, following the authors' configuration. Its
GraSH optimizes hyperparameters for link prediction using successive halvings to discard unpromis- ing 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.
34

---

Table 7:
Comparison to additional baselines on Freebase. Normalized mean cross-validation scores on real-world downstream tasks, along with total training time. SEPAL outperforms all baselines while being the fastest to train.
Method
Housing prices
Movie revenues
US accidents
US elections
Time
PBG
0.513
0.723
0.742
0.957
33h 42m
DGL-KE
0.445
0.610
0.686
0,962
10h 50m
SMORE
0.160
0.332
0,410
0.926
6h 15m
GraSH
0.601
0.862
0,810
0.961
32h 33m
SEPAL 0.868
0.880
0.953
1.000
5h 58m
Table 8: Evaluation on Ruffinelli et al.'s benchmark. Classification and regression results on FB 15k-2337 (14k entities, 272k triples), YAGO3-10 10 (123k entities, 1M triples), and Wikidata5M (4.8M entities, 21M triples). Best results for each task are in bold.
Dataset
Method
Classification weighted F1 Regression RSE +
ComplEx (MTT)
0.858
0.394
RotatE (MTT)
0,890
0.573
FB15k-237
KE-GCN
0.829
0.501
SEPAL
0.853
0.492
DistMult (MTT)
0.746
0.472
TransE (MTT)
0.723
0.441
YAGO3-10
KE-GCN
0.700
0.398
SEPAL
0.762
0.386
TransE (STD)
0.596
Wikidata5M
SEPAL
0.568
C.5 Evaluation on prior benchmark
Ruffinelli and Gemulla [0244] propose a benchmark for evaluating KGE methods on downstream
classification and regression. includes several KGE baselines, with varying training procedures, and the graph neural network KE-GCN for entity classification. For each knowledge graph (FB 155k- 237, YAGO3-10, Wikidata5M), they evaluate embeddings on downstream tasks created from entity attributes of the knowledge graph.
We put the evaluation on this benchmark in appendix because our goal in this paper is evaluate external, real-world tasks (Figure 2 that are independent of a specific knowledge graph, to compare the benefits of diverse knowledge graphs. In contrast, the Ruffinelli al. tasks are created artificially and associated with specific knowledge graphs, that are orders of magnitude smaller than those of our main study.
However, evaluating SEPAL on these datasets complements our main experiments and enables direct comparison with prior work. Thus, used 128-dimensional embeddings to match one of the dimensions Ruffinelli et al.'s hyperparameter search space. We also used the authors' released evaluation script for comparable results. For each knowledge graph, Table reports:
1. The best KGE method for classification from Ruffinelli and Gemulla (2024)
2. The best KGE method regression from Rufhnelli and Gemulla 2024
3. KE-GCN results from Ruffinelli and Gemulla 2024
4. SEPAL results.
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 knowledge graphs. FB15k 5k-237, SEPAL has weaker results, but this may be due to the dataset size (FB15k-237 has 14k entities, 185 to 6,500 times smaller than the graphs considered in our main evaluation). For these tiny graphs, which fall outside SEPAL's intended scope, SEPAL may not adapted because the core becomes too small to leam good representations for the relations and core entities.
35

---

Reciprocal Rank
Hits@10
Rank
2.0
2.5
Figure Critical difference diagrams on link prediction metries. Statistical tests show no
significant difference between methods at significance level a = 0.05.
Regression Prediction
Classification Link
1.00
0.95
Datasets
YAG04.5
0.90
YAGO4
Froebase
Moan waighted
(nommalino
YAGO4+T
WIKKGG90M22
0.6
0:17
0.85
YAG04.5
Slope 0:33
Slope 0.11
R2
Methods
0.4
SEPAL
NodeFiece
0.75
PBG
DistMult
0.70
0.2
MAR
MRR
Figure 10: Downstream task performance against link prediction performance, validation sets. Linear regression, with 95% confidence interval. We plot the performance models that share the same hyperparameters on the train graph (used for link prediction) and the full graph (used for downstream tasks).
C.6 Evaluation on knowledge graph completion
C.6.1 Link prediction results
Table provides the link prediction results for the different metrics. It shows that, depending on the dataset, SEPAL is competitive with existing methods (DGL-KE, PBG) or not. However, none of the methods consistently better than the others for all datasets. Following the analysis in ssction 4 these results are expected given that SEPAL does not enforce local contrast between positive and negative triples through contrastive learning with negative sampling, like other KGE methods do, but rather focuses on global consistency of the embeddings. Link prediction is, by essence, a local task, asking to discriminate efficiently between positives and negatives. For this purpose, seems that negative sampling, absent from SEPAL's propagation, plays a crucial role.
Nevertheless, Figure shows that Friedman test followed by Conover's post-hoc analysis [Conover and Iman 1979 Conover [999] reveal no statistically sigmificant differences (at significance level 0.05) among the three methods that scale all the knowledge graphs (SEPAL, PBG, and DGL-KE), as indicated by the critical difference diagrams where all methods are connected by
black line.
From a hyperparameter perspective, contrary to downstream tasks, the hybrid core selection strategy (with both node and relation sampling) yields better results than its simpler degree-based counterpart. This highlights different trade-off's between downstream tasks and link prediction. For link prediction, good relational coverage seems
most, whereas for downstream tasks, the core density matters
most (Figure 22)
C.6.2 Downstream and link prediction performance weakly correlate
Figure 10 shows that embeddings performing well on downstream tasks do not necessarily perform well on link prediction, and vice versa. There is only small positive correlation between these two performances: R² 0.1.
D Theoretical analysis
Notations We use the following notations:
36

---

( E Raxd is the embedding matrix at step f. where each row is the embedding of an entity. Without loss of generality. we assume that the entities are ordered core first, then outer, so
write (()) O with O E Re the embedding matrix of core
(fixed) entities, and ! IR_ xd the embedding matrix outer (updated) entities at step t. ne and n, denote the number of core and outer entities, respectively, and n. + no is the total number of entities.
1R,.x
ww Rd: embedding of relation R. (fixed).
(4) = v ()) = f........
θ (1) n. 1,2
O00 1,d
O(1)
n.d E RRdd
n,2
vectorization of the embedding matrix.
P E Indxnd; global linear propagation matrix. e madxnd permutation matrix to reorder æ into core and outer blocks.
y Qx =
: 0n
E RRnd; reordered vector of embeddings. y() can also be
written as y
y E Rudxndd reordered update matrix. M can be written by block
M Q(I + PP)Q
M cc
M co
M
where M oo and M submatrices representing outer-to-outer
M
Moo
and core-to-outer influences.
D.1 Analysis of SEPAL's dynamic and analogies eigenvalue problems
This section presents a theoretical analysis of the SEPAL propagation algorithm. We provide a series of intuitive and structural analogies classic iterative methods numerical linear algebra. Our goal is to contextualize the algorithm's behavior under various assumptions and shed light on its dynamic properties. The analysis is carried out in the case of DistMult, which simplifies the propagation rule due to its element-wise multiplication structure.
SEPAL power iteration (no normalization, boundary conditions) We begin by analyzing the case without normalization or fixed embeddings. this setting, with the vectorized embedding matrix (t) E Rad the propagation equation (Fquation 6) becomes:
(++1) (I (P)
where P E Rddxxnd encodes the linear update based the knowledge graph structure and DistMult composition rule. The matrix is block diagonal:
((1)
0
(
0
Rnnxnd
(10)
((d)
where each block (kk) corresponds to the k-th embedding dimension and has:
P(A)
[w
(11)
(M.F.NJEK
p(k) can be seen as a weighted adjacency matrix of the graph, whose weights are the k-th coefficients of the relation embeddings of the corresponding edges. Here, each (v, r, u) E K. contributes a rank-1 update to based on w..
Therefore, in this setting, the problem is separable with respect to the dimensions, so each dimension be studied independently.
The recurrence in [Bquation Ieefines classical power iteration. general, it diverges unless spectral radius p(7 aP) < In our setting, norms can grow arbitrarily because P contains non-normalized adjacency submatrices whose eigenvalues are only bounded by the maximum degree of the graph. In practice, the normalization (studied below) prevents the algorithm from diverging.
37

---

With boundary conditions: non-homogeneous recurrence Now, we consider the SEPAL's setting where core entity embeddings are fixed and only outer embeddings evolve, still without normalization. We the reordered vector embeddings y (t) Qx(() Rud which can be written follows:
y yo
y
(12)
where ( is the embedding of entity The reordered update matrix M Q(T++ has the following block structure:
M
Min
M
Runxnd
(13)
M
Mn
where each block M ue entity u. the case of the DistMult scoring function, this block diagonal and takes the form:
RRdd encodes how the embedding of entity u contributes to the update of
((uraa)xx diag(w,) M uv + C(mmajje a diag(w,) otherwise,
if u + v.
(14)
where diag(w,) is the diagonal matrix with the relation embedding w, E It on the diagonal.
Thus, M is sparse block matrix, with each non-zero block being diagonal, and it linearly propagates information across entity embeddings via dimension -iise interactions determined by the DistMult
M cc M
Men
model. Grouping core and outer entities together, we can also write M
M oo
This allows us to rewrite the propagation equation to account for the boundary conditions. We obtain:
y !!
(++1) M y M oocler
(15)
where Mas represents signal propagation between outer nodes, and M encodes injection from the core nodes.
This is a non-hommgeneuus linear recurrence. If p( oo) 2 1, the outer embeddings diverge in norm.
Nonetheless, the structure is analogous to forced linear systems such as:
y++1 Ay, b,
where the long-term behavior is driven by the balance between eigenvalues of A and direction of b.
Normalization and Arnoldi-type analogy
SEPAL applies & normalization after each update:
0 + oa
(++1) (++1)
0 ((++1)
(16)
l0( oa.
1
which constrains every embedding to the unit sphere. This couples dimensions and prevents simple linear analysis. However, the recurrence
yo (t+1) M M ocMle:
(17)
followed by blockwise normalization of (*) (with a 6200 mixed norm), shares structural similarities with the Arnoldi iteration [Amolli 1951]:
Successive embeddings span Krylov subspace: after iteration f, without normalization, yo belongs to (C, b) = span (b, Ab, A²b... b.....,. A A with M oo and b = M Mo.ye. given that yo 0.
(0)
38

---

Core embeddings define the forcing direction (6 = ocH.).
Normalization serves as regularizer, preventing divergence in norm.
The Amoldi iteration is used to compute numerical upproximations of the eigenvectors of general matrices, for instance, in ARPACK [Lehoueq et al. [198]] This analogy suggests that the direction of outer embeddings stabilizes over time and aligns with form dominant generalized eigenvector of the propagation operator M, conditioned on the core. Therefore, the embeddings produced by SEPAL's propagation encapsulate global structural information on the knowledge graph.
D.2 Formal proof of Proposition 4.1
Gradient descent on & updates the embedding parameters 0, of an entity u with
0
(
(
(18)
(0
where 1) is the learning rate.
The mini-batch gradient satisfies
0 ( (00 w.,)
30
Σ
00(!)
(0
(h.r,))E8
a
8(000 u
0
$0 w.)
Σ (l.r.))BB A=u
Σ
00 (t)
a
(h.r.)))B
where B the mini-batch. Note that the previous identity is still true if the knowledge graph contains self-loops, due to DistMult's scoring function being product. Plugging the DistMult relational operator function d00n, w,) = On @ w, in the previous equation gives
20
(0(1)
(w, O )(0)
(0(() (1)
(w, O (())
Σ (brr,t)
Σ (k.Ae))
()
(0
00(1) (t)
h=a
t=u
Σ (hrrat)
w, (())
Σ
w
(h,))))
Σ (B.r,))EB
w. 0
Σ
(
wr).
(h.r:))
h=u
tmu
Therefore, going back to Equation 18, we get that
f ((+1) (()) + 7
Σ
(10
w.
+1
Σ
un @ 0.0
(19)
(B. Em
(h.r.))BB
h=
einbedding propugation update for a and B=SUC
We can see that the embedding propagation update only differs by a term that corresponds to the message passing from the tails to the heads. We did not include this term in our message-passing framework because we wanted SEPAL to adapt to any model whose scoring function has the form given by Equation In practice, the propagation direction tail head is already handled by the addition of inverse relations.
Therefore, parallel can be drawn between: 1) the outer subgraphs and mini-batches, 2) the number of propagation steps and the number of epochs, 3) the hyperparameter a and the learning rate.
After each gradient step, we normalize the entity embeddings to enforce the unit norm constraint. This procedure corresponds to projected gradient descent on the sphere [Bertsekas] 1997], where each update is followed by projection (via e normalization) back onto the feasible set. The energy
39

---

function & (Equation 7 is composed of inner products and element multiplications of smooth functions, thus it smooth, and gradient is Lipschitz continuous on the unit sphere. Under these conditions, the algorithm is guaranteed to converge to stationary point of the constrained optimization problem [Bertsekas]. 1997, Proposition 2.3.2]. The limit points of the optimization thus satisfy the first-order optimality conditions on the sphere.
Presentation and analysis of BLOCS E
E.1 Prior work on graph partitioning
Scaling up computation on graph, for graph embedding or more generally, often relies on breaking down graphs subgraphs. METIS [arrpis and Kumar, 1997. a greedy node-merging algorithm, popular solution. A variety of algorithms have also been developed to detect "communities", groups of nodes more connected together, often with applications on social networks: Spectral Clustering (SC) [Shi and Malik] [000]. the Leading Eigenvector (LE) method [Newman, [2006]. the Label Propagation Algorithm (LPA) [Raghavan al. [207]] the Louvain method [Blondel et al. 20088, the Infomap method Rosvall and Bergstrom 2008 and the Leiden method (Traag et al. 2019] which
Algorithm 1 BLOCS
Input: Graph G = EV) E)) with nodes V and edges E, hyperparameters i and m Output: List of overlapping connected subgraphs
8 5-+0 0
b list of subgraphs set of unassigned nodes
U+V
Step 1: Create subgraphs from super-spreaders' neighbors for each node u do
if deg(v) > 0.2 then
S, U + SplitMeighbors(1 max_size 0.2 m)
end if for
Step 2: Assign nodes to subgraphs by diffusion while IU > (1 - V do
Sn < {arg max.cu deg(1))
start with unassigned node with highest degree
while [Sa] < 0.8 do
Sk41 f- Diffuse(St)
: 11
end while
Append S to S, and update U
D Sk-1 is the last subgraph smaller than 0.8
end while
Step 3: Merge small overlapping subgraphs
<- SrrgeSmaa1Suubrrpphee (8, min size = m/2)
Step 4: Dilation and diffusion until all entities are assigned
p <-<00 0
create new subgraphs by diffusion every 5 rounds, to tackle long chains
while |U/ 0 do
divides p and p > then
repeat
6-00 So farg mar.max.cur deg(1:)
while [Sa] 0.8 m do
SEL1 +- Diffuse(St)
k 1-
end while
Append St-1 to S, and update U until i 10
i+i+1
end if
+ Dilate(S) : p+p+1
end while
Step 5: Merge small overlapping subgraphs again
S, E <- SyatematicMerge(( min_size 0.4
Step Split subgraphs larger than m
8, U < SplitLarggeSubrappssSS. max size = m)
S, U
1atrgmmphSSuggrpphs( (8, min size = m 22)
Return: 3, the set of overlapping subgraphs covering G
40

---

BLOCS
METIS
Leiden
Louvain
LE
Infomap
LPA
HDRP
300
RAM usage (GiB)
250
CPU RAM capacity
10a
Time (minn
200
10a
10a
10a
10a
10a
10
10a
10a
107
10a
Number of triples
Number of triples
Figure 11: Scalability of partitioning methods. Memory usage and time for 8 knowledge graphs of various sizes. The "CPU RAM capacity" dashed line represents the CPU RAM of the machine we used to run SEPAL (we used a different machine with more RAM to run this benchmark, see Appendix B.3p. Partitioning methods going beyond this limit thus cannot be combined with SEPAL on our hardware. BLOCS is the only method to scale up to WikiKG90Mv2, knowledge graph with 601M triples. Leiden and METIS both caused memory errors WikiKG90Mv2, while HDRF was too long for graphs larger than YAGO4 (our time limit was set to 333 minutes).
BLOCS
METIS
Leaden
Louvain
LE
Infomap
LPA
HDRF
R1: connectedisikk
R2: boundeed sine
1w7
sotl cossedas
max/iin size ratio
10
comppnents
Largest sizee
2000
107
2-
101
10F
100
10F
107
10'
10a
Number of triples
Number triples
Number of triples
Figure 12: Quality of partitioning methods. Maximum number connected components one partition, ratio between the largest and smallest partition sizes, and size (number of entities) of the largest partition produced for knowledge graphs various sizes. The "GPU capacity" dashed line represents the typical number of entities that can be loaded onto the GPU before causing memory error. Methods producing partitions larger than this cannot be combined with SEPAL, since the partition's 's embeddings must fit in GPU memory. BLOCS and Leiden the only methods to consistently return connected partitions (requirement R1). BLOCS, METIS, and HDRF are the only methods to control the partition size (requirement R2).
guarantees connected communitics. LDG [Stanton and Kliot 2012 and FENNEL Tsourakakiss et al. 2014] are streaming algorithms for very large graphs. Some algorithms have also been specifically tailored for power-law graphs: DBH Xie et al. 2014] leverages the skewed degree distributions to reduce the communication costs, HDRF [Petroni al. 2015 is streaming partitioning method that replicates high-degree nodes first, and Ginger [Chen et al. 2019b) is a hybrid-cur algorithm that uses heuristics for more efficient partitioning skewed graphs.
E.2 Detailed algorithm and pseudocode
Algorithm I describes BLOCS pseudocode, and Figure 13 illlsstras its base mechanisms. Below, provide more details subparts of the algorithm.
The function SplitNeighbors is designed to manage high-degree nodes by distributing their neighboring entities into smaller subgraphs. For each node whose degree exceeds certain threshold, groups neighbors multiple subgraphs smaller than this threshold. These new subgraphs also include the original high-degree node to maintain connectedness. By assigning the neighbors
41

---

select high-degree nodes
diffuse
merge
dilate
Figure 13: Base mechanisms of the BLOCS algorithm. BLOCS grows subgraphs from high-degree unassigned nodes using three main operations: diffusse adds all neighbors the current subgraph; merge combines two overlapping subgraphs; and dilate adds only unassigned neighbors.
of the very high-degree nodes first, BLOCS ensures that subgraphs grow more progressively in the subsequent diffusion step.
The function SrtrgeSmamSSuubraappaa
takes a list of subgraphs and a minimum size threshold as input. It identifies subgraphs that are smaller than this given minimum size and merges them into larger subgraphs if they share nodes and if the size of their union remains below the maximum size m.
The function cesstematiMMerree is very similar to MergeSmall SangeSmma1SSubrreee Subgraphs, but it does not check that the resulting subgraphs smaller than m. Its objective is to eliminate all the subgraphs whose size is smaller than a given threshold (set to 0.4 m in Algorithm D. The subgraphs produced that are larger than
then handled by the function SplitLargeSubgraph...
The function SplitLargeSubgraphs processes the list of subgraphs to break down overly large subgraphs while preserving connectivity. The function iterates over the subgraphs having more than m nodes, subtracts the core, and computes the connected components. Then, it creates new subgraphs by grouping these connected components until the size limit is reached. As a result, outer subgraphs can be disconnected at this stage, but merging them with the core ensures their connectedness during embedding propagation.
E.3
Benchmarking BLOCS against partitioning methods
First, we compare BLOCS to other graph partitioning, clustering, and community detection methods. 12 report empirical evaluation eight knowledge graphs. BLOCS, METIS, and Leiden are the only approaches that scale to the largest knowledge graphs. Others fail due to excessive runtimes -our limit was set 2- 10 seconds. Compared METIS, BLOCS is more efficient in terms of RAM usage while having similar computation times FFiure ITI. Experimental results also show that classic partitioning methods fail meet the connectedness and size requirements. Indeed, knowledge graphs are prone to yield disconnected partitions due to their scale-free nature: they contain very high-degree nodes. Such node is hard allocate single subgraph, and subgraphs without it often explode into multiple connected components. Our choice of overlapping subgraphs avoids this problem.
Figure 11
Classic methods do not meet the requirements of SEPAL Here, we provide qualitative obser- vations on the partitions produced by the different methods. We explain why they fail to meet our specific requirements.
METIS based on a multilevel recursive bisection approach, which coarsens the graph, partitions it, and then refines the partitions. It produces partitions with the same sizes; however, due to the graph structure, they often explode into multiple connected components, which is detrimental to the embedding propagation (see Appendix E.3
Louvain based on modularity optimization. It outputs highly imbalanced communities, often with one community containing almost all the nodes and a few very small communities. This imbalance is incompatible with our approach, which requires strict control over size of the subgraphs so that their embedding fits in GPU memory. Moreover, some of the communities are disconnected. On the two largest graphs, YAGO4 taxonomy and Freebase, Louvain exceeds the time limit (2 10a seconds).
42

---

Leiden modifies Louvain to guarantee connected communities and more stable outputs. It has very good scaling capabilitiess (Figure ITp but shares with Louvain the issue of producing highly-imbalanced communities.
LE is recursive algorithm that splits nodes based the sign of their corresponding coefficient in the leading eigenvector the modularity matrix. these signs are all the same, the algorithm does not split the network further. Experimentally, LE returns only one partition (containing all the nodes) for YAGO3, YAGO4, YAGO4 + taxonomy, and Freebase. For YAGO4.5 taxonomy, hits pre-set time limit 10 seconds). Therefore, its performance for Mini YAGO3 and YAGO4.5, for which it outputs and 4 partitions, respectively. It is important note that the more communities returns, the longer it takes to run because the algorithm proceeds recursively.
only report
Infomap uses random walks and information theory to group nodes into communities. Experimen- tally, it produces lot small communities with no connectedness guarantee. Additionally, it is too slow to be used on large graphs.
LPA propagates labels across the network iteratively, allowing densely connected nodes to form communities. Similarly to Louvain and Leiden, the downside is that it does not control the size of the detected communities. It is also too slow run the largest graphs.
SC uses the smallest eigenvectors of the graph Laplacian dimensional space and then applies k-means to group nodes together. However, the expensive eigenvector computation is bottleneck that does not allow this approach to used on huge graphs.
transform the graph into a low-
HDRF is streaming algorithm that produces balanced edge partitions (vertex cut) and minimizes the replication factor. However, it produces disconnected partitions, and it too slow to run the largest graphs.
Therefore, none of the above methods readily produces subgraphs suitable for SEPAL. Indeed Figure shows that BLOCS is the only method that returns subgraphs that are both connected and bounded size, while being competitive in terms of scalability (Figure IT).
BLOCS cannot be replaced with METIS To demonstrate the benefits of BLOCS over existing methods, we try to replace BLOCS with METIS our framework. The results are presented in Figure 14]
Two important points differentiate these methods:
Contrary to BLOCS, METIS outputs disconnected partitions (see Figure 12p. Given the structure of SEPAL, this results in zero- cero-embeddings for entities not belonging to the core connected component at propagation time. Interestingly, the presence of zero-embeddings affects downstream scores very little, likely because most downstream entities belong to the core connected component and are thus not impacted by this.
Aggregated performance
4-
SEPAL...
with BLOCS with METIS
3-
2
Knowledge graph
Mini YAGO3
YAGO3
YAG04.5
10c
10t
102
CPU usage (GiB)
Figure 14: Ablation study: replacing BLOCS with METIS. Normalized R2 scores (same
Figure 6) aggregated across evaluation datasets (movie revenues, US accidents, US elections. housing prices) for SEPAL with BLOCS and METIS plotted against CPU RAM usage. BLOCS necessi- tates significantly less memory than METIS, We were not able to run SEPAL + METIS on knowledge graphs larger than YAGO4.5, hitting CPU RAM limits during the partitioning stage.
43

---

YAG03
YAG04
YAGO6,5
YACO6
YAGD4
Freebase WKIKGSSOAZ
10*
Aazz
Execuatinn time (S)
4M
10a
7.5
Max size
10a
2.5
0.4
0.6
0.8
0.4 0.6 0.8
0.4
0.6
0.8
Figure 15: Sensitivity analysis to parameter h. Effect of varying h BLOCS' execution time, replication factor (average number of outer subgraphs containing a given entity), and maximum subgraph size. A lower bound of the domain of h values to explore for a dataset is given by the proportion of nodes that are neighbors to super-spreaders. Indeed, as BLOCS' first step is to assign super-spreaders neighbors, if is smaller than this value, BLOCS completely skips the diffusion phase. For YAGO4.5 and YAGO4, this results in sharp variations of the replication factor or the maximum subgraph size, respectively. The maximum size parameter and 4M for others.
set to 400k for YAGO3,
2. METIS does not scale as well as BLOOC in terms of CPU memory. On our hardware, SEPAL + METIS could not scale to graphs larger than YAG04.5 (32M entities), and therefore, BLOCS is indispensable for very large knowledge graphs.
E.4 Effect of BLOCS' stopping diffuuion threshold
In the BLOCS algorithm, the hyperparameter l controls the moment of the switch from diffusion to dilation. For h E (0, 1). BLOCS stops diffusion once the proportion of entities the graph assigned to subgraph is greater than or equal to h.
Figure shoss that increasing à tends increase the execution time and the overlap between sub- graphs. Higher overlaps can be preferable to enable the information to travel between outer subgraphs during embedding propagation. However, a high overlap also incurs additional communication costs because the embeddings are moved several times from CPU to GPU, increasing SEPAL's overall execution time.
E.5
How distant from the the outer entities?
Figure 16]shows that outer entities are average very close the core subgraph. This is due the fact that the core contains the most central entities, and to the scale-free nature of knowledge graphs.
YAS03
M60445
VAS045
Lasconerty
TAGG4
Laxortany
fresbuse
1AG03
VAcooss s
Lexonassy
YAGG4
sastmomy
fristuse
walkcaaha
% core-conitected entities
of core-conneeting edges
100
1.00
60-
40
60
Figure 16: Outer subgraphs are well connected to the core. The left plot gives the percentage of outer entities that are directly connected the core subgraph. The right plot gives the percentage of edges that come from the core subgraph among all the edges coming to given outer subgraph, showing the amount of information transferred from the core to outer subgraphs relative outer-outer communication.
44

---

YAG04.5
Core subgraph extraction
Core
embedding Embedding
Outer subgraphs generation (BLOCS)
+T
propagation
YAG04
YAGO4+T
Freebase
WikikG90Mv2
Time (hours)
Figure 17: SEPAL's execution time breakdown. Execution time of SEPAL's different components, for the west-performing configurations of SEPAL on downstream tasks (see Table for hyperparame- ters values).
F Further analysis of SEPAL
F. Execution time breakdown
Here, we present the contribution of each part of the pipeline to the total execution time. Specifically, we break down our method into four parts:
1. core subgraph extraction;
2. outer subgraphs generation (BLOOCS):
3. core embedding;
4. embedding propagation.
Figure 17 shows the execution time the different components of SEPAL. It includes six large-scale knowledge graphs, for which the execution times have the same order of magnitude. The results reveal that most of execution time is due to the core embedding and embedding propagation phases, while the core extraction time is negligible.
Four key factors influence SEPAL's execution time during the four main steps of the pipeline:
1. The core selection strategy: the degree-hased selection is faster than the hybrid selection. For the hybrid selection, the factor that influences the speed the most is the number of distinct relations.
2. The diameter the knowledge graph: graphs with large diameters call for more dilation steps during BLOCS' subgraph generation, and dilation is more costly than diffusion because it requires checking node assignments. This explains why adding the taxonomies to YAGO4 and YAGO4.5 drastically reduces the time required to rum BLOCS. shown on miFuure 17
3. The core subgraph size: the more triples in the core subgraph, the longer the core embed- ding. This explains the wide disparities between the core embedding times on Figure 17 despite all the core subgraphs having roughly the same number entities: YAGO4 core subgraph is more dense (33M triples), compared to YAGO4.5 (7M triples), for instance. The core embedding time also depends on hyperparameters such as the number of training epochs.
4. The total number embedding matrix. The communication cost of moving embedding matrices from CPU to GPU, and vice versa, accounts for most of the propagation time, and increases with N. also increases with the amount of overlap between the outer subgraphs produced by BLOCS.
entities in the graph: this number determines the size of
45

---

explaining the differences in propagation time between YAGO4.5 and YAGO4.5 + taxonomy for instance.
The number of propagation steps 7 has little impact on the embedding propagation time. The reason for this is that much of this time stems from the communication cost loading the embeddings onto the GPU, and not from performing the propagation itself.
F.2 SEPAL's hyperparameters
F.2.1 List of SEPAL's hyperparameters
Here, we list the hyperparameters for SEPAL, and discuss how they can be set. Table 9 gives the values of those that depend on the dataset.
Proportion of core nodes Th the idea is to select it large enough to ensure good core embeddings, but not too large so that core embeddings fit in the GPU memory. Figure 18] shows the experimental effect varying this parameter;
Proportion of core edges T): increasing it at the expense of T/2. (to keep the core size within GPU memory limits) improves the relational coverage, but reduces the density of the core. Sparser core subgraphs tend to deteriorate the quality of SEPAL's embeddings for feature enrichment (Figure 22). However good relational coverage is essential for better link pre-pcreditiio performance;
Stopping diffusion threshold h: depends on the graph structure, and tuning is done empirically by monitoring the proportion of unassigned entities during the BLOCS algorithm: h is chosen equal the proportion of assigned entities at which BLOCS starts to stagnate practice,FFigure
during its diffusion regime. In practice, FFigure 15 and Figure 19 shows that as long as h
is chosen greater than the proportion of entities that are neighbors of super-spreaders, the algorithm is not too sensitive to this parameter (otherwise, skips the diffusion phase, which can be detrimental);
Number of propagation steps T: is chosen high enough to ensure reaching the remote entities (otherwise, they will have zeros as embeddings). Taking T equal to the graph's diameter guarantees that this condition is fulfilled. However, for graphs with long chains, this may slow down SEPAL too much. In practice, setting 7 at 2-3 times the Mean Shortest Path Length (MSPL) usually embeds most entities effectively:
Propagation learning rate a: it controls the proportion of self-information relatively to neighbor-informatin informationnnnn during propagation updates. For the DistMult model, this parameter has no effect during the first propagation step. when an entity is reached for the first time because outer embeddings are initialized with zeros and the neighbors' message is normalized. In practice, the embedding of an outer entity can reach in one step a position very close to its fix point, and thus this parameter does not have much effect (Figure 20).
For our experiments we typically use a = 1;
Subgraph maximum size m: the idea to use the largest value for which it possible to fit the subgraph's 's embeddings in the GPU memory. We use 4 10 for Mini YAGO3, 4 10 for YAGO3, 10 for WikiKG90Mv2, and 4 106 for the other knowledge graphs;
Embedding dimension d: we use d 100 (except for complex embedings, where d 50
to keep the same number of parameters);
Number of epochs for core training nepochi see Table
Batch size for core training b: see Table 9
Optimizer for core training: we use the Adam optimizer with learning rate Ir 1 10 10-3,
Number p of negative samples per positive for core training: use p 100 Table 9..
F.2.2
Experimental study of hyperparameter effect
Figure 18, Figure 19 Figure 20 and Figure 21 investigate the sensitivity of SEPAL to different
hyperparameters. The hyperparameter that seems impact the most SEPAL's performance the core proportion 7h. Indeed, Figure 18 shows that increasing T) tends to improve embedding quality
46

---

Dataset
Parameter
Grid (best in bold)
Ma/Me
0.05/-,00 0.2/
0.025/0.005, 0.3/0.05
0.6, 0.65, 0.7, 0.75, 0.8
2, 5, 10, 15, 25
Mini YAGO3
nepoch
12, 25, 50, 60, 75
b
512
p
1, 100, 1000
Ma/Me
0.05/ 0.1/-, 0.025/0.015, 0.3/0.05
0.55, 0.6, 0.65, 0.7, 0.75, 0.77
2,5, 10, 15, 25
YAGO3
Tepochh
16, 18, 25, 45, 50, 75
b
2048, 4096, 8192
P
1. 100, 1000
Ma/Me
0.03/ 0.015/0.01, 0.05/0.03
0.4, 0.5, 0.6
2, 5, 10, 15, 25, 50
YAG04.5
Teepach
16, 24, 75 8192, 16384
b
Table 9: Hyperparameter search space for SEPAL, and best values (in bold) for each knowledge graph on downstream tasks. The best values are those that gave the best average perfor- mance on the 4 validation ta- bles and that were used to the results in Figure 2 and Figure
p
1. 100
Ma/Me
0.03/-, 0.015/0.005, 0.04/0.015
0.8
2, 10, 15, 20, 25
YAG04.5+T
Teepoch
32, 75
b
8192
P
100
Ma/Me
0.03/ 0.015/0.005, 0.012/0.025
0.55
2,5, 10, 15, 20, 255
YAGO4
Thepach
4, 28, 75
b
8192, 65536
P
1. 100
Ma/
0.02/
0.01/0.005
0.45, 0.8
10, 20
YAGO4+T
Tepocch
32, 75
b
8192, 65536
P
1. 100
Ta/m
0.02/-
0.01/0.005
0.55
15
Freebase
Thpoch
24
b
8192
P
100
Ma/Me
0.02/-
0.92
10
WikiKG90Mv2
Zhppoch
12
b
8192
p
100
for downstream tasks. However, the effect seems to be plateauing relatively fast for YAGO3 (not
much improvement between 7/. = 5% and 1),, 10%). For other datasets (YAGO4.5, YAGO4), it is not possible to explore larger values of 7) because the core subgraph would not fit in the GPU memory. Moreover, decreasing 7h makes SEPAL faster, the core embedding phase accounts for substantial share of the total execution time (igure 17). There is, therefore, a trade-off between time and performance.
47

---

Aggregated performance
3
Knowledge graph
YAGO3
2
YAGO4
YAG04.5
1
0
0.02
0.06 Core proportion n
0.10
Figure 18: strategy.
Effect of core proportion f) on SEPAL's performance, with the degree-based core selection
Aggregated performance
4
3
Knowledge graph
Mini YAGO3 YAGO3
2
1
0
0.55
0.60
0.65
0.70
0.75
0.80
Figure 19; Effect of stopping diffusion threshold h SEPAL's performance.
Core selection strategy Degree-based selection: The simple degree- based core selection strategy convenient for two reasons:
1. Degree is inexpensive to compute, ensuring the core extraction phase to be fast (see Fig ure 17);
2. It yields very dense core subgraphs. Indeed, while they contain 7n, % of the entities of the full graph, they gather around 47,, % of all the triples (Table 10). This allows the training on the core process substantial portion of the knowledge-gree garlggee-raaphh triples, resulting in richer representations.
Hybrid selection: However, problem with degree-based selection is that some relation types may not be included in the core subgraph. To deal with this issue, SEPAL also proposes more complex hybrid method for selecting the core subgraph, that incorporates the relations. It proceeds in four main steps:
Aggregated performance
Knowledge graph
Mini YAGO3
3
YAGO3
YAGO4
2
YAGO4 taxonomy
1
YAG04.5
YAG04.5 taxonomy
10
10
Propagation learning rate
Figure 20: Effect of propagation learning rate a on SEPAL's downstream performance.
48

---

Aggregated performance
Knowledge graph
Mini YAGO3
2
YAGO3
YAGO4
1
YAG04.5
0
10
20
30
40
50
Number T of propagation steps
Figure 21: Effect of number 7 of propagation steps SEPAL's downstream performance.
Table 10: Effect of core selection strategies. Number entities and triples inside the core subgraph and proportion of the full graph they represent (in parentheses). 7/n and ne the hyperparameters for nodes and edges, respectively. Column #Rel gives the number relation types present in the core compared the total number of relation types in the knowledge graph. We highlight in red the cases where some relations are missing. Column Time gives the measured computation time for core selection.
Strategy
77n
#Rel
#Entities
#Triples
Time
Degree Hybrid
5%
37/37
126k (4.9%)
1.0M (18.5%)
17s 20s
YAGO3
2.5%
1.5%
37/37
121k (4.7%)
733k (13.1%)
Degree Hybrid
3%
62/62
932k (2.9%)
7.2M (9.6%)
2min
YAG04.5
1.5%
1%
62/62
1.IM (3.3%)
5.7M (7.5%)
6min
Degree Hybrid
3%
61/76
1.1M (3.0%)
33M (13.4%%
8min
YAGO4
1.5%
0.5%
76/76
1.4M (3.8%)
28M (11.1%)
11min
Degree Hybrid
3%
64/64
1.5M (3.0%)
13M (9.9%)
4min
+
1.5%
0.5%
64/64
1.2M (2.5%)
8.3M (6.5%)
5min
Degree Hybrid
2%
64/78
1.3M (2.0%)
41M (12.8%)
9min
YAGO4+T
1 %
0.5%
78/78
1.5M (2.3%)
32M (10.1%)
12min
Degree Hybrid
2%
5,363/14,665
1.7M (2.0%)
15M (4.4%)
9min
Freebase
1
0.5%
14,665/14,665
1.9M (2.3%)
14M (4.1%)
4h
Degree Hybrid
2%
886/1,387
1.8M (2.0%)
62M (10.4%)
17min 48min
WikiKG90Mv2
0.4%
0.7%
1,387/1,387
2.0M (2.2%)
37M (6.2%)
Sample the nodes with the top 7ho degrees. 2. Relation selection: Sample the edges with the top 7) degrees (sum of degrees of head and tail) for each relation type, and keep the corresponding entities.
Degree selection:
3. Merge: Take the union of these two sets of entities.
4. Reconnect:
If the induced subgraph several connected components, add entities to make it connected. This is done using a breadth- -fistt search (BFS) with early stopping from the node with the highest degree of each given connected component (except the largest) the largest connected component. For each connected component (except the largest), path linking it to the largest connected component is added to the core subgraph.
This way, each relation type is guaranteed to belong to the core subgraph, by design. Table 10 confirms this experimentally, even for Freebase and its 14,665 relation types. This method features two hyperparameters 7), and Te. the proportions for node and edge selections, controlling the size of its output subgraph. The values we used are provided in Table 10 for each dataset.
Regarding performance, Figure 22 shows that the hybrid strategy slightly underperforms the degree- based approach on four real-world downstream tasks. Indeed, the hybrid approach enhances relational coverage but, as counterpart, yields a sparser core subgraph (see #Triples in Table 10), which is detrimental to downstream performance. However, one can adjust the values 7), and Te to control the trade-off between downstream performance and relation coverage, depending the case.
49

---

h YAGO3 (2.6M entities, 5.6M triples)
Hybrid
min
Degree
23 min
YAG04.5 (32M entities, 75M triples)
Degree
h
Hybrid
YAGO4.5 taxonomy (50M entities, 128M triples)
Degree
h
Evaluation dataset
Hybrid
h Movie revenues
YAGO4 (38M entities, 250M triples)
accidents
elections
Degree
12
Housing prices
Hybrid
7
YAGO4 taxonomy (67M entities, 320M triples)
Degree
Hybrid
h
Freebase (85M entities, 338M triples)
Degree
Hybrid
10
Cumulative normalized cross-validation score (R2)
Performance of DisALtDistMult for the two different core selection strategies. We use the hyperparameters of Table 10 The simpler degree-based selection strategy runs faster and performs better on downstream tasks.
Figure 22:
For instance, for the link prediction task, a better relational coverage (greater 7))) improves the performance (Appendix C.6).
Exploring other centrality measures Here, we compare degree with PageRank as centrality measure for the core selection (keeping all other hyperparameters unchanged). Like the degree, the PageRank can be computed very efficiently on huge graphs using sparse matrix multiplications.
Table 11 reports results on the real-world downstream tasks. Regarding performance, it seems that the difference between degree and PageRank depends on the graph's 's structure. Specifically, we observe that for YAGO4, YAGO4+T, Freebase, and WikiKG90Mv2, PageRank improves the performance. This echoes the results of Figure 16 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. Regarding computational cost, we see that SEPAI. with PageRank usually runs slightly faster than with degree. This is because PageRank yields slightly sparser cores, leading to faster core training.
Table 11: Effect of core selection strategy: PageRank vs Degree. We compare the performance of DisMLt real-world downstream tasks when using either degree PageRank centrality measure for core selection. We report the average normalized R2 score across the four downstream tasks, along with the total execution time (in parentheses).
Dataset
Core defined by Degree
Core defined by PageRank
YAGO3
0.783 (1 Im 20s)
0.742 (9m 23s)
YAGO4
0.817 (6h 20m)
0.861 (4h 53m)
YAGO4+T
0.815 (10h 9m)
0.881 16m)
YAGO4.5
0,949 (4h 11m)
0,925 (4h 3m)
YAG04.5+T
0,923 (2h 47m)
0.912 (2h 40m)
Freebase
0.917 (5h 58m)
0.919 (5h 58m)
WikikG90Mv2
0.898 (20h 31m)
0.902 (23h 59m)
50

---

Aggregated performance
with BLOCS
4
without BLOCS
3
without BLOCS (extrapolated)
2
Knowledge graph
CP0 capac.u
Mini YAGO3
YAGO3
YAGO4
10a
10a
10
10a
YAG04.5
GPU RAM usage (MiB)
Figure 23: Ablation study: BLOCS scales SEPAL memory-wise. Normalized R2 scores aggregated across evaluation datasets (movie revenues, US accidents, US elections, housing prices) for SEPAL. with and without BLOCS are plotted against GPU RAM usage. BLOCS preserves performance for given knowledge graph while drastically reducing memory pressure GPU RAM. Without BLOCS, the GPU runs out of memory for YAGO4 and YAGO4.5.
E33 Ablation study: SEPAL without BLOCS
Here, we study the effect of removing BLOCS from our proposed method. On smaller knowledge graphs, SEPAL can be used with simple core subgraph extraction and embedding followed by the embedding propagation. This ablation reveals the impact of BLOCS on the model's performance. Figure 23 shows that adding BLOCS the pipeline graphs that would not need it (because they small enough for all the embeddings to fit in GPU memory) does not alter performance. Additionally, move the blue points horizontally on Figure 23 and choose a value within the GPU memory constraints. There trade-off between decreasing GPU RAM usage (i.e., moving the blue points to the left) and increasing execution time, as fewer entities are processed at the same time.
BLOCS brings scalability. By tuning the maximum subgraph size m hyperparameter,
F.4 Speedup over base embedding model
Figure 24 demonstratess that SEPAL can accelerate its base embedding model by more than factor of 20, while also boosting its performance on downstream tasks.
a)
Lower training time
ligher performance
1.0
Mini YAGO3
DistMult
Mean R2 score (normalized
Training time (s)
YAGO3
27.9x faster
0.8
SEPAL
x Waster
30.3x
0.6
faster
1min
DistMult
0.4
Epochs
6.6x faster
SEPAL
10s
0.2
10a
10a
102
10s
1min
Number of epochs
Training time (s)
Figure 24: Comparison between SEPAL and its base embedding model. a) Computation time per training iteration. For a given training configuration, SEPAL is up to 30 times faster than its base embedding algorithm DistMult. b) Learning curves. SEPAL achieves strong downstream performance much quicker than DistMult. For both plots, we only vary the number of epochs and fix the following parameters for DistMult's 's training and SEPAL's core training: p 1, Ir 1 10 b 512 for Mini YAGO3 and 2048 for YAGO3. For SEPAL, we use the degree-based core selection with 7h 5%.
51

---

Table 12: Comparison between SEPAL and DistMult-ERAvg on Mini YAGO3. We report the normalized mean cross-validation score (R2) across the four real-world downstream tasks, along with the total training time. SEPAL outperforms Dis while being significantly faster.
Method
Housing prices
Movic revenues
US accidents
US elections
Time
FirMuult-EAyy
0.149
0.124
0.444
0.916
2h 41m
SEPAL
0.276
0.159
0.548
0.929
5m
Moreover, the speedup increases with the number of training epochs, SEPAL's constant-cost steps (core extraction, BLOCS, and propagation) are amortized when core training gets longer. Indeed, each additional epoch is cheaper with SEPAL than with DistMult, since training is done only on the smaller core rather than the full graph.
G
Discussion
G.1
Comparison to prior work
G.1.1
Comparison to DistMult-ERAvg
Albooyeh et al.
2020 propose an aggregation that is similar to SEPAL's aggregation during the propagation phase, however the two methods optimize the embeddings in two very distinct ways:
Albooyeh et al. 2020) introduce propagation within the standard link prediction pipeline: during training. for each triple (v, u), they occasionally (with probability p) replace one entity's 's embedding with an aggregated version (c.g., 0,,) before computing the plausibility score. However, training still relies negative sampling and classic link prediction loss, and thus optimizes for local triple-level contrasts like traditional KGE methods.
SEPAL, in contrast, explicitly separates the optimization objective: embeddings for a small core are trained with classic KGE objective, and then relation-awarg propagation used across the rest of the graph, without negative sampling. This distinction is crucial: SEPAL removes the need for negative sampling on typically 95 to 99% of the graph, enabling both improved scalability and alignment properties beneficial for downstream tasks.
Moreover, DistMult-ER is not designed for very large graphs. On the datasets considered in this paper, it fails with out-of out-of-memory errors on all the graphs except Mini YAGO3 (129k entities, 1.1M triples).
Table 12 reports performance and runtime on Mini YAGO3, showing that SEPAL 32 times faster than DistMult- while achieving consistently better scores. This is expected 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 out-of-sample embedding computation, which SEPAL also supports (see Appendix G.3), but with greater scalability.
G.1.2 Comparison to NodePiece
SEPAL shares with NodePiece the fact that embeds a subset of entities. Parallels can be drawn between: the anchors of NodePiece and the core entities of SEPAL; b) the encoder function of NodePiece and the embedding propagation of SEPAL. Yet, our approach differs from NodePiece in several ways.
Neighborhood context handling Both methods handle completely differently the neighborhood of entities. NodePiece tokenizes each node into sequence of k anchors and m relation types, where k and m are fixed hyperparameters shared by all nodes. If the node degree is greater than m, NodePiece downsamples randomly the relation tokens, and if is lower than m, [PAD] tokens appended; both seem sub-optimal. In contrast, SEPAL accommodates any node degree and uses all the neighborhood information, thanks to the message-passing approach that handles the neighborhood context naturally.
Additionally, NodePiece's 's tokenization relies on an expensive BFS anchor search, unsuitable for huge graphs. On our hardware, could not run the vanilla NodePiece (PyKEEN implementation)
52

---

Mini YAGO3 (129k entities, 1.1M triples)
Evaluation dataset
DistMult + SEPAL
min
Movie revenues
accidents
elections
DistMult NodePlece
min
Housing prices
4
Cumulative normalized mean cross-validation scare (R2)
Figure 25: Comparing SEPAL with NodePiece Mini YAGO3.
on graphs bigger than Mini YAGO3 (129k entities). For YAGO3 and YAGO4.5, had to run an ablated version where nodes are tokenized only from their relational context (i.e., k = 0, studied in the NodePiece paper with good results), to skip the anchor search step.
Training procedure At train time, NodePiece goes through the full set of triples at each epoch to optimize both the anchors' embeddings and the encoder function parameters, necessitating many gradient computes and resulting in long training times for large graphs. On the contrary. SEPAL performs mini-batch gradient descent only on the triples of the core subgraph, which provides significant time savings. To illustrate this, Figure 25 compares the performance of SEPAL and vanilla NodePiece on Mini YAGO3, showing that SEPAL outperforms NodePiece on downstream tasks while being nearly two times quicker.
Embedding propagation non-anchor/non-core entities To propagate to non-anchor entities, NodePiece uses an encoder function (MLP or Transformer) that has no prior knowledge of the relational structure of the embedding space, and has to learn through gradient descent. On the contrary, SEPAL leverages the model-specific relational structure compute the outer embeddings with no further training needed.
G.2
Communication costs of SEPAL
SEPAL optimizes data movement In modern computing architectures, memory transfer costs are high, amounting to much computation, and the key to achieve high operation efficiency is to reduce data movement [Mutlu et al. 2022).
For distributed methods such as PBG or DGL-KE, parallelization incurs additional communication costs due two factors: 1) Learned parameters shared across workers (relation embeddings) require frequent synchronization 2) Entities occurring in several triples belonging to different buckets have their embeddings moved several times from CPU to GPU, and this for every epoch. This latter effect can be mitigated by better partitioning, but remains significant.
SEPAL avoids much of the communication costs by keeping the core embeddings on GPU memory throughout the process. These core em- beddings are the ones that would move the most in distributed settings, because they correspond to high-degree entities involved in many triples. Moreover, SEPAL's propagation loads each outer subgraph only on the GPU, contrary to other methods that perform several epochs. This significantly reduces data movement for outer embeddings: em- pirically, they only cross the CPU/GPU boundary twice on average (see
Empirical av- erage number of memory transfers between CPU and GPU for outer embeddings across datasets.
Table 13:
Dataset
Couter
Mini YAGO3
1.20
YAGO3
3.07
Table 13)
YAGO4.5
7.47
YAG04.5+T
1.94
Estimating I/O Communication costs occur in SEPAL during the propagation phase, where the embeddings of each of the subgraphs generated by BLOCS have to be loaded on the GPU, subgraph after subgraph. We analyze the number x back-and-forth of given embedding between CPU and GPU memory. The optimal value is I 1, meaning the embeddings are transferred only once. detailed breakdown follows:
YAGO4
2.29
YAGO4+T
1.27
Freehase
2.09
WikiKG90Mv2
1.84
Average
2.65
53

---

For core embeddings: core embeddings remain at all times on the GPU memory. They are only moved to the CPU once the end, be saved on disk with the rest of the embeddings.
Therefore, the data movement of core embeddings is optimal: Fcore = 1.
For outer embeddings: SEPAL loads each outer subgraph only once to the GPU. Conse- quently, the average number Zouter of memory transfers for outer embeddings corresponds to the average number of subgraphs in which given outer entity appears. Table 13 reports empirical values of Touter across datasets, ranging from 1.20 to 7.47, with an overall average of 2.65. This redundancy arises from subgraph overlap, which is directly influenced by the h hyperparameter in BLOCC: smaller values of h yield fewer diffusion steps (and more dilation steps), leading to reduced subgraph overlap and, hence, fewer memory transfers per embedding.
The optimal value of x can only be achieved in the case where the entire graph fits GPU memory. Every approach that scales beyond GPU RAM limits has its communication overheads, i.e., x 1.
For comparison, distributed training schemes that load buckets of triples to GPU iteratively exhibit significantly higher communication costs. In such settings, the number of memory transfers for the embedding of an entity u is given by I = Tbuuckets (u) X Repochs where Abuckets (u) is the number of buckets that contain a triple featuring entity u, and Repochs is the number of epochs. That is at least one or two orders of magnitude greater than what SEPAL achieves in terms of data movement. embedding methods are usually trained for a few tens if not a few hundreds of epochs, so is much bigger than 10, not even taking into account Thuckets (u) that can be large, depending on the graph structure and on the quality of the graph partitioning.
Indeed, knowledge-grat
G.3 Outlook on continual learning
The modular nature of SEPAL makes it well-suited for continual learning scenar- ios, where new entities are added to the knowledge graph over time. Indeed, new embeddings be computed without training from scratch, via a few additional propagation steps, long the relations
Table 14: Statistics of the two versions YAGO3 used to illustrate SEPAL's suitability for continual learning.
Version
#Entities
#Relations
#Triples
7A14 YAGO3-2022
2,570,716
37
5,585, 004
4.546,966
37
14,691,781
remain unchanged. To demonstrate this, we use two versions of the YAGO3 knowledge graph: the original 2014 release, and the 2022 revived version. Table givvs the statistics of these two datasets.
We adapt SEPAL to this continual learning setting by: (1) initializing the embeddings of YAG03-2022 using embeddings precomputed on YAGO3-2014, (2) propagating embeddings for 5 additional steps to update existing nodes and embed new entities. We denote this method SEPAL-CL the results.
Table 15 shows that:
For downstream applications, YAGO3-2022 brings value compared to YAG03-2014. Indeed, for all the methods considered, the embeddings learned the 2022 dataset score higher than the strongest method on YAGO3-2014, SEPAL.
SEPAL trained from scratch is 10 x faster than DistMult on YAGO3-2022.
SEPAL-CL is 57 x faster than SEPAL trained from scratch on YAGO3-2022, and 587 x faster than DistMult.
Table 15: Continual learning experiment on YAGO3, Average normalized R2 scores across the four real-world downstream regression tasks (movie revenues, US accidents. US elections, housing prices) and total runtime for different methods. SEPAL-CI. denotes SEPAL the continual learning setting, where new entities are embedded via propagation.
YAGO3 version
Method
Average performance
Runtime
2014
SEPAL
0.836
Oh 11m 20s
2022
DistMult
0.884
11h 05m 36s
2022
SEPAI
0.988
1h 05m 07s
2022
SEPAL-CI.
0.962
Oh 01m 08s
54

---

SEPAL-CL clearly outperforms DistMult, and almost matches the performance of SEPAL trained from scratch, even in this very challenging scenario 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 real-life application, we could imagine emheddings recomputed monthly at very low cost.
G.4 Broader impacts
SEPAL may reflect the biases present in the training data. For instance, Wikipedia, from which YAGO is derived, reder-represents women [Reagle and Rhue 2011). We did not evaluate how much our method captures such biases. We note that the abstract nature of embeddings may make the biases less apparent to the user; however, this problem is related to embeddings and not specific to our method. It may be addressed by debiasing techniques [Bolukbasi et al. 2016 Fisher al. 2020 for which SEPAL could be adapted.
55


Reviews:
[{"review_id": "4c8Vf13ffo", "reviewer": "Reviewer_aZkD", "summary": "The paper proposes two things – an embedding propagation algorithm called SEPAL that scales to large KGs and BLOCS, an algorithm to break large graphs into balanced overlapping subgraphs. The algorithm works in two phases – identifying a core subgraph and creating core and relation embeddings using existing KGE methods and propagating the embeddings to the other subgraphs using message passing. The authors show that this process can be executed in a limited GPU memory setting for really large graphs. The evaluation on downstream applications shows cases the merit of the proposed solution.", "questions": "Q1: If the knowledge graph is updated with new entities and relations, does the entire process need to rerun (starting from code graph selection)?\nQ2: Is there a dependency on the graph having higher connectivity or connectedness for the SEPAL algorithm?", "limitations": "Authors have sufficiently addressed the limitations of the work", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "S1: The authors have clearly defined the problem and where the proposed solution comes in. \nS2: The proposed algorithm SEPAL reuses several methods from the existing graph / KG literature towards scaling of the KGE generation, and the authors also provide theoretical analysis for SEPAL.\nS3: The proposed algorithms are evaluated on a broad set of KGs and of varying lengths showcasing the strength of the solution in terms of usage of only commodity hardware to compute the embeddings.\nW1: The biggest weakness is that the paper is heavily reliant on the Appendix and while it is appreciated that the authors have provided substantial and important information in the appendix, the main paper should be representative of the core work (both algorithms and the evaluation). In the current format, it takes a significant amount of back and forth to understand the work.\nW2: (Minor) The placement of the proposed algorithm BLOCS in appendix is slightly confusing as it is claimed to be a contribution but only mentioned in the main paper.", "was_revised": true, "final_justification": "The authors have mostly addressed the two questions that were raised in the review.", "rebuttal": "We sincerely thank the reviewer for the insightful feedback.\n\nWe 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.\n\nBelow, we answer the reviewer’s questions and concerns in detail.\n\n### **Q1: SEPAL for continual learning**\n\nSEPAL 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.\n\nTo demonstrate this, **we conducted an additional experiment** using two versions of the YAGO3 knowledge graph:\n- YAGO3-2014 (original release),\n- YAGO3-2022 (revived version).\n\nThe table below gives the statistics of these datasets.\n\n| Dataset       | #Entities   | #Relations | #Triples     |\n|:------------:|:-----------:|:----------:|:------------:|\n| YAGO3-2014    | 2,570,716   | 37         | 5,585,004    |\n| YAGO3-2022    | 4,546,966   | 37         | 14,691,781   |\n\nIn the continual learning setting (**SEPAL-CL**), we:\n- Initialized the embeddings of YAGO3-2022 using embeddings precomputed on YAGO3-2014,\n- Propagated embeddings for just 5 steps to update existing nodes and embed new entities.\n\nThe 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.\n\n| YAGO3 version | Method     | Avg. performance (normalized R²) | Runtime       |\n|:-------------:|:-----------:|:---------------------:|:--------------:|\n| 2014          | SEPAL      | 0.836                  | 0h 11m 20s    |\n| 2022          | DistMult   | 0.884                  | 11h 05m 36s   |\n| 2022          | SEPAL      | 0.988                  | 1h 05m 07s    |\n| 2022          | SEPAL-CL   | 0.962                  | 0h 01m 08s    |\n\nTable: Results of the continual-learning experiment, on the real-world downstream tasks.\n\nWe see that:\n- 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).\n- SEPAL from scratch is 10$\\times$ faster than DistMult.\n- **SEPAL-CL is 57$\\times$ faster than SEPAL from scratch, and 587$\\times$ faster than DistMult**.\n- **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.\n\nWe 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**.\n\n### **Q2: Dependency on connectedness and connectivity**\nWe 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.\n\nRegarding 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.\n\nThe **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.\n\n### **W1-2: Reliance on the Appendix**\nDue 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.\n\nTherefore, 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.\n\n### **Paper formatting**\nWe 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."}, {"review_id": "IKtGVeaCiI", "reviewer": "Reviewer_mvhY", "summary": "Knowledge graphs are widely used to store knowledge and can be leveraged to produce embeddings that benefit various applications. However, existing methods usually do not scale well. This paper proposes a method that first obtains embeddings on a small subgraph called core subgraph and then uses message passing to propagate embeddings outside the core subgraph. Extensive experiments corroborate the effectiveness of the proposed method.", "questions": "See above.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths**:\n\n1. The considered problem is of great importance to both academia and industry.\n\n2. The paper is well-written and easy-to-follow.\n\n3. The experimental results are sufficient to prove the effectiveness of the proposed method, from my perspective.\n\n4. The propagation step outside the core subgraph enjoys the advantage of existing knowledge graph embedding models and further affirms their effectiveness.\n\n5. The propagation step is theoretically guaranteed.\n\n**Weaknesses**:\n\n1. The BLOCS algorithm is described in the appendix. The authors could still describe its high-level ideas and main steps in the main paper.\n\n2. The authors mainly determine core subgraphs using node degrees. Other node centrality measures like PageRank score could also be tried.", "was_revised": true, "final_justification": "Both of my concerns are addressed by the authors. The additional experiments based on PageRank scores further  confirm the robustness of the proposed method. I will keep the score unchanged.", "rebuttal": "We thank the reviewer for the thoughtful review, insightful suggestions, and positive feedback.\n\nWe 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.\n\nBelow, we address the specific comments made by the review.\n\n### **1. BLOCS in the appendix**\nDue 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.\n\n### **2. Considering other centrality measures for core selection**\nFollowing 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.\n\nThe table below reports results on the real-world downstream tasks using normalized R² scores and training time (in parentheses).\n\n| Dataset         | Core defined by Degree           | Core defined by PageRank         |\n|-----------------|------------------|------------------|\n| YAGO3           | **0.783** (11m 20s) | 0.742 (9m 23s)   |\n| YAGO4           | 0.817 (6h 20m)     | **0.861** (4h 53m) |\n| YAGO4+T         | 0.815 (10h 9m)     | **0.881** (8h 16m) |\n| YAGO4.5         | **0.949** (4h 11m) | 0.925 (4h 3m)    |\n| YAGO4.5+T       | **0.923** (2h 47m) | 0.912 (2h 40m)   |\n| Freebase        | 0.917 (5h 58m)     | **0.919** (5h 58m) |\n| WikiKG90Mv2     | 0.898 (20h 31m)    | **0.902** (23h 59m) |\n\n**Performance**\n\nRegarding 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**.\n\n**Cost**\n\nRegarding 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.\n\nWe will include these findings, along with a brief analysis and discussion, in the final version of the paper."}, {"review_id": "KDzml7PdOH", "reviewer": "Reviewer_da1w", "summary": "SEPAL is an efficient method for large-scale knowledge graph embedding, addressing computational and memory bottlenecks through message passing and the BLOCS algorithm. Its improvements include:Time optimization: Utilizing the message passing mechanism, the embeddings of the core subgraph (selected by degree or a hybrid strategy of highly connected entities) are propagated to the entire graph, preserving the geometric properties of the relationships.Memory optimization: The graph is divided into overlapping subsets via the BLOCS algorithm to accommodate GPU memory constraints. The selection of the core subgraph takes into account both entity density and relationship diversity (such as a hybrid strategy combining node degree and relationship types), ensuring the quality of the embeddings.", "questions": "See Weakness.", "limitations": "Yes, the proposed method, while promising, reveals certain limitations in the Experiments section.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1.Significantly improve the performance of downstream tasks \n\n2.A single 32GB V100 GPU can handle graphs with hundreds of millions of nodes (such as the 91 million entities in WikiKG90Mv2), while baseline methods (such as DGL-KE) require distributed computing. \n\n3. It can capture the global structure and enhance the geometric consistency of the embedding by replacing local contrastive learning with relation-aware propagation.\n\nWeaknesses:\n1.Experimental design flaw: Insufficient coverage of downstream tasks\nMost tasks are based on table regression/classification and have not been validated in complex scenarios such as multi hop inference.\n2.In WikiKG90Mv2 link prediction, SEPAL's MRR (0.195) is significantly lower than PBG's (0.632).", "was_revised": true, "final_justification": "After the rebuttal and discussion process, I am happy to change my decision to accept this paper.", "rebuttal": "We thank the reviewer for their thoughtful and positive assessment of our work.\n\nWe 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.\n\nBelow, we address the reviewer’s comments in more detail.\n\n### **1. Experimental design and task focus**\nIn 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).\n\nThis 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.\n\nWe 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].\n\nTo 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**.\n\nWe 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.\n\nIf the paper is accepted, we will further clarify this distinction in the introduction and conclusion to avoid confusion regarding task scope.\n\n[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.\n\n[2] Pedro Tabacof and Luca Costabello. Probability calibration for knowledge graph embedding models. In International Conference on Learning Representations, 2020.\n\n[3] Hamilton, W., Bajaj, P., Zitnik, M., Jurafsky, D., & Leskovec, J.. Embedding logical queries on knowledge graphs. Advances in Neural Information Processing Systems, 2018.\n\n[4] Ren, H., & Leskovec, J.. Beta embeddings for multi-hop logical reasoning in knowledge graphs. Advances in Neural Information Processing Systems,  2020.\n\n### **2. Link Prediction Performance on WikiKG90Mv2**\nFollowing 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.\n\nThat 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**."}, {"review_id": "MRDea4JrEr", "reviewer": "Reviewer_UiQt", "summary": "Proposes a method to obtain knowledge graph embeddings for large knowledge graphs. This is done by decomposing the graph into a \"core\" (used for training and to obtain embeddings of frequent entities) and multiple potentially overlapping \"rest\" subgraphs (updated via message passing to obtain embeddings of remaining entities). Reports on an experimental study.", "questions": "/", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The main strength of this work lies in it's simplicity:\n\nS1. Simple method\n\nS2. Cheap to run\n\nS3. Reasonable heuristic (most frequent entities + neighbors)\n\nThe approach as a whole, however, fails to make a convincing case:\n\nW1. Cost arguments not convincing. KGE methods have been scaled to graphs larger than the largest one considered in the experimental study, including many works mentioned in Sec. 2.3 and including works that require few resources. It's not clear if there is a need for another method.\n\nW2. The subgraph propagation part (which is the key technical contribution) is not convincing. This is for three reasons:\n\nW2-1: Analysis limited. For the subgraph propagation step, the authors claim in text that their approach minimizes \"a global energy\". The actual proposition then limits this to DistMult, identity similarity and \"sum of scores\" objective; this is does not reflect an actually interesting setting (e.g., sum of scores is not a suitable KGE training objective).\n\nW2-2: The method seems to be equivalent to the one of Albooyeh et al. (EMNLP Findings, 2020, https://aclanthology.org/2020.findings-emnlp.241/).\n\nW3-3: It's not clear why the decomposition method (appendix) is needed for propagation and what its impact is w.r.t. to the analysis of Prop. 4.1. Can't this simply be done on the CPU (e.g., stream edges through)?\n\nW3. Experimental setup not clear. Neither the hyperparameters (which ones there are and which ranges have been explored) nor the search strategy has been described in the paper. This includes hyperparameters of the proposed method as well as the underlying KGE method, and the cost/validation objectives used for the core graph.\n\nW4. Experimental study not insightful. This is for multiple reasons.\n\nW4-1: The paper compares to embeddings trained using PyTorch BigGraph and DGL-KE, neither of which is a state of the art method; i.e., no newer \"large KG\"-methods are considered.\n\nW4-2: Transductive methods are not timely anymore, esp. in the KG setting, since good inductive methods exist by now; e.g., Cui et al. (NeurIPS 2024, https://proceedings.neurips.cc/paper_files/paper/2024/hash/0d70af566e69f1dfb687791ecf955e28-Abstract-Conference.html). Such methods are neither discussed nor compared to.\n\nW4-3: The proposed method aims to optimize link prediction performance cheaply (as that's the idea behind propagation), and, as expected, falls behind link prediction methods (as shown in the appendix). Nevertheless, the proposed method achieves better vertex classification/regression scores in the experimental study. It's neither explored nor intuitively clear why this is the case.", "was_revised": true, "final_justification": "The authors conducted a number of additional experiments in their final response, which strengthens their case. I feel that this paper is not ready, though, but requires a revision (which we do not have here, unfortunately).\n\n> On W1. My key point is that scalable (and also low-cost / single-GPU) methods exist but have not been considered in the experimental study.\n\nThe authors report numbers on SMORE, an older method, in their response and state that they could not get Marius* to run. This addresses this point somewhat, and could be fully addressed by rewriting the paper and removing claims that existing methods \"struggle to scale\", as they clearly do not. \n\n> On W2-1) This objective is not well-motivated then, and I did not fully understand the alignment discussion in the paper. I found the response somewhat confusing because this objective is not used for the core (why not?), and quality (\"alignment\") and scalability (core+propagation) arguments are mixed in the paper.\n\nThis point is not addressed (as it would require revising that part), but the additional experimental results provided by the authors are promising and indicate that the \"alignment\" may be useful.\n\n> On W2-2) A comparison to this work is missing in the paper (both in words and in experimental study).\n\nHere the quick experimental comparison again looks favorable for the proposed method. A more thorough setup and discussion of technical differences is still open though; that's important as this work appears conceptually very close.\n\n> On W2-3) I am not convinced a new method is needed here. The propagation is \"just\" a GNN, and GNNs have been scaled to very large graphs (e.g., by MariusGNN). (Also, it's not clear why this would take 24h on a CPU, as it's cheap per edge operations and edges can be streamed through multiple cores. But that's not the key point.)\n\nHere also the setup is not clear. As backprop is not needed, we can simply stream the edges and aggregate the messages; in parallel over arbitrarily many cores (with the usual tricks).\n\n> On W4-1) DGL-KGE and PyTorch-BigGraph are not SOTA; e.g., MariusGNN is a natural baseline, as are all the newer large-scale GNN works.\n> On W4-2) It still needs discussion. And what about TIGER (https://dl.acm.org/doi/10.14778/3675034.3675039)?\nSee above.\n\n> On W4-3) To see if this is true (it might be), a well-tuned SOTA link prediction method should be trained and compared to. In fact, the response mentions [1], which seems to have done just that (on smaller graphs); so why not compare to SEPAL on these datasets? See also W2-2.\n\nThe authors report convincing results here.\n\n\nBased on the rebuttal, I am now more convinced that the proposed \"alignment\" is useful in practice, whereas the scalability part appears rather nice to have than a crucial novelty (and, again, it's unclear if BLOCS is needed). \n\nI've upped my rating and downed my confidence to reflect these thoughts.", "rebuttal": "We sincerely thank the reviewer for the detailed review.\n# Preamble\nBefore 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.\n\n### **Research problem**\nOur 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**.\n\nRecent 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**.\n\nOur 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.\n\n[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.\n\n### **Contributions**\n1. 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).\n2. 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.\n3. We propose **SEPAL**, a method designed to maximize this global consistency, and we **theoretically analyze** its propagation step to support this claim.\n4. 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).\n5. 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.\n\n# Specific points\nWe now address each of the reviewer’s concerns in detail.\n\n### **W1. “Cost arguments not convincing”; “not clear if there is a need for another method”**\n\nOur 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.\n\nWhile 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.\n\nSEPAL 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.\n\n### **W2-1. Theoretical analysis of the propagation**\nOur 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.\n\nThis 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.\n\nFor 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.\n\n### **W2-2: Comparison to Albooyeh et al.**\nAlbooyeh 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**:\n\n- **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.\n\n- **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.\n\n### **W2-3: Why BLOCS is needed**\nBLOCS 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**.\n\n### **W3: Clarify experimental setup**\nWe 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.\nRegarding 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.\n\n### **W4-1: Choice of baselines**\nWe 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.\n\n**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.\n\n### **W4-2: “no inductive method discussed nor compared to”**\nOur experiments already include **NodePiece**, an inductive method that can scale up to YAGO4.5 (32M entities).\n\nInductive 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).\n\nThe 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.\n\n### **W4-3: SEPAL performs better on downstream tasks than link prediction**\nWe 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."}]

Author rebuttal:

Meta-review: This paper proposes SEPAL, an approach to learn knowledge graph embeddings on large graphs which can be used to enrich downtream task applications like classification and regression.  The authors propose a two stage approach which involves computing embeddings over a small subgraph (core subgraph) and propagating these over the rest of the graph.  The authors discuss optimizations for training as well as show improvements in performance of embeddings learned with SEPAL on downstream tasks.

This paper leans towards acceptance, and the rebuttal efforts were generally appreciated by reviewers, some of whom raised scores.  Authors introduced new baselines and some referenced benchmarks as well, which do not detract from their claims.

Main feedback points:

- this paper is heavily reliant on appendix and the main content of the paper doesn't stand well on its own without frequent referencing to the appendix.  This brings down the evaluation and I encourage the authors to find ways to better focus on the key points to communicate in the main paper (aZkD, mvhY)

- some reviewers took issue with baseline choice (e.g. adopting newer baselines like Marius or TIGER), as well as inclusion of other downstream tasks (UiQt)

- there were some questions about theoretical and conceptual clarity (rationale behind the chosen core selection method, theoretical analysis of global energy objective, and relative novelty of the propagation step compared to prior works (UiQt, mvhY)
Decision: Accept (poster)