Traditional Knowledge Graph (KG) embedding models suffer from a fundamental scalability law: they assign a unique, high-dimensional vector to every entity. As Mrinmaya Sachan notes, this causes model size to grow linearly with the number of entities, creating a prohibitive memory bottleneck for real-world graphs containing millions or billions of nodes.
To break this linear scaling, a new generation of research moves away from "atomic" embeddings—where an entity is an opaque ID—toward "compositional" and "entity-agnostic" representations. These methods allow models to represent massive graphs using a fixed, small number of parameters.
Tokenizing the Graph
In Natural Language Processing, we don't learn a unique vector for every possible string; we tokenize words into subword units. NodePiece, introduced by Mikhail Galkin and colleagues, applies this logic to graphs.
Instead of a dedicated embedding for "Albert Einstein," NodePiece represents the entity as a set of "anchors" (nearby landmark nodes) and the relational paths leading to them. By learning a vocabulary of only a few thousand anchors, the model can represent millions of entities. This approach achieves up to 70x parameter reduction and, crucially, allows the model to handle "out-of-vocabulary" entities seen only at inference time.
Quantization and Random Mapping
Another path to efficiency is discrete quantization. In Knowledge Graph Embedding Compression, Mrinmaya Sachan proposes representing entities as sequences of discrete "KD codes." An autoencoder reconstructs the continuous representation from these codes, allowing for 50x to 1000x compression.
Surprisingly, the mapping between an entity and its components doesn't always need to be learned. Jiaang Li and colleagues demonstrated in Random Entity Quantization that even randomly assigning entities to a shared codebook of vectors works remarkably well. The intuition is that random assignment provides enough mathematical distinctness to distinguish millions of entities while forcing the model to learn shared relational patterns rather than memorizing individual node IDs.
Reasoning Without Identities
The most radical shift is toward "fully entity-agnostic" models. These systems eliminate entity embeddings entirely, relying instead on the local topology and relational paths.
- Path-based Reasoning: PathE, proposed by Ioannis Reklos and others, dynamically computes entity representations from relational paths. By focusing on how nodes are connected rather than who they are, PathE uses less than 25% of the parameters of previous efficient models.
- Temporal Migration: In the context of temporal graphs, the DaeMon framework by Hao Dong decouples reasoning from entity identities. Because the model learns the "logic" of relations rather than specific node features, it can migrate to entirely new datasets without retraining.
- Social Dynamics: This trend extends to recommendation systems. PULSE, developed by Jaemin Yoo and team, removes user embeddings by constructing representations on-the-fly from social communities and interaction history.
The Generative and Textual Turn
Finally, researchers are leveraging Pre-trained Language Models (PLMs) to bypass the embedding table entirely. KGT5, by Apoorv Saxena and colleagues, treats KG completion as a sequence-to-sequence task. Instead of looking up a vector, the model "reads" the entity name and "writes" the answer.
This shift, supported by libraries like LambdaKG and frameworks like JAKET, allows models to use the rich semantic knowledge already present in language models. As Donghan Yu argues, text provides the context and grounding that static, ID-based embeddings lack, enabling a more flexible and scalable understanding of world knowledge.