PaperlayerView exact revision on arXiv

Source-linked AI summary

NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs

Mikhail Galkin, Etienne Denis, Jiapeng Wu, William L. Hamilton

arXiv:2106.12144v2cs.CLcs.AIcs.LG

TL;DR

Shallow entity lookup embeddings make KG memory scale linearly with the number of nodes. NodePiece represents nodes compositionally using a fixed vocabulary of anchors and relations. It reports competitive results across several prediction tasks, including for unseen entities, while using far fewer anchors than nodes.

  • Problem

    Shallow KG embedding lookups scale linearly with the number of nodes, making representation learning on large graphs computationally challenging.

    Source: §1 · p. 1

  • Method

    NodePiece tokenizes each node into a hash of nearby anchors and immediate relations, then encodes it using a fixed-size vocabulary.

    Source: §1 · p. 2

  • Results

    NodePiece is competitive in link prediction, node classification, and relation prediction, supports prediction for unseen entities, and can use 10–100× fewer anchors than nodes.

    Source: §1 · p. 2, §5 · p. 9

  • Takeaways & Limitations

    NodePiece can represent unseen entities with the same anchor-based tokenization and downstream prediction approach used for seen entities.

    Source: §1 · p. 2, §5 · p. 9

    Encoding full relational paths separately with a sequence encoder is not scalable, so the paper does not use that approach.

    Source: §3.3 · p. 4

Abstract

from arXiv · show

Conventional representation learning algorithms for knowledge graphs (KG) map each entity to a unique embedding vector. Such a shallow lookup results in a linear growth of memory consumption for storing the embedding matrix and incurs high computational costs when working with real-world KGs. Drawing parallels with subword tokenization commonly used in NLP, we explore the landscape of more parameter-efficient node embedding strategies with possibly sublinear memory requirements. To this end, we propose NodePiece, an anchor-based approach to learn a fixed-size entity vocabulary. In NodePiece, a vocabulary of subword/sub-entity units is constructed from anchor nodes in a graph with known relation types. Given such a fixed-size vocabulary, it is possible to bootstrap an encoding and embedding for any entity, including those unseen during training. Experiments show that NodePiece performs competitively in node classification, link prediction, and relation prediction tasks while retaining less than 10% of explicit nodes in a graph as anchors and often having 10x fewer parameters. To this end, we show that a NodePiece-enabled model outperforms existing shallow models on a large OGB WikiKG 2 graph having 70x fewer parameters.

1 INTRODUCTION

Shallow KG embeddings scale with the number of nodes, making large graphs computationally challenging. NodePiece adapts the fixed-vocabulary idea of NLP subword tokenization to represent nodes compositionally and report competitive results across several tasks, including for unseen entities.

1 INTRODUCTION

  • Shallow entity embeddings require O(|N|) space, and scaling to large Wikidata subsets may require a GPU or CPU cluster to maintain a 78M × 200d matrix.The paper contrasts this with smaller conventional benchmarks such as Freebase (~15K nodes) and WordNet (~40K nodes).Source: §1 · p. 1
  • Like NLP subword methods, NodePiece uses a fixed-size vocabulary of graph pieces rather than one learned vector per entity.NLP subword units allow fixed-size vocabularies to form combinations and address out-of-vocabulary words.Source: §1 · pp. 1–2
  • NodePiece tokenizes each node into a hash of nearby anchors and immediate relations, then applies an encoder to produce its embedding.The parameter budget depends on the vocabulary and encoder rather than a separate entity embedding for every node.Source: §1 · p. 2
  • NodePiece reports competitive results in link prediction, node classification, and relation prediction, and anchor-based hashing supports prediction for unseen entities.The paper contrasts this with unseen-entity scenarios that otherwise required tailored learning mechanisms.Source: §1 · p. 2

2 RELATED WORK

The related work spans shallow KG embeddings, compression, feature-based hashing, language-model representations, and out-of-sample learning. NodePiece is positioned as a replacement for per-node lookups that can also tokenize newly arriving entities.

Conventional KG embedding approaches

  • KG embedding families and relation-aware GNNs commonly retain learned node embeddings or feature vectors, which NodePiece can replace as a drop-in lookup alternative.The cited families include translational, tensor-factorization, convolutional, and hyperbolic models.Source: §2 · p. 2

Distillation and compression

  • Embedding distillation and discrete-code compression still require a full embedding matrix as input, unlike NodePiece’s design goal.The passage describes distillation into low-dimensional counterparts and compression into discrete codes.Source: §2 · p. 2

