Graph representation learning has traditionally relied on a straightforward paradigm: assign every node or entity a unique, dense, high-dimensional floating-point vector. As formalized in the foundational encoder-decoder framework by Jure Leskovec et al., these vectors act as lookups that map discrete nodes into continuous spaces where geometric distances reflect structural similarities. Early translational models like TransE, introduced by Antoine Bordes, demonstrated that simple vector arithmetic ($\mathbf{h} + \mathbf{r} \approx \mathbf{t}$) could effectively capture multi-relational semantics.
However, this paradigm suffers from a fundamental scalability flaw: the memory footprint scales linearly ($O(N)$) with the number of nodes. When moving from small benchmark datasets to web-scale social networks or massive production knowledge bases containing millions or billions of entities, the embedding table quickly outgrows the memory capacity of standard hardware. As noted by Cheng Yang et al. and Ke Sun et al., this "memory wall" makes full-batch training and real-time deployment on resource-constrained or edge devices impossible. To bypass this bottleneck, researchers have developed several distinct strategies to compress, decompose, or entirely reimagine how graph structures are represented.
Discretization and Hashing
One intuitive way to break the memory wall is to change the data type of the representation itself. Instead of storing nodes as sequences of 32-bit floating-point numbers, discrete network embedding methods compress representations into compact binary codes or discrete indices.
For instance, Shirui Pan et al. introduced Discrete Network Embedding (DNE), which directly learns binary codes for nodes and optimizes them jointly with a discrete classifier. Similarly, the node2bits framework by Mark Heimann et al. combines temporal random walks with feature-based hashing to generate compact binary "fingerprints."
Why does this work? Graphs often exhibit significant structural redundancy; many nodes share nearly identical local neighborhoods. By mapping continuous spaces to discrete bit vectors, these frameworks exploit this redundancy. A single bit can partition the graph, and a short sequence of bits can uniquely pinpoint a node's structural role. In another approach, Mrinmaya Sachan proposed representing entities as sequences of discrete "KD codes" via an autoencoder architecture, achieving up to 1000x compression. This drastic reduction occurs because discrete codes compress the representation size per node from hundreds of bytes to just a few bits, allowing massive graphs to fit entirely within fast cache memory or on mobile devices.
Compositional and Anchor-Based Representations
Instead of giving every node its own independent parameters, compositional approaches represent nodes as combinations of a small, shared vocabulary of base elements. This is highly analogous to subword tokenization (like Byte-Pair Encoding) in natural language processing, where a massive vocabulary of words is reconstructed from a small set of subword tokens.
A prime example of this is NodePiece, a framework developed by Mikhail Galkin et al.. NodePiece selects a small fraction of nodes to serve as "anchors." Any regular node in the graph is then represented solely by its spatial relationship (e.g., shortest paths or relational context) to its nearest anchors. Because the model only stores explicit embedding vectors for the anchors and the relation types, the total parameter count drops dramatically.
Similarly, the Multi-Hot Compact Network Embedding (MCNE) framework by Chaozhuo Li et al. represents nodes using a small set of shared "basis vectors" combined with discrete multi-hot indices. In the unsupervised domain, Xuelong Li utilized an anchor-based graph strategy to reduce the computational and storage complexity of spectral embeddings from quadratic to linear. These methods work because a graph's global topology can be effectively triangulated; you do not need to know a node's absolute coordinates in a latent space if you know its exact relative position to a fixed set of global landmarks.
Tensor Decomposition and Dimension Lifting
Another powerful strategy applies algebraic compression directly to the embedding matrix. Rather than storing a raw $N \times D$ table, the matrix is represented implicitly as the product of much smaller, low-rank tensors.
Chunxing Yin et al. applied Tensor-Train (TT) decomposition to Graph Neural Network (GNN) embedding tables. By breaking a massive matrix into a chain of low-dimensional core tensors, they compressed embedding tables by up to 80,000x, allowing billion-node graphs to fit entirely within GPU memory.
Conversely, instead of compressing a large matrix after the fact, the LiftNet architecture by Borui Cai et al. trains models using tiny, low-dimensional vectors (e.g., 16 dimensions) and passes them through a deep "dimension lifting" upsampling network to project them into highly expressive spaces when needed. This works because the underlying semantic dimensionality of graph nodes is often much lower than the high-dimensional vector space required to prevent collisions and resolve complex multi-relational interactions. Low-rank decompositions and lifting networks exploit this low intrinsic dimensionality, materializing the high-dimensional representation only during active computation.
Caching and Entity-Agnostic Message Passing
When full embedding tables cannot be compressed away, scaling requires changing how memory is managed during training or shifting the learning target entirely away from node identities.
To stabilize training on massive graphs without blowing up GPU memory, frameworks like GNNAutoScale, developed by Jan Eric Lenssen et al., and GraphFM, by Haiyang Yu et al., utilize "historical embeddings." Instead of recomputing representations across the entire graph at every layer (which causes an exponential "neighborhood explosion"), these systems cache node representations from previous iterations in system RAM or out-of-core storage, pulling them into GPU memory only when needed.
Alternatively, some frameworks eliminate entity embeddings altogether. The PathCon framework by Hongwei Wang et al. shifts the focus of Knowledge Graph Completion from entity identities to the relationships themselves. By aggregating local connectivity paths via relational message passing, PathCon predicts missing links based purely on structural context. Similarly, the EARL framework by Hao Zhou et al. utilizes entity-agnostic representation learning to generalize to unseen entities.
These methods work because the predictive power of a graph often resides in its local connectivity patterns and relational paths rather than the specific names or IDs of individual nodes. By learning how structures behave rather than memorizing who each node is, these models achieve complete inductive scalability with a fraction of the memory footprint.