Vocabulary reduction in recommender systems

  • Anchor-based hashing in recommender systems factorizes sparse feature vectors, whereas NodePiece learns its vocabulary embeddings from scratch without assuming KG feature vectors.Source: §2 · p. 2

Out-of-sample representation learning

  • Figure 1 depicts NodePiece hashes as combinations of nearest anchors, their distances, and the target node’s outgoing relational context.Source: Figure 1 · p. 3

Entity descriptions and language models

  • Language-model entity-description methods are orthogonal to NodePiece; textual features may be absent in domain-specific KGs, but can be concatenated with NodePiece features when available.Source: §2 · p. 3

Out-of-sample representation learning

  • Prior out-of-sample methods use neighborhood aggregation or meta-learning while retaining shallow embeddings; NodePiece tokenizes new nodes from their new edges using an existing vocabulary.Source: §2 · p. 3

3 NODEPIECE VOCABULARY CONSTRUCTION

NodePiece constructs a fixed vocabulary from anchor nodes and relation types, then tokenizes nodes into anchor- and relation-based sequences for encoding. Its construction choices address graph connectivity, token collisions, and permutation invariance while allowing different encoder designs.

3 NODEPIECE VOCABULARY CONSTRUCTION

  • The vocabulary combines a preselected set of anchor nodes with relation types, and inverse edges are added to preserve reachability and balance in- and out-degrees.Each node is represented by nearby anchors, discrete anchor distances, and immediate relations.Source: §3 · p. 3

3.1 ANCHOR SELECTION

  • Random anchor selection performed as effectively as centrality-based selection in preliminary experiments, while degree- or PPR-based choices can skew anchor distances toward 2- or 3-hop neighborhoods.Source: §3.1 · pp. 3–4

3.2 NODE TOKENIZATION

  • Each node’s hash uses k anchors with their shortest-path distances and m sampled immediate outgoing relations, padding the relation set when needed.Disconnected nodes receive an auxiliary token or can be selected as anchors; the authors say this is negligible in most existing KGs because few nodes are disconnected.Source: §3.2 · p. 4
  • Random tokenization samples an unordered set of k anchors and requires enough combinations to avoid collisions, so its hashes are precomputed; deterministic tokenization uses k nearest anchors found by BFS.For deterministic tokenization, anchor distances and relational context provide additional signals to distinguish nearby nodes with similar anchors.Source: §3.2 · p. 4

3.3 ENCODING

  • The encoding pipeline vectorizes the token hash from learned anchor and relation vectors plus distance embeddings, with summed anchor representations retaining a (k + m) × d hash dimension.The resulting vectorized hash is the input to the encoder.Source: §3.3 · pp. 4–5
  • Nearest-anchor hashing has more collisions but is effectively permutation invariant, and the proposition characterizes it as a π-SGD approximation to Janossy pooling.The canonical ordering is induced by anchor distances; the permutation-invariant encoding and lack of transductive node-specific features support inductive learning.Source: §3.3 · p. 5
  • With a fixed vocabulary, downstream parameter and complexity budgets depend largely on encoder complexity; the tested MLP is faster and scales better to more edges, while the Transformer uses fewer trainable parameters.The authors leave study of more efficient and effective encoders for future work.Source: §3.3 · p. 5

4 EXPERIMENTS

The experiments assess NodePiece across transductive, inductive, out-of-sample link prediction, and node classification, rather than seeking to outperform every existing approach. They report competitive performance with smaller vocabularies across these tasks.

4 EXPERIMENTS

  • The experimental program tests NodePiece across transductive, inductive, out-of-sample link prediction, and node classification, with transductive comparisons against RotatE.For the transductive link-prediction experiments, five KGs range from about 15K to 2.5M nodes.Source: §4 · p. 5, §4.1 · p. 5

4.1 TRANSDUCTIVE LINK PREDICTION

  • A vocabulary below 10% of graph nodes retains 80–90% of the strongest shallow models’ Hits@10; on YAGO 3-10, a similarly sized RotatE model scores 20 Hits@10 points lower.The authors attribute the YAGO gap to NodePiece’s ability to use larger anchor embeddings under a small parameter budget.Source: §4.1 · pp. 5–6, Table 3 · p. 6
  • Anchor requirements vary with graph structure: Hits@10 saturates from 25 anchors on dense FB15k-237, while sparse WN18RR needs more anchors; larger vocabularies also help more precise predictions.The authors hypothesize that longer anchor distances in sparse graphs account for the difference; diminishing returns begin around anchor sets of 1% of nodes.Source: §4.1 · p. 6, Figure 2 · p. 7
  • In transductive link prediction, removing relational context and anchor distances has little effect on dense FB15k-237 but harms sparse WN18RR; relation-only hashes retain fair FB15k-237 performance but yield zero on WN18RR.The authors connect the difference to FB15k-237 having 20× more unique relations than WN18RR.Source: §4.1 · p. 6

4.1.1 OGB WIKIKG 2

  • On WikiKG 2, NodePiece + AutoSF uses 6.9M parameters—about 70× fewer than top shallow models—while achieving better performance than the best reported shallow approaches.The graph has 2.5M nodes and 16M edges; the result is averaged over 10 seeds.Source: §4.1.1 · p. 7, Table 4 · p. 7

4.2 INDUCTIVE LINK PREDICTION

  • NodePiece + CompGCN outperforms GraIL in all but one inductive experiment and is competitive with NBFNet on relation-rich FB15k-237 splits.The benchmark uses disjoint training and inference graphs, so entity hashes use relational context without training-graph anchors.Source: §4.2 · pp. 7–8, Table 5 · p. 8

4.3 NODE CLASSIFICATION

  • With 50 anchors against 46K entities, NodePiece + CompGCN reaches ROC-AUC 0.98, with +16–19 PRC-AUC points and a 3× boost in Hard Accuracy over baselines.The gains remain when the labeled-node fraction rises to 10%; performance is saturated with 50 anchors.Source: §4.3 · pp. 8–9, Table 6 · p. 8

4.4 OUT-OF-SAMPLE LINK PREDICTION

  • On out-of-sample FB15k-237, NodePiece retains about 90% of oDistMult’s performance; on larger oYAGO 3-10, oDistMult runs out of memory while NodePiece converges in 40 epochs.NodePiece uses the same vocabulary to tokenize seen and unseen entities, without task-specific modifications.Source: §4.4 · p. 9, Table 7 · p. 9

5 CONCLUSION

NodePiece represents multi-relational graph nodes compositionally using a fixed-size vocabulary of anchors and relations. Its anchor set can be 10–100 times smaller than the node set, and it can tokenize unseen entities for downstream prediction.

5 CONCLUSION

  • NodePiece tokenizes each node as a combination of anchors and relations from a fixed-size vocabulary.The approach is compositional, similar to subword units.Source: §5 · p. 9
  • The number of anchors can be 10–100× smaller than the total number of nodes.Source: §5 · p. 9
  • In some tasks, rich relation types make node embeddings unnecessary for acceptable accuracy.Source: §5 · p. 9
  • NodePiece is inductive by design: it tokenizes unseen entities and performs downstream prediction as it does for seen entities.Source: §5 · p. 9

A IMPLEMENTATION & HYPERPARAMETERS

The appendix describes implementation, datasets, and task setups, then discusses deployment in dynamic graphs and a hypothesized scaling property. NodePiece can materialize embeddings for new nodes without recomputing representations for all existing nodes.

A IMPLEMENTATION & HYPERPARAMETERS

  • Experiments use a deterministic anchor mix of 40% top-PPR nodes, 40% top-degree nodes, and 20% random nodes, with non-overlapping selections.The appendix also specifies Python/igraph for centrality and tokenization, PyTorch, PyKEEN, and PyTorch-Geometric for downstream tasks, and the GPU/RAM configurations.Source: A IMPLEMENTATION & HYPERPARAMETERS · p. 15

A.1 DATASETS

  • The datasets cover transductive and out-of-sample link prediction, relation prediction, and node classification; the inductive benchmark has three graphs with four splits each.FB15k-237 and most NELL-995 splits are relation-rich, while WN18RR is sparse with few relation types; dataset and inductive relation-prediction statistics are tabulated.Source: §A.1 · p. 15, Table 8 · p. 15, Table 9 · p. 15

A.2 TRANSDUCTIVE LINK PREDICTION

  • Transductive link-prediction experiments use Adam; RotatE’s reported embedding dimension sums its real and imaginary dimensions.For example, 1000d denotes 500 dimensions for each component.Source: §A.2 · p. 16

A.3 RELATION PREDICTION

  • Relation-prediction configurations largely follow the transductive setup, with fewer epochs and negative samples because models converge faster.Source: §A.3 · p. 16

A.4 NODE CLASSIFICATION

  • For node classification, NodePiece bootstraps the node-embedding matrix before CompGCN, whereas CompGCN and MLP use directly trained node embeddings.The appendix lists node-classification hyperparameters in Table 13.Source: §A.4 · p. 16, Table 13 · p. 17

A.5 OUT-OF-SAMPLE LINK PREDICTION

  • Out-of-sample link-prediction settings use DistMult and a Transformer encoder; oDistMult on oYAGO 3-10 was omitted because preprocessing exceeded the available 256 GB RAM.NodePiece training times exclude evaluation, and baseline oDistMult training times were not reported by its authors.Source: §A.5 · pp. 16–17, Table 14 · p. 18

A.6 DEPLOYMENT IN REAL-WORLD DYNAMIC KNOWLEDGE GRAPHS

  • NodePiece can materialize embeddings for new nodes without recomputing every other node’s representation, supporting dynamic-graph settings with latency requirements.The authors describe caching the embedding matrix and updating embeddings as nodes and edges arrive.Source: §A.6 · p. 17

B LIMITATIONS AND FUTURE WORK

  • The authors hypothesize, but do not prove, that NodePiece’s parameters can grow sublinearly with graph size while performance is maintained.Their rationale is that anchor combinations grow with anchor count and that sublinear anchor growth may maintain average node–anchor distance; they believe stable hashing uniqueness and distances may suffice for equivalent performance.Source: B LIMITATIONS AND FUTURE WORK · p. 18

C ANCHOR SELECTION STRATEGIES

Anchor selection affects node-to-anchor distances: centrality-based selection and nearest-anchor sampling generally favor shorter distances than random alternatives. Increasing the total anchor count with nearest sampling also shortens distances, with larger distance changes in sparse WN18RR than in denser FB15k-237.

C ANCHOR SELECTION STRATEGIES

  • PPR, degree, and mixed anchor selection generally skew distances toward smaller values than random selection; nearest-per-node sampling also shifts distances lower than random sampling.Figure 3 compares the distributions on WN18RR and FB15k-237 under the main-experiment configurations.Source: C ANCHOR SELECTION STRATEGIES · p. 18, Figure 3 · p. 19
  • With mixed anchor selection and nearest-per-node sampling, increasing total anchors A from 50–1000 on WN18RR and 20–1000 on FB15k-237 shifts anchor distances lower.Figure 4 shows the distance distributions across these anchor counts.Source: C ANCHOR SELECTION STRATEGIES · p. 19, Figure 4 · p. 19
  • Sparse WN18RR benefits more in average node–anchor distance from increasing A than dense FB15k-237.Figure 5 varies A from 25 to 1000 and k from 5 to 50; smaller A/k configurations are described as inferior on WN18RR but competitive on FB15k-237.Source: C ANCHOR SELECTION STRATEGIES · p. 20, Figure 5 · p. 20

D EMBEDDING VISUALIZATIONS

  • The embedding visualizations use tSNE and UMAP projections of sampled entities and their most common anchors from FB15k-237 and WN18RR.The samples contain 1,000 entities from FB15k-237 and 4,000 from WN18RR, with each set’s top 100 common anchors.Source: D EMBEDDING VISUALIZATIONS · p. 20
  • The visualizations show the encoder reconstructing clusters of similar entities while anchors are distributed among communities.Communities have nearby specialized anchors; less common anchors cluster together in FB15k-237, while encoded entities remain in distinct clusters.Source: D EMBEDDING VISUALIZATIONS · p. 20

E TRANSDUCTIVE LINK PREDICTION RESULTS: MRR

MRR results indicate that sparse WN18RR needs larger anchor configurations before performance saturates, whereas denser FB15k-237 saturates at smaller configurations. The section also describes the construction and resulting scale of the WD50K node-classification dataset.

E TRANSDUCTIVE LINK PREDICTION RESULTS: MRR

  • On WN18RR, smaller A/k settings such as 25/5 or 50/10 struggle on precise Hits@1 predictions, and performance begins to saturate at 500/10.On FB15k-237, the minimum-to-maximum MRR difference is less than 4 points, with saturation evident at 50/10; Figure 8 compares MRR across anchor configurations.Source: E TRANSDUCTIVE LINK PREDICTION… · pp. 20–21, Figure 8 · p. 22

F.1 NODE CLASSIFICATION: WD50K NC

  • The WD50K node-classification dataset removes instance-of and subclass-of triples, extracts three-hop class hierarchies, and retains labels appearing at least 50 times in training.The resulting graph has 46k nodes, 526 relation types, and 465 class labels; 10% of labeled nodes are sampled for validation and 10% for test.Source: §F.1 · pp. 21–22

E TRANSDUCTIVE LINK PREDICTION RESULTS: MRR

  • Figure 8 compares MRR across combinations of total anchors A and anchors per node, with faster saturation on denser FB15k-237 than on sparse WN18RR.Source: Figure 8 · p. 22

F.2 OUF-OF-SAMPLE LINK PREDICTION: OYAGO 3-10

The out-of-sample YAGO 3-10 validation and test sets are formed by randomly sampling entities and assigning their incident triples to held-out splits.

F.2 OUF-OF-SAMPLE LINK PREDICTION: OYAGO 3-10

  • 5% of entities appearing in at least two triples are randomly sampled for validation and another 5% for test.The original train, validation, and test triples are first merged for transductive link prediction.Source: §F.2 · p. 22
  • Triples containing a sampled entity as subject or object are assigned to its validation or test set, respectively.These edges connect an unseen entity with the seen graph.Source: §F.2 · p. 22
  • Only entities appearing in at least two triples are eligible for out-of-sample sampling.Source: §F.2 · p. 22

G NODE CLASSIFICATION: TRAINING CURVES

On WD50K node classification with 5% labeled nodes, NodePiece has smaller training–validation gaps than the compared baselines, while the authors relate this pattern to explicit node embeddings adding noise.

G NODE CLASSIFICATION: TRAINING CURVES

  • Figure 9 compares training and validation Hard Accuracy and PRC-AUC on WD50K with 5% labeled nodes; generalization gap is defined as their delta.The NodePiece configuration uses 50 anchors, 10 nearest anchors per node, and 5 unique relation types.Source: G NODE CLASSIFICATION: TRAINING CURVES · p. 22
  • 2–3× smaller validation performance than training is reported for CompGCN, while NodePiece has the smallest generalization gaps.NodePiece validation performance is very close to training on Hard Accuracy, and its PRC-AUC gap is smaller than 10 points.Source: G NODE CLASSIFICATION: TRAINING CURVES · p. 22
  • MLP quickly overfits and fails to generalize on validation, whereas CompGCN has a smaller but still significant gap.Source: G NODE CLASSIFICATION: TRAINING CURVES · p. 22
  • The ablation suggests explicit node embeddings do not contribute to classification performance, and the authors hypothesize they add noise in overparameterized baselines.They also report no performance improvement when increasing the A/k anchor configurations.Source: G NODE CLASSIFICATION: TRAINING CURVES · p. 22

H PROOFS

The proof section frames NodePiece hashing through approximate permutation-invariant pooling; the accompanying relation-prediction and inductive-link-prediction discussions report competitive performance with reduced or relation-only vocabularies.

H PROOFS

  • Janossy pooling sums over all permutations and is computationally intractable, motivating canonical orderings, k-ary pooling, and π-SGD approximations.Source: H PROOFS · p. 23
  • Nearest anchors are ordered by distance, but equidistant anchors prevent a fully permutation-invariant canonical ordering; truncation and randomized tie ordering approximate Janossy pooling.Varying k and the relational-context size truncates the sequence, while π-SGD samples possible permutations during training and evaluation.Source: H PROOFS · pp. 22–24

I RELATION PREDICTION

  • More than 97% Hits@10 across graphs of different sizes is reported for NodePiece relation prediction with reduced vocabulary sizes.On WN18RR and YAGO 3-10, models with fewer anchors even slightly improve accuracy over the shallow embedding baseline; relation-only hashes match performance on FB15k-237 and YAGO 3-10.Source: I RELATION PREDICTION · p. 24, Table 15 · p. 24

J INDUCTIVE LINK PREDICTION

  • Without anchors, NodePiece vocabulary size depends only on relation types, and the results across four increasing-size splits show competitive inductive performance on dense, relation-rich graphs.Inference relation types are a subset of those seen in training; evaluation ranks each triple against 50 random negatives using Hits@10.Source: J INDUCTIVE LINK PREDICTION · p. 24

K UNIQUENESS OF NODE HASHES

The section considers how many distinct node hashes tokenization can produce, while distinguishing a large combinatorial capacity from guarantees under deterministic nearest-anchor selection.

K UNIQUENESS OF NODE HASHES

  • 4.7 · 10^13 combinations are reported, enough to cover all existing public KGs combined.Source: K UNIQUENESS OF NODE HASHES · p. 25
  • Deterministic nearest-anchor selection has no uniqueness guarantees, although relational contexts and anchor distances can add more unique hashes.Source: K UNIQUENESS OF NODE HASHES · p. 25
  • Collisions remain possible in highly regular graphs such as Wordnet, while Wikidata and DBpedia are described as not having such regular structure.The authors identify tighter uniqueness bounds and new sampling and tokenization strategies as future work.Source: K UNIQUENESS OF NODE HASHES · p. 25

Related papers

Loading 2106.12144v2…