NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs
Authors: Mikhail Galkin
Etienne Denis
Jiapeng Wu
William L. Hamilton
Venue: ICLR 2022 Poster (2022)
Keywords: knowledge graphs
graph representation learning
tokenization
link prediction
node classification

Abstract: 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 of 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 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.


Published as a conference paper at ICLR 2022
NODEPIECE: COMPOSITIONAL AND PARAMETER- EFFICIENT REPRESENTATIONS OF LARGE KNOWL- EDGE GRAPHS
Mikhail Galkin, Etienne Denis, Jiapeng Wu and William L. Hamilton
Mila, McGill University
Montreal, Canada
(mi miikhail.. galkin, deniseti, jiapeng. wu, hami Mton] @mi la quebec
ABSTRACT
Conventional representation learning algorithms for knowledge graphs (KG) map each entity to unique embedding vector. Such 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 NL.P, we explore the landscape of more parameter-efficient node embedding strategies. To this end, propose NodePicce, an anchor-based approach to learn a fixed-size entity vocabulary. In NodePiece, vocabulary of subword/sub-ente entity units is construeted from anchor nodes in a graph with known relation types. Given such a fixed-size vocabulary, it is possible bootstrap encoding and embedding for any entity, including those unseen during training. Experiments show that NodePiece performs competitively 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 NodePicce-enabled model outperforms existing shallow models on a large OGB WikiKG 2 graph having ~70x fewer parameters
INTRODUCTION
Representation learning tasks on knowledge graphs (KGs) often require a parameterization of each unique alom in the graph with a vector matrix. Traditionally, in multi-relational KGs such atoms constitute a set of all nodes n E N (entities) and relations (edge types) r E R (Nickel let al. (2016). Assuming parameterization with vectors, atoms are mapped d-dimensional vectors through shallow encoders fu n + Rd and fr r - Fd which scale linearly to the number of nodes and edge types) i.c. having ([LV) space complexity of the entity embedding matrix. Albeit efficient on small conventional benchmarking datasets based on Freebase (Toutanova & Chen 2015) (-15K nodes) and WordNet (Dettmers et al.) 2018) (-40K nodes), training on larger graphs (e.g.. YAGO 3-10 (Mahdisoltani et al. 2015) of 120K nodes) becomes computationally challenging. Scaling it further up to larger subsets Hu et al. 2020; Wang et al. 2021 Safavi & Koutra 2020) of Wikidata (Vrandecic& & Krötzsch, 2014) requires top-level GPU CPU cluster as done in, e.g., WyTorch-Bigrrap (Lerer et al. 2019) that maintains a 78M x 200d embeddings matrix in memory (we list sizes of current best performing models in Table
Taking the perspective from NLP, shallow node encoding in KGs corresponds to shallow word embedding popularized with word2vec (Mikolov al.) 2013) and GloVe (Pennington et al. 2014) that learned a vocabulary of 400K most frequent words, treating rarer ones as out-oll (OOV). The OOV issue was resolved with the ability build infinite combinations with a finite vocabulary enabled by subword units. Subword- -poeerdd algorithms such as fastText (Bojanowski
2017). Byte-Pair Encoding (Sennrich et al., 2016), and WordPiece (Schuster & Nakajima 2012) became standard step in preprocessing pipelines of large language models and allowed to
construct fixed-size token vocabularies, e.g., BERT (Devlin al. 2019) contains ~30K tokens and
'The code is available on GitHub: https: / / thub. com/mi ga 1a1k k / NodePiece We then concentrate nodes usually their size orders of magnitude larger than that of edge types.

---

Published as a conference paper at ICLR 2022
Table Node embedding sizes of state-of-the-art KG embedding models compared to BERT Large.
Parameters of type float32 take 4 bytes each. FB15k-237, WN18RR, and YAGO3-10 10 models as reported in Sun et al. (2019), OGB WikiKG2 as in Zhang et al. (2020c), Wikidata 5M as in Wang
et al. (0211) PBG Wikidata in Lerer et al. (2019). and BERT Large as in Devlin et al. (0019)
FB15k-237
WNI8RR
YAGO3-10
OGB WikiKG2
Wikidata 5M
PBG Wikidata
BERT Large
Vocabulary size
15k
40k
120k
2.5M
5M
78M
30k
Emhedding dim
2000
1000
1000
200
512
200
1024
GPU RAM, GB
0.12
0.15
0.46
1.87
9.69
58.1
0.12
GPT-2 (Radford et al. 2019) employs ~50K tokens. Importantly, relatively small input embedding matrices enabled investing the parameters budget into more efficient encoders (Kaplan al. (020)
Drawing inspiration from subword embeddings in NLP, we explore how similar strategies for tokeniz- ing entities in large graphs can dramatically reduce parameter complexity, increase generalization, and naturally represent new unseen entities as using the same fixed vocabulary. To do so, tokenization has to rely on atoms akin to subword units and not the total set of nodes.
To this end, we propose NodePiece, an anchor-based approach to learn a fixed-size vocabulary V (VV) < [ of any connected multi-relational graph. In NodePiece, the set of atoms consists of anchors and all relation types that, together, allow to construct combinatorial number of sequences from limited atoms vocabulary. In contrast to shallow approaches, each node n is first tokenized into a unique hash(n) (n) of k closest anchors and m immediate relations. A key element to build node embedding is a proper encoder function enc(n): : hash(n) + Rd which can be designed leveraging inductive biases of an underlying graph or downstream tasks. Therefore, the overall parameter budget is now defined by a small fixed-size vocabulary of atoms and the complexity of the encoder function.
Our experimental findings suggest that fixed-size NodePiece vocabulary paired with simple en- coder still yields competitive results on a variety of tasks including link prediction, node classification, and relation prediction. Furthermore, anchor-based hashing enables conventional embedding models to work in the inductive and out-of-samppl scenarios when unseen entities arrive at inference time, which otherwise required tailored learning mechanisms.
2 RELATED WORK
Conventional KG embedding approaches. To the best of our knowledge, all contemporary em- bedding algorithms (ii et al., 2020 Ali et al.) 2020) for link prediction on KGs employ shallow embedding lookups mapping each entity to a unique embedding vector thus being linear O( to the total number of nodes |N| and size of embedding matrix. This holds for different em-
bedding families, e.g., translational (Sun et al., 2219). tensor factorization (Lacroix et al.) 2018).
convolutional (Dettmers al. 2018). and hyperbolic (Chami et al. 2020 Balazevic al. 2019
The same applies to relation- aware graph neural network (GNN) encoders (Schlichtkrull et al. 2018
Vashishth al. 2020) who still initialize each node with a learned embedding or feature vector before message passing. Furthermore, shallow encoding is also used in higher-order KG structures such as hypergraphs (Fatemi al. 2020) and hyper-relations graphs (Rosso et al.. 2020 Galkin et al.) 2020). NodePiece can be used as a drop-in replacement of the embedding lookup with any of those models.
Distillation and compression. Several recent techniques for reducing memory footprint of embed- ding matrices follow successful applications of distilling large language models in NI.P (Sanh et al. 2019) i.e., distillation (Wang al., 2020 Zhu et al. (022)) into tow-dimensional counterparts, and compression of trained matrices into discrete codes (Sachan 2020). However, all of them require full embedding matrix as input which we aim to avoid designing NodePiece.
Vocabulary reduction in recommender systems. Commonly, recommender systems operate on thousands of categorical features combined in sparse high-dimensional Sectors.Recent ap- proaches (Medini et al. 2021: Liang et al.] (021) employ inchor-based hashing techniques to factorize sparse feature vectors into dense embeddings. Contrary to those setups, we do not expect availability of feature vectors for arbitrary KGs and rather learn vocabulary embeddings from scratch.
2

---

Published as a conference paper at ICLR 2022
Target
Encoder
11
Inv
r3 Inv
17
r3 Inv
r1
Closest anchors
Relational context
Target node
Anchor distances
Figure 1: NodePiece tokenization strategy. Given three anchors d1 02, ag target node can be tokenized into a hash of top-k closest anchors, their distances to the target node, and the relational context of outgoing relations from the target node. This hash sequence is passed through injective encoder to obtain a unique embedding, Inverse relations are added to ensure connectivity.
Entity descriptions and language models. A recent line of work such as KG-BERT (Yao et al. 2019), MLMLM (Clouâtre et al. (022I, BLP (Daza et al.) 202T) utilize entity descriptions passed through language model (LM) encoder as entity embeddings suitable for link prediction. We would like to emphasize that such approaches are rather orthogonal to NodePiece. Textual features are mostly available in Wikipedia-derive
KGs like Wikidata but are often missing graphs like social networks and product graphs. We therefore assume textual features are not available and rather learn node representations based on their spatial characteristics. Still, textual features can features with LM-produced features.
commin--ppeiffi
be easily added by concatenating
Out-of-sample representation learning. This task focuses on predictions involving previously unseen, out-of-xample, entities that attach to a known KG with few edges. These new edges are then utilized as context to compute its embedding. Previous work (Wang et al. 2019 Hamaguchi et al. 2017: Albooyeh et al.) 2020) proposed different neighborhood aggregation functions for this process or resorted to meta-learning (Chen et al., [2199] Back et al.) 2020) Zhang et al., 2020a). However, all of them follow the shallow embedding paradigm. Instead, NodePiece uses the new edges as a basis for sachor-based, tokenization of new nodes in terms of an existing vocabulary.
NODEPIECE VOCABULARY CONSTRUCTION
Given a directed KG G (N, E, R) consisting of |NN] nodes, EE] edges, and |R] relation types, our task is to reduce the original vocabulary size of |N] nodes to smaller, fixed-size vocabulary of node pieces akin to subword uniss. In this work, we represent node pieces through anchor nodes A, A N, pre-selected set of nodes in graph following deterministic or stochastic strategy. A full NodePiece vocabulary is then constructed from anchor nodes and relation types, i.c,
V A R. Note that in order to maintain reachability of each node and balance in- and out-degrees we enrich G with inverse edges with inverse relation types, such that |R inverse = R direct and [R] direct + [R] inverse Using elements of the constructed vocabulary each node can be tokenized into hash(n) as sequence of & closest anchors, discrete anchor distances, and a relational context of immediate relations. Then, any encoder function enc(n) hash(n) Rd can be applied to embed the hash into d- d-dimensional vector. An intuition of the approach is presented in Fig. I with each step explained more detail below.
3.1 ANCHOR SELECTION
Subword tokenization algorithms such as BPE (Sennrich et al. 2016) employ deterministic strategies to create tokens and construct a vocabulary, e.g., based on frequencies of co-occurring n g-grams, such that more frequent words are tokenized with fewer subword units. On graphs. such strategies might employ centrality measures like degree centrality or Personalized PageRank (Page et al. 1999). However, in preliminary experiments, found random anchor selection to be effective as
3

---

Published as a conference paper at ICLR 2022
centrality- based strategies. A choice for deterministic strategies might be justified when optimizing for certain task-specific topological characteristics. e.g.. degree and PPR strategies indeed skew the distribution of shortest anchor distances towards smaller values thus increasing chances to find anchors in 2- or 3-hop neighborhood of any node (we provide more evidence for that in Appendix C).
3.2 NODE TOKENIZATION
Once the vocabulary V = A + R is constructed, each node can be hashed (or tokenized) into hash(n) using 1) k nearest anchors and their discrete distances; 2) m immediate outgoing relations from the relational context of n. Since anchor nodes are concrete nodes in G, they get hashed in the same way as other non-anchor nodes.
Anchors per node. Given |A| anchor nodes, it impractical use all of them for encoding each node. Instead, we select k anchors per node and describe two possible strategies for that, i.e., random and deterministic. The basic random strategy uniformly samples an unordered set of A: anchors from A yielding (1x) possible combinations. To avoid collisions when hashing the nodes, |.|| and & are to be chosen according the lower bound on possible combinations that is defined by the total number of nodes, e.g., (lAl) 2 M Note that running depth-first search (DFS) to random anchors inference time is inefficient and, therefore, hash(n) of the random strategy has to be pre-computed.
On the other hand, the deterministic strategy selects an ordered sequence of & nearest anchors. Hence, the anchors can be obtained via breadth-first search (BFS) in the I-hop neighborhood of n at inference time (or pre-computed for speed reasons). However, the combinatorial bound not applicable in this strategy and we need more discriminative signals to avoid hash collisions since nearby nodes will have similar anchors (we elaborate on the uniqueness issue in Appendix K). Such signals have better ground anchors to the underlying graph structure, and we accomplish that using anchor distances and relational context described below.
node residing in a disconnected component is assigned with an auxiliary IDISCONNECTED token or can be turned into an anchor. However, the majority of existing KGs are graphs with one large connected component with very few disconnected nodes, such that this effect is negligible.
Anchor Distances. Given target node n and an anchor a,, we define anchor distance 2a, [0; diameter(G)) as an integer denoting the shortest path distance between a, and n in the original graph G. Note that when tokenizing anchor among top-k is always 0j itself with distance We then map each integer to a learnable d-dimensional vector fa Za. + Rd akin relative distance encoding scheme.
anchor aj with the deterministic strategy, the nearest.
Relational Context. We also leverage the multi-relational nature of an underlying KG. Commonly the amount of unique edge types in orders magnitude smaller than the total number of nodes, i.e., [R] < |N| This fact allows to include the entire R in the NodePiece vocabulary Vnp and further featurize each node with a unique relational context. We construct a relational context of a node by randomly sampling set of m immediate unique outgoing relations starting from i.c., rcon, = fr, 1m S (n) where (n) denotes all outgoing relation types. Due to a non-uniform degree distribution, if (n)) m, add auxiliary [PAD] tokens to complete reon, size m.
[T]
3.3 ENCODING
At this step, a node n is tokenized into a sequence of k anchors, their k respective distances, and relational context of size m:
hash(n) = [a.33 (2a. 3+, {ry}"]]
(1)
Taking anchors vectors an and relation vectors rn from the learnable NodePiece vocabulary V E R xd and anchor distances Za, from Z E ((diimmtte(())+))) we obtain a vectorized hash:
hash(n) (1) An Za I'n ā
I' E R (k+
AA full relational path can mined as well but has proven to not scalable as each path needs to be encoded separately through a sequence encoder, e.g., GRU.
"s of 2021, one of the largest open KGs Wikidata contains about 100M nodes and 6K edge types
4

---

Published as a conference paper at ICLR 2022
Although other operations certainly possible, in this work, anchor distances positional encodings of corresponding anchors and sum up their representations that helps to maintain the overall hash dimension of (k m) d.
Finally, encoder function enc [R - R is applied to the vectorized hash to bootstrap an embedding of n. In our experiments, we probe two basic encoders: 1) MLP that takes as input a concatenated hash vector R Rl projecting it down to R2; 2) Transformer encoder (Vaswani al. 2017) with average pooling that takes as input an original sequence [[ While MLP is faster and better scales to graphs with more edges, Transformer is slower but requires less trainable parameters. As the two encoders were chosen to illustrate the general applicability of the whole approach, we leave study of even more efficient and effective encoders for future work.
While the nearest-neighhor hashing function has a greater number of collisions, its non-arbitrary mapping means that it is effectively permutation invariant. We show this in Proposition througgh the framework of Janossy pooling and permutation sampling based SGD, T-SGD (Murphy et al. 2019). A proof is provided in Appendix H
Proposition 1. The nearest- -nneesrrttrrrrrroe encoder with (1 anchors and (m) subsampled relations, can be considered a x-SGD approximation of (k mml)-ary Janossy pooling with canonical ordering induced by the anchor distances.
Janossy pooling with x-SGD can be used to learn permutation-invarian function from a broad class of permutation-sensitvy functions such as MLPs (Murphy et al. 2019). The permutation-invant nature of the nearest-neighbor encoding scheme combined with the lack of transductive features such as node-specific embeddings mean that NodePiece can be used for inductive learning tasks as well.
With fixed-size vocabulary VNP. the overall complexity and parameter budget of downstream models are largely defined by the complexity of the encoder and its inductive biases. By design, the NodePiece smaller vocabulary larger encoder framework is similar to various Transformer-basee language models (Qiu et al., 2020) whose vocabulary size remains rather stable with the encoder being the most important part responsible for the final performance.
4 EXPERIMENTS
We design the experimental program not seeking to outperform the best existing approaches but to show the versatility of NodePiece on a variety of KG-related tasks: transductive, inductive, out-of- sample link prediction, and node classification (with relation prediction results in Appendix []. With this desiderata, we formulate the following research questions: RQ 1) Is it necessary to map each node to unique vector for acceptable performance KG tasks?: RQ 2) What is the effect of hashing features?; RQ 3) Is there an optimal number of anchors per node, after which diminishing returns hit the performance?
4.1 TRANSDUCTIVE LINK PREDICTION
Setup. We run experiments on five KGs of different sizes (Appendix A.1 varying the total number of nodes from -15K to -2.5M. As a baseline, we compare RotatE Sun al., 2019) that remains one of ttatc-of-the-art shallow embedding models for transductive link prediction tasks. To balance with NodePiece, RotatE operates on a graph with added inverse edges as well. We report MRR with Hits@ 10 in the filtered (Bordes et al., 2013) setting as evaluation metrics, and count parameters for all models. On larger KGs, we also compare to a smaller RotatE with a similar parameter budget.
In this task, NodePiece is equipped with 2-layer MI. encoder. For a fair comparison, we also adopt the RotatE scoring function as link prediction decoder. As to the NodePiece configuration, we generally keep the number of anchors below 10% of total nodes in respective graphs. We select lk/20 for FB 253-22237 (i.c., total 1000 anchors and 20 anchors per tokenized node) with 15 unique outgoing relations in the relational context; 500/50 with 4 relations for WN18RR; 7k/20 with 6 relations for CoDEx-L; 10k/20 with 5 relations for YAGO 3-10. Other hyperparameters are listed in Appendix [
Discussion. Generally, the results suggest that fixed-size NodePiece vocabulary of <10% of nodes sustains 80-90% of Hits@ 10 compared to 10x larger best shallow models. Some performance loss is expected due to the compositional and compressive nature of entity tokenization. On smaller graphs
5

---

Published as a conference paper at ICLR 2022
Table 2: Transductive link prediction on smaller KGs. i results taken from (Sun al. 2019). denotes vocabulary size (anchors + relations), #P is a total parameter count (millions). % denotes the Hits 10 ratio based on the strongest model.
[
FB 15k-237
WNISRR
[
#P (M)
MRR
H@ 10
%
[V]
#P (M)
MRR
H@ 10
%
RotatE NodePiece RotatE
15k + 0.5k
29
0.3381
0.533
100
40k + 22
41
0.476
0.571
100
1k 0.5k
3.2
0.256
0.420
79
500
22
4.4
0.403
0.515
90
no rel. context
Ik 0.5k
2
0.258
0.425
80
500 + 22
4.2
0.266
0.465
81
no distances
Ik + 0.5k
3.2
0.254
0.421
79
500 + 22
4.4
0.391
0.510
89
no anchors, rels only
0 0.5k
1.4
0.204
0.355
67
0 22
0.3
0.011
0.019
0.3
Table 3: Transductive link prediction on bigger KGs. The same denotation as in Table 2 Second RotatE has a similar parameter budget as NodePiece-basee model.
CoDEx-L
YAGO 3-10
[V
#P (M)
MRR
H@ 10
%
[V]
#P (M)
MRR
H@ 10
%
RotatE (500d)
77k 138
0.258
0.387
100
123k + 74
123
0.4951
0.670
100
RotatE (20d) NodePiece RotatE
77k 138
3.8
0.196
0.322
83
123k + 74
4.8
0.121
0.262
39
7k 138
3.6
0.190
0,313
81
10k 74
4.1
0.247
0.488
73
no rel. context
7 1338
3.1
0.201
0.332
86
10k 74
3.7
0.249
0.482
72
no distances
7k + 138
3.6
0.179
0.302
78
10k + 74
4.1
0,250
0.491
73
no anchors, rels only
0+ 138
0.6
0.063
0.121
31
0 + 74
0.5
0.025
0.041
(Table 2 parameter saving might not be well pronounced due to the overall small number of nodes to embed. Still, taking even few as 500 nodes anchors performance. On bigger graphs (Table parameter efficiency is more pronounced, i.e., on YAGO 3-10, RotatE model of comparable size 20 Hits @ 10 points worse than NodePiece-basee one. This observation can be attributed to the fact the shrinking shallow models results in shrinking the embedding dimension of each node (20d for RotatE) which is inefficient on small parameter budgets. In contrast, small fixed-size vocabulary allows for larger anchor embedding dimensions (100d for NodePiece with RotatE) since most of the parameter budget defined by the encoder.
retains 90% of the best model
We further study the effect of different anchor selection combinations (Fig. D) On WN18RR, fewer anchors with fewer anchors per node (lAA//)) yield relatively low accuracy but starting from 50/20 (-0.1% of 40k nodes in the graph) the Hits 10 performance starts to saturate. On FB15k 1355--377, as few as 25 anchors already exhibit the signs of saturation where a further increase to 500 or 1000 anchors only marginally improves the performance. We hypothesize such a difference can be explained by graph density, e.g., WN18RR is a sparse graph with a diameter of 23 and average anchor distance of 6 hops; while FB15k 237 is denser graph with an average anchor distance of 2-3. Hence, sparse graph with longer distances, it takes more anchors to properly encode a node.
A However, more precise predictions (e.g., Hits@ 1) reflected in the MRR metric (see Appendix F still remain a challenging task for small vocabulary NodePiece setups, and bigger Al/k combinations alleviate this issue. We also observe that diminishing returns, which make further vocabulary increase less rewarding, start to appear from anchor set sizes of -1% of total nodes.
Ablations. In the ablation study, measure the impact of relational context and anchor distances on link prediction (Table 2) Removing relational context and anchor distances does not tangibly affect the denser 151kk231 data but does impair the accuracy on the sparser WNISRR. Pushing vocabulary sizes to the limit, we also investigate NodePiece behavior in the absence of anchors at all, ie., when hashes are defined only by the relational context of size m. Interestingly, this still yields fair performance on FB15k-237 with just 7 points Hits @ 10 drop, but drops to zero the WN1 18RR performance. The fact that node embeddings might not be at all necessary but relations are more important supports the recent findings of Teru et al. (2020) that relies only on relations seen in small subgraph around a target node. However, at this point, seems to be a virtue of graphs with a diverse set of unique relations. That is, FB 135 has 20x more unique relations than WN18RR and resulting hashes have more diverse combinations of relations which lead to more discriminative node representations. Additionally, visualize anchor embedding projections in Appendix D

---

Published as a conference paper at ICLR 2022
WONTOOO
11116-297
0.6
A62a
A-00
0.42
A-500
A:1000
0.88
0.4
0.28
01
233
341
40
30
1001
10
20
Auadhans taad
Anchers mode
Figure 2: Combinations of total anchors A and anchors per node. Denser FB 15k--2237 saturates faster on smaller A while sparse WN18RR saturates at around 500 anchors.
4.1.1 OGB WIKIKG 2
To measure the benefits of NodePiece on large-scale KGs, we a link prediction experiment OGB WikiKG (Hu et al. 2020), a subset of Wikidata that consists of 2.5M nodes and
Table 4: Test MRR and parameter budget on OGB WikiKG
16M edges. NodePiece is configured sample vocabulary 20K anchor nodes << 1% of total nodes) where each node represented with
Model
#Params
MRR
20 nearest anchors and relational context of size m = 12, and we use 2-layer MLP as a hash encoder (other hyperparameters as in Appendix A). Gener- ally, such NodePiece configuration can be paired with any link prediction decoder and we chose a non-parametric Au-
NP + AutoSF
6.9M
0.570 20.003
rel. context
5.9M
0,592 1.0003
anc. dists
6.9M
0.570 =0.004
anchors
1.3M
0.476
AutoSF
500M
0.546 =0.005
toSF (Zhang et al. 2020b) as one of the strongest decoders on this graph. Overall, the NodePiece + AutoSF model has only 6.9M parameters, about 70x smaller than top shallow models. Compared to the best reported shallow approaches.
PairRE
500M
0.521
RotatE
1250M
0.433 10,002
TransE
1250M
0.426 100003
the IndePiece-enables model exhibits (ef. Table 4 averaged 10 seeds) better performance achieved with a orders of magnitude smaller parameter budget. We believe this result shows the effectiveness of NodePiece on large KGs with a dramatic parameter size reduction without significant performance losses. Ablations report the duality of a relational context, i.e., removing it from hashes leads to even higher MRR scores. On the other hand, the relational context alone with learnable anchors still yields considerably better results than x000 larger shallow models RotatE and TransE.
4.2 INDUCTIVE LINK PREDICTION
We conduct a set of experiments on the inductive link prediction benchmark introduced by Teru et al.) (200)) to measure the performance of NodePiece features the extreme case when anchor nodes not available and only relational context can be used to compose entity representations.
Setup. The unique feature of this benchmark compared other evaluated tasks is that training and inference graphs are disjoint, i.c.. inference at validation and test time is performed on a completely new graph comprised of new entities, and link prediction involves only entities unseen during training. As inference graphs are disconnected from training ones, learning anchors from the training graph is useless, so node hashes are built only using the m-sized relational context. On top of the obtained NodePiece features we then employ relational message passing GNN, CompGCN (Vashishth et al., 2020), with RotatE (Sun et al., 2019) as a scoring function for triples. More details on the setup and best hyperparameters for NodePiece are presented in Appendix [
Baselines. We compare NodePiece CompGCN with two families of models applicable in the inductive setting, i.c.. rule-based methods, Neural LP (Yang et al., 2017). DRUM (Sadeghian et al.) 2019), RuleN (Meilicke et al. 2018), and GNNs: GralL (Teru et al. 2020 and recently proposed Neural Bellman-Ford Nets (NBFNet) (Zhu et al. 2021).
Generally, the results confirm the trend identified previously: relation-only features strong performers in dense relation-rich graphs. NodePiece features paired with CompGCN significantly improve over path-basce methods where performance gap might reach 37 absolute Hits @ 10 points, e-g., in FB15k-237 V1 and NELL-995 V1. Comparing to GNNs, NodePiece
Discussion.
7

---

Published as a conference paper at ICLR 2022
Table 5: Inductive link prediction results, Hits@@ 10.
Best results are in bold, second best are
underlined. i results taken from Teru et al.
2020
NBFNet results taken from Zhu et al. 2021
233
WNISRR
NELL-995
Class
Method
V1
V2
V3
V4
VI
V2
V3
V4
V1
V2
V3
V4
Neural LP
0.529
0,589
0.529
0.559
0.744
0.689
0.462
0.671
0.408
0.787
0.827
0.806
Path
DRUM F
0,529
0.587
0.529
0,559
0.744
0.689
0.462
0.671
0.194
0.786
0.827
0.806
RuleN
0.498
0.778
0.877
0.856
0.809
0.782
0.534
0.716
0.535
0.818
0.773
0.614
Grall, 7
0.642
0.818
0.828
0.893
0.825
0.787
0.584
0.734
0.595
0.933
0.914
0.732
GNN
NBFNet
0.834
0.949
0.951
0.960
0.948
0.905
0.893
0.890
NP + CompGCN
0.873
0.939
0.944
0.949
0.830
0.886
0.785
0.807
0.890
0.901
0.936
0.893
Table 6: Node classification results. parameter count (millions).
[V] denotes vocabulary size (anchors + relations), #P is a total
WDS0K (5% labeled)
WDS0K (10% laheled)
VI
#P (M)
ROC-AUC
PRC-AUC
Hard Ace
ROC-AUC
PRC-AUC
Hard Acc
MLP CompGCN
46k + Ik
4.1
0,503
0.016
0.001
0,510
0.017
0.002
46k + Ik
4.4
0.836
0.280
0.176
0.834
0.265
0.161
NodePiece GNN
50 + 1k
0.75
0.981
0.443
0.513
0,981
0,450
0.516
no rel. context
50+ 1k
0.64
0.982
0.446
0,534
0.982
0.449
0.530
no distances
50 1k
0.74
0.981
0.448
0.516
0,981
0.448
0.513
anchors, rels only
0+
0.54
0.984
0.453
0.532
0.984
0.456
0.533
CompGCN outperforms GralL by a large margin in all (except one) experiments and is competitive to NBFNet on relation-rich FB15k-237 splits. As expected, NodePiece features less efficient on sparse graphs (like WN18RR with few unique relations) but still outperform ropology-based Grall..
4.3 NODE CLASSIFICATION
Setup. Due the lack of established node classification datasets on a multi-class multi-label task based on triple version of recent WD50K (Galkin et al., (020) extracted from Wikidata. The pre-processing steps are described Appendix [F] and the final graph consists of 46K nodes and 222K edges. The task belongs to the family of transductive (the whole graph seen during training) semi-supervised (only a fraction of nodes are labeled) problems, where labels are 465 classes seen in Wikidata. In semi-supervised mode, test the models graph with 5% and 10% of labeled nodes. Node features have to be learned as node embeddings.
KGs, we design
As baselines, we compare to a 2-layer MLP and CompGCN (Vashishth et al. 2020) in full-batch mode which is one of the strongest GNN encoders for muult-relationn. KGs. Both baselines learn a full entity vocabulary. We report ROC-AUC, PRC-AUC, and Hard Accuracy metrics commonly done in standard graph benchmarks like OGB (Hu et al. (020). For PRC-AUC and Hard Accuracy, binarzze predicted logits using a threshold of 0.5. Hard Accuracy corresponds the exact match of predicted sparse -65-dimensional vector to a sparse 465-dimensional labels vector.
NodePiece is configured to have only 50 anchors and use 10 nearest anchors per node with 5 unique relations in the relational context. The dimensionality of anchors and relations is the same as in the baseline CompGCN. Each epoch, we first materialize all entity embeddings through the NodePiece encoder and then send the materialized matrix to CompGCN with the class predictor.
Discussion. Surprisingly, -1000x vocabulary reduction ratio (50 anchors against 46k for shallow models) greatly outperforms the baselines (Table 6). MLP, as expected, is not able to cope with the task producing random predictions. CompGiNN, in turn, outperforms ML. demonstrating non- random outputs as seen by the ROC-AUC score of 0.836 and higher PRC-AUC and Hard Accuracy metrics. Still, a NodePiece-equipped CompGCN with 50 anchors reaches even higher ROC-AUC of 0.98 with considerable improvements along other metrics, i.e., 19 PRC-AUC points and 3x boost along the hardest accuracy metric. We attribute such noticeable performance difference to better generalization capabilities of the NodePiece model. That is, generalization gap between training and validation metrics of the NodePiece + CompGCN is much smaller compared to the basclines who overfit rather heavily cf. the training curves in the Appendix G). The effect remains after increasing
8

---

Published as a conference paper at ICLR 2022
Table 7: Out-of-sample link prediction. results are taken from (Albooyeh et al.
2020 |V|
denotes
vocabulary size (anchors + relations), #P is total parameter count (millions).
0FB15k-237
oYAGO 3-10 (117k)
[V]
(M)
MRR
11@
V
(M)
MRR
11@
aDistull-ERAAgg
11k + 0.5k
2.4
0.256t
0.420f
100
117k + 74
23.4
0OM
0OM
NodePiece + DistMult
1k + 0.5k
1
0.206
0.372
88
10k 74
2.7
0.133
0.261
100
no rel. context
1k 0.5k
0.173
0.329
10k 74
2.7
0.125
0.245
94
no distances
1k 0.5k
1
0.208
0.372
74
2.7
0.133
0.260
99
anchors, rels only
0 0.5k
0.8
0.069
0.127
0++ 74
0.7
0.015
0.017
the number of labeled nodes to 10%. Even with 50 anchors, the overall performance is saturated as the further increase of the vocabulary size did not bring any improvements.
Ablations. We probe setups where NodePiece hashes use only anchors or only relational context, and find they both deliver a similar performance. Following the previous experiments on dense graphs with lots of unique relations. appears that node classification can be performed rather accurately based only on the node relational context which is captured by NodePiece hashes.
4.4 OUT-OF-SAMPLLY LINK PREDICTION
Setup. In the out-of-sample setup, validation and test splits contain unseen entities that arrive with few edges connected the seen nodes. For this experiment, we use the nut-of-sample FB15k- 237 split (oFB 15k-237) as designed in in/Alboyyeh et al. (2020). We do not employ their version of WN18RR as the split contains too many disconnected entities and components the train graph. Instead, using the authors script, we sample a much bigger out-of-sample version of YAGO 3-10.
As a baseline, we compare to oDistMult (Albooyeh et al. 2020) which aggregates embeddings of all seen neighboring nodes around the unseen one (akin to I-layer message passing with mean aggregator). We adopt the same evaluation protocol given an unseen node with its connecting edges, we mask one of the edges and predict its tail or head using the rest of the edges, repeating this procedure for each edge. We report filtered MRR and Hits 10 as main metrics.
NodePiece enables traditional transductive- models to perform inductive inference as both seen and unseen nodes are tokenized using the same vocabulary. For a smaller oFB 15k-237 the NodePiece 10k/20
vocabulary has 1k/20 configuration with 15 relations, while in bigger o YAGO 3-10 with relations. For this task, we apply a transformer encoder instead of MLP. For a fair comparison, we use DistMult as scoring function as well.
The results in Table show that a simple NodePiece-based model retains ~90% of the baseline performance oFB15k-237, but achieved faster and computationally inexpensive compared to oDistMult. Moreover, while oDistMult is tailored specifically for the out-of-sampll task, we did not do any task-specific modifications to the NodePiece-enabled model as it is inductive by design. Furthermore, oDistMult is not able to scale to bigger oYAGO 3-10 on a 256 GB RAM machine due to the out of memory crash. Conversely, NodePiece NodePiece-equippedd model has the same computational requirements as in other tasks and converges rather quickly (40 epochs). Performed ablations underline the importance of having both anchors and relational context for tokenizing unseen entities. We elaborate more on possible inference strategies for transductive and inductive tasks in Appendix(A.o
Discussion.
5 CONCLUSION
In this paper, we have introduced NodePiece, compositional approach for representing nodes in multi-relational graphs with a fixed-size vocabulary. Similar to subword units, NodePiece allows to tokenize every node combination of anchors and relations where the number of anchors can be 10-100x smaller than the total number of nodes. We show that in some tasks, node embeddings are not even necessary for getting acceptable accuracy thanks to rich set of relation types. Moreover, NodePiece inductive by design and is able to tokenize unseen entities and perform downstream prediction tasks in the same fashion
ones.

---

Published as a conference paper at ICLR 2022
Reproducibility Statement. The source code is openly available GitHub. All hyperparameters and implementation details are presented in Appendix [A] Information on the used datasets is presented in Table 8 and we provide more details dataset construction for node classification and out-of- sample link prediction tasks in Appendix F The proof for Proposition 1 is given the Appendix H
Ethics Statement. As NodePiece is general graph representation learning method, we do not foresee immediate ethical consequences pertaining to the method itself.
Acknowledgements. The authors would like to thank Koustuv Sinha, Gaurav Maheshwari, and Priyansh Trivedi for insightful and valuable discussions at earlier stages of this work. We also thank anonymous reviewers for the helpful comments. This work is partially supported by the Canada CIFAR AI Chair Program and Samsung Al grant (held at Mila). We thank Mila and Compute Canada for access to computational resources.
REFERENCES
Marjan Albooyeh, Rishab Goel, and Seyed Mehran Kazemi. Out-of-sample representation learning for knowledge graphs. In Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 2657-2666, Online, November 2020, Association for Computational Linguistics. doi: 10.18653/v w..186553/1/22200.. 1/22000..ininngseemllp.. 2020. fi wwwdiiinnsnnnlll.......
URL https: h/tp:::/wwww... ac awwweb. org/ anthology/
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 a unified framework. CoRR, abs/2006. 13365, 2020.
Mehdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Sahand Sharifzadeh, Volker Tresp, and Jens Lehmann. PyKEEN 1.0: A Python Library for Training and Evaluating Knowledge Graph Embeddings. Journal of Machine Learning Reseurch, 22(82):1-6, 2021. URL http
820000882..0 html
Jinheon Back, Dong Bok Lee, and Sung Ju Hwang. Learning to extrapolate knowledge: Transductive few-shot out-of-graph link prediction. Advances in Neural Information Processing Systems, 33, 2020.
Ivana Balazevic, Carl Allen, and Timothy M. Hospedales. Multi-relational poincaré graph em- beddings. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bue, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver. BC, Canada, pp. 4465 4475, 2019.
Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. Enriching word vectors with subword information. Transactions of the Association for Computational Linguistics, 5:135- 146, 2017. doi: 10.1 162/tacl 000551 017-1010
URL https: www. aclweb.ww.e... wwwp:/eb..rrr.eooo...... anthology/
Antoine Bordes, Nicolas Usunier, Alberto Gareía-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 2787-2795 2013.
Ines Chami, Adva Wolf. Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low- dimensional hyperbolic knowledge graph embeddings. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACI. 2020, Online, July 5-10, 2020, pp. 6901-6914, Association for Computational Linguistics, 2020.
Mingyang Chen, Wen Zhang, Wei Zhang, Qiang Chen, and Huajun Chen. Meta relational learning for fho-shot link prediction in knowledge graphs. In Proceedings of the 2019 Conference on
10

---

Published as a conference paper at ICLR 2022
Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 4208 4217,, 2019.
Louis Clouâtre, Philippe Trempe, Amal Zouaq. and Sarath Chandar. MLMLM: link prediction with mean likelihood masked language model. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Findings of the Association for Compustaional Linguistics: ACL/IJCNPP 2021, Online Event, August 1-6, 2021, volume ACL/IICNLP 2021 of Findings of ACL, pp. 4321 -331..
Association for Computational Linguistics, 2021.
Daniel Daza, Michael Cochez, and Paul Groth. Inductive entity representations from text via link prediction. Jure Leskovec, Marko Grobelnik, Mare Najork, Jie Tang. and Leila Zia (eds.), WWW 21: The Web Conference 2021, Virtual Event L.jubljana, Slovenia, April 19.23, 202/, pp. 798 -08.
ACM / IW3C2, 2021.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 1811-1815 AAAI Press, 2018
Jacob Devlin, Ming-War Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.). Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACI-HLLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume I (Long and Short Papers), pp. 4171-4188 Association for Computational Linguistics, 2019.
Bahare Fatemi, Perouz Taslakian, David Vázquez, and David Poole. Knowledge hypergraphs: Prediction beyond binary relations. In Christian Bessiere (ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pp. 2191-2197. ijeai.org, 2020.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Mikhail Galkin, Priyansh Trivedi, Gaurav Maheshwari, Ricardo Usbeck, and Jens Lehmann. Mes- sage passing for hyper-relational knowledge graphs. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7346-7359. Association for Computational Linguistics, 2020.
Takuo Hamaguchi, Hidekazu Oiwa, Masashi Shimbo, and Yuji Matsumoto. Knowledge transfer for sal--of-koowledee-baae entities A graph neural network approach. In Carles Sierra (ed.), Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pp. 1802-1808. ijcai.org, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, MariiaFlorina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020
Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and Philip S. Yu. A survey on knowledge graphs: Representation, acquisition and applications. CoRR, abs/2002.00388, 2020.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.088 003661 2020.
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmásssan Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 2869 2878. PMLR, 2018
11

---

Published as a conference paper at ICLR 2022
Adam Lerer, Ledell Wu, Jiajun Shen, Timothee Lacroix, Luca Wehrstedt, Abhijit Bose, and Alex Peysakhovich. BarrchBigGraph: A Large-scale Graph Embedding System. In Proceedings of the 2nd SysML Conference, Palo Alto, CA, USA, 2019.
Paul Pu Liang, Manzil Zaheer, Yuan Wang, and Amr Ahmed. Anchor & transform: Learning sparse embeddings for large vocabularies. In International Conference on Learning Representations, 2021. /
net wttt//oormmiidddvV" Vcwcdv CMvtLqg.
Farzaneh Mahdisoltani, Joanna Biega, and Fabian M. Suchanek. YAGO3: knowledge base from multilingual wikipedias, In Seventh Biennial Conference on Innovative Data Systems Research, CIDR 2015, Asilomar, CA, USA, January 4-7, 2015, Online Proceedings. www.cidrdb.org. 2015,
Tharun Medini, Beidi Chen, and Anshumali Shrivastava. (SOLAR): Sparse orthogonal learned and random embeddings. In International Conference on Learning Representations, 2021. URL
htttps://ppeneviiee net/ foorumiidfffi BB1ik-j
Christian Meilicke, Manuel Fink, Yanjie Wang, Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt. Fine-grained evaluation of rule- and embedding- based systems for knowledge graph completion. In The Semantic Web ISWC 2018- 17th International Semantic Web Conference, Monterey, CA, USA, October 8-12, 2018, Proceedings, Part volume 11136 of Lecture Notes in Computer Science, pp. 3-20. Springer, 2018.
Tomás Mikolov, Ilya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality, In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 3111-3119, 2013.
Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pooling: Learning deep permutation-invariie functions for variable-size inputs, 2019.
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proc. IEEE, 104(1):11-3) 2016.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking:
Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, November 1999. Previous number = SIDL- Ww---9---19992229
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. 7achary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 8024 8035, 2019.
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word representation. In Alessandro Moschitti, Bo Pang, and Walter Daelemans (eds.), Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, October 25-29, 2014, Doha, Qatar, A meeting of SIGDAT, a Special Interest Group of the ACL, pp. 1532 1543. ACL, 2014.
Xipeng Qiu, Tianxiang Sun, Yige Xu, Yunfan Shao, Ning Dai, and Xuanjing Huang. Pre-trained models for natural language processing: A survey. Science China Technological Sciences, pp. 1-26, 2020.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners OpenAl blog, 1(8):9, 2019.
Paolo Rosso. Dinggi Yang, and Philippe Kudré-Maurous Beyond triplets: Hyper-relational knowl- edge graph embedding for link prediction. In Proceedings of The Web Conference 2020, pp. 1885-1896, 2020.
12

---

Published as a conference paper at ICLR 2022
Mrinmaya Sachan. Knowledge graph embedding compression. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 2681-2691, Online, July 2020. URL https:
Association for Computational Linguistics. doi: 10. /tt.////////22..a//llllooo
1/www. acw web. org ant wttp ac 1aaacmmma -ma 238
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. DRUM: end-to-end differentiable rule mining on knowledge graphs. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 15331_15331, 2019.
Tara Safavi and Danai Koutra. CoDEx: A Comprehensive Knowledge Graph Completion Benchmark. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 8328-8350, Online, November 2020. Association for Computational Linguistics. doi: 10. 111118//1/22200.mm/l 2020 emn 1p-main-mn in. 669
wtt.:/000.mmmmmmmmia.aa m6in URL https: www. ac awwwwb.wwwb......... org/ httpg//nnhhoog//
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of BERT: smaller, faster, cheaper and lighter. CoRR, abs/1910.01 108, 2019. URL httt:://p///t
or org arg/abs/13m 11900 01108
Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In The Semantic Web 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, Proceedings, volume 10843 of Lecture Notes in Computer Science, pp. 593-607. Springer, 2018.
Mike Schuster and Kaisuke Nakajima. Japanese and korean voice search. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2012, Kyoto, Japan, March 25-30, 2012, pp. 5149-5149551 5152. IEEE, 2012. doi: 10. AAA110//CAASPP22222299990 1ttp://11111119AAA1111. 2012. 6289079
URLhttps:
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Anmual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers), pp. 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.11653/v1/P11-111 1162. URL https: /wwp aclweb
org/antho hts/anttologgy/PPP 1162
Zhiqing Sun, Zhi-Hong Deng, Jian-Yur Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Komal K. Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 9448 9457. PMLR, 2020.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop Continuous Vector Space Models and their Compositionality, pp. 57-66, Beijing, China, July 2015. Association for Computational Linguistics. doi: 1118653/v1/1154494 415-4007
http::/tt://///e ac www.we.bc.o anthr/og/t
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition- multi- relational graph convolutional networks. In International Conference on Learning Representations, 2020. httttttt//pppetiiie
net/ forummicuiicooooo By C4tPr
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Gareett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. $998-6008, 2017.
Denny Vrandecic and Markus Krötzsch. Wikidata: a free collaborative knowledgebase. Commun. ACM, 57(11)778--85 2014.
13

---

Published as a conference paper at ICLR 2022
Kai Wang, Yu Liu, Qian Ma, and Quan Z Sheng. Mulde: Multi-teacher knowledge distillation for low-dimensional knowledge graph embeddings. arXiv preprint arXiv:2010.07152. 2020.
Peifeng Wang, Jialong Han, Chenliang Li, and Rong Pan. Logic attention based neighborhood
aggregation for inductive knowledge graph embedding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 7152-7159, 2019.
Xiaozhi Wang, Tianyu Gao, Zhaocheng Zhu, Zhengyan Zhang, Zhiyuan Liu, Juanzi Li, and Jian Tang. KEPLER: A unified model for knowledge embedding and pre-trained language representation. Trans, Assoc. Comput. Linguistics, 9:176-194, 2021.
Fan Yang. Zhilin Yang, and William W. Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 2319-2328, 2017.
Liang Yao, Chengsheng Mao, and Yuan Luo. KG-BERT: BERT for knowledge graph completion. CoRR, htt/1999.0199, 2019. URL httt:://axxiv.oor/ab///////
03193
Chuxu Zhang, Huaxiu Yao, Chao Huang, Meng Jiang, Zhenhui Li, and Nitesh V Chawla. Few-shot knowledge graph completion. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 3041-3048, 2020a.
Yongqi Zhang, Quamming Yao, Wenyuan Dai, and Lei Chen. Autosf: Searching scoring functions for knowledge graph embedding. In 36th IEEE International Conference Data Engineering, ICDE 2020, Dallas, TX, USA, April 20-24, 2020, pp. 433-444, IEEE, 2020b.
Yongqi Zhang, Quamming Yao, Wenyuan Dai, and Lei Chen. Autosf: knowledge graph embedding. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp. 433 444. IEEF, 2020c.
Searching scoring functions for
Yushan Zhu, Wen Zhang, Hui Chen, Xu Cheng, Wei Zhang, and Huajun Chen. Distile: Distiling knowledge graph embeddings for faster and cheaper reasoning. arXiv preprint arXiv:2009.05912, 2020.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. In Neural Information Processing Systems, NeurIPS, 2021.
14

---

Published as a conference paper at ICLR 2022
A IMPLEMENTATION & HYPERPARAMETERS
Table 8: Dataset statistics. LP- link prediction, RP relation prediction, NC node classification, OOS out-of-sample. In OOS-LP, Nodes also shows the amount of unseen nodes in validation/test.
Datasel
Task
Nodes
Relations
Edges
Trann
Validation
Test
FBI5k-237 (Toutanova & Chen
2015
I.P. RP
14,505
237
310,079
252,
17,526
20,438
WNISRR DDttmees Ale 2018
RP
40,559
92.583
86,835
2824
2924
CoDEx-Large (Satavi & Koulra
2020
LP
77.951
69
612,437
551,193
30,622
30,622
YAGO 3-10 Mtnsossoaaail
2013
RP
123,143
1,089,000
1,079,040
4978
4982
OGB WikiKG
2020
LP
2,500,604
535
17.137,181
16.109.182
429,456
598,543
WDS0K
NC
46,164
526
222,563
4600 (N)
4600 (N)
4600 (N)
aFB15k-237 Albooyeh al. 2020
OOS-LP
115/1395/1395
234
292,173
193,490
44,601
54,082
aYAGO 3-10
00S.IP
1176/26622959
1,086,416
988,124
47,112
51,180
Table 9: Inductive relation prediction dataset statistics. Facts denote the size of the input graph while queries denote the triples to be predicted. Training sets contain all queries as facts. Note that in validation and test we receive new graph disjoint from the training one, and queries are sent against this new inference graph (hence the number of entities and facts for validation and test is the same).
Train Query
Validation Query
Test Query
Dataset
Relations
Entity
Facts
Entity
Fact
Entity
Facts
v1
183
2,000
4,245
4,245
1,500
206
1,993
1,500
205
1,993
203
3,000
9,739
9,739
2,000
469
4,145
2,000
478
4,145
FB15k-237
218
4,000
17,986
17.986
3,000
866
7.406
3,000
865
7,406
222
5,000
27,203
27,203
3,500
1,416
11,714
3,500
1,424
11,714
v1
9
2,746
5,410
5,410
922
185
1,618
922
188
1,618
v2
10
6,954
15,262
15.262
2,923
411
4.011
2,923
441
4,011
WNI8RR
v3
11
12,078
25,901
25,901
5,084
538
6,327
5,084
605
6,327
9
3,861
7,940
7,940
7,208
1,394
12,334
7,208
1,429
12,334
v1
14
3,103
4,687
4,687
225
101
833
225
100
833
v2
88
2,564
8,219
8,219
4,937
459
4,586
4,937
476
4,586
NELL-995
v3
142
4,647
16,393
16,393
4,921
811
8,048
4,921
809
8,048
v4 77
2,092
7,546
7,546
3,294
716
7,073
3,294
731
7,073
NodePiece is implemented in Python using igraph library (licensed under GNU GPL 2) for com- puting centrality measures and perform basic tokenization. Downstream tasks employ NodePiece conjunction with PyTorch (Paszke et al.) 2019) (BSD-style license), PyKEEN (Ali et al., 2021) (MIT License), and PyTorch-Gerr Geometric (Fey & Lenssen, 2019) (MIT License). We ran experiments on machine with one RTX 8000 GPU and 64 GB RAM. The OGB WikiKG experiments were executed on single Tesla V100 16 GB VRAM and 64 GB RAM. All used datasets are available under open licenses.
For all downstream tasks and datasets we employ the deterministic anchor selection strategy where 40% the total number anchors |A| are nodes with top PPR scores, 40% are top degree nodes, and remaining 20% are selected randomly. All anchor sets some top degree nodes have already been selected with the PPR policy, they will be skipped in favor of next nodes in the sorted list. The choice for this strategy is motivated in Appendix
overlapping and disjoint, i.e., if
A.1 DATASETS
Details on the datasets for transductive link prediction, out-of-sample link prediction, relation prediction and node classification are collected in Table 8 The inductive link prediction benchmark introduced by Teru et al. (2020) includes 3 graphs, FB 237, WNISRR, and NELL-995, each has different splits that vary the number of unique relations, number of nodes and triples training and inference time. Full dataset statistics is provided in Table FB15k-237 and most splits NELL-995 can be considered relation-rich graphs while WN18RR sparse graph with few relation types.
15

---

Published as a conference paper at ICLR 2022
A.2 TRANSDUCTIVE LINK PREDICTION
The optimizer is Adam for all experiments. As RotatE is scoring function the complex space, the reported embedding dimensions sum of real and imaginary dimensions, e.g., 1000d means that both real and imaginary vectors are 500d.
Table 10: NodePiece hyperparameters for transductive link prediction experiments
Parameter
FB 153-2233
WN18RR
CoDEx-L
YAGO 3-10
OGB WikiKG 2
# Anchors, |A]
1000
500
7000
10000
20000
# Anchors per node, k
20
50
20
20
20
Relational context,
15
6
5
12
Vocabulary dim, d
200
200
200
200
200
Batch size
512
512
256
512
512
Learning rate
0,0005
0.0005
0.0005
0.00025
0.0001
Epochs
400
600
120
600
300k (steps)
Encoder type
MLP
MLP
MLP
MLP
MLP
Encoder dim
400
400
400
400
400
Encoder layers
2
2
2
2
2
Encoder dropout
0.1
0.1
0.1
0.1
0.1
Loss function
BCE
NSSAL
BCE
NSSAL
NSSAL
Margin
15
50
50
# Negative samples
20
10
128
Label smoothing
0.4
0.3
Training time, hours
7
5.5
26
23
11
Table 11: RotatE hyperparameters for transductive link prediction experiments. CoDEx-L and YAGO
3-10 also list the hyperparameters (after the symbol /) for smaller models (reported in Table 3 of the same parameter budget as NodePiece
Parameter
FB15k-237
WNI8RR
CoDEx-L
YAGO 3-10
Embedding dim,
2000
1000
1000 50
1000 40
Batch size
1024
512
512 512
1024 / 512
Loss function
NSSAL
NSSAL
NSSAL
NSSAL
Margin
6
25 /
24 15
# Negative samples
256
1024
100 / 100
400 100
A.3 RELATION PREDICTION
Configurations (Table 12) for the compared models are almost identical to those of the transductive link prediction experiment. We mostly reduce the number of epochs and negative samples as models converge faster on this task.
A.4 NODE CLASSIFICATION
In this experiment (Table 13) NodePiece is used at the initial step to bootstrap a node embeddings matrix which is then sent the CompGCN graph encoder. In contrast, CompGCN and MLP baselines use directly a trained node embedding matrix as their initial input.
A.5 OUT-OF-SAMPLE LINK PREDICTION
The set of NodePiece hyperparameters (Table 14 is similar to the set of the transductive experiments except the scoring function (DistMult), encoder function (Transformer), and number of epochs the model converges faster. We do not provide a setup for the baseline oDistMult on oYAGO 3-10 as the model was not able to pre-process the dataset on machine with 256 GB RAM. Reported training
16

---

Published as a conference paper at ICLR 2022
Table 12: Hyperparameters for relation prediction experiments. The content is largely identical to
Table 10
only changed parameters are listed
NodePiece RotatE
RotatE
Parameter
155-237
WNISRR
YAGO 3-10
FB15k-237
WNI8RR
YAGO 3-10
Batch size
512
512
512
512
512
512
Epochs
20
150
7
150
150
150
Loss function
NSSAL
NSSAL
NSSAL
NSSAL
NSSAL
NSSAL
Margin
15
12
25
# Negative samples
20
20
20
20
20
20
Training time, min
25
30
25
28
10
57
Table 13: Hyperparameters for node classification experiments
Parameter
NodePiece + CompGCN
CompGCN MLP
Anchors, |
50
# Anchors per node, lo Relational context, m Vocabulary dim, d
10
100
100
100
Batch size
512
512
512
Learning rate
0.001
0.001
0.001
Epochs
4000
4000
4000
NodePiece encoder
MLP
NodePiece encoder dim
200
NodePiece encoder layers
NodePiece encoder dropout
0.1
GNN (MIP) layers
3
GNN (MLP) dropout
0.5
0.5
0.5
Loss function
BCE
BCE
BCE
Label smoothing
0.1
0.1
0.1
Training time, hours
14
22
times for NodePiece models exclude evaluation. Training times of the baseline oDistMult were not reported by its authors.
A.6 DEPLOYMENT IN REAL-WORLD DYNAMIC KNOWLEDGE GRAPHS
NodePiece, on account of its compositional representation, can be applied to dynamic real-world knowledge graphs where nodes are added and removed time. That is, training on graph snapshot we can obtain the embeddings of new nodes without re-computing and updating representations of every other node in the graph. This is valuable in settings where there are latency requirements such as many online services. For example, if a user creates an account on a social media service and begins liking content (represented
"like" edge the social network graph between the user and the content), it would be desirable to make future content recommendations rapidly reflect this new data without waiting for the next batched retraining to update the users embedding. In order to reduce latency the entire embedding matrix can be materialized and cached ahead of time, updating embeddings as new nodes and edges are added. The parameter efficiency and compositionality of NodePeice means that for large real-world graphs NodePiece subsumes what would before have been a complex system large-scale embedding framework like Pytorch- -iigr-p (Lerer et al. 2019). OOV embedding method (e.g.. FRAvg) and shallow embedding method (e.g., Rotatht.
17

---

Published as a conference paper at ICLR 2022
Table 14: Hyperparameters for out-of-sample link prediction experiments. The content largely identical to Table 10 only changed parameters are listed
NodePiece + DistMult
DDitMMult
Parameter
oFB15k-237
oYAGO 3-10
oFB15k-237
# Anchors, |
1000
10000
# Anchors per node, k Relational context, m Vocabulary dim, d
20
20
15
5
200
200
200
Batch size
256
256
1000
Learning rate Epochs
0.0005
0.0005
0.01
40
40
1000
NodePiece encoder
Transformer
Transformer
NodePiece encoder dim
512
512
NodePiece encoder layers
2
2
NodePiece encoder dropout
0.1
0.1
Loss function
Softplus
Softplus 5
Softplus
# Negative samples
Training time, hours
2
8
B LIMITATIONS AND FUTURE WORK
Our experimental results demonstrate the promise of using NodePeice significantly reduce the parameter complexity of node embeddings. While it is difficult to prove, we also hypothesize that the parameters required by NodePeice to maintain the same level of performance (as the graph scales) increase sublinearly according to the size of the graph. The intuition for this is twofold. First, the number of unique anchor combinations of size that can be encoded increases according to (1A1) (i.e. ({ randomly sampled - if the sampling is done via nearest neighbor anchor selection then the number of unique permutations is expected increase polynomially. Second, increasing the size of the graph will only require sublinear increase the number of anchors in order maintain the same average node-anchor distance. Although proving causality is difficult, believe that maintaining hashing uniqueness and node-anchor distances stable will be sufficient to maintain equivalent performance.
C ANCHOR SELECTION STRATEGIES
Here, we provide more details as to anchor configurations (k: nearest from total A anchors) and anchor distances. Recall that there exist several ways select the total of anchors A stated in Section 3.1 i.c., random or cnntrality-measure based. Then, i anchors per node can be chosen either as nearest (default NodePiece mode) or random anchors. Figure Ideuccts the effect of those strategies on the distribution of anchor distances (number of hops between target node and its anchors). We use the configurations used in the main experiments, i.e., 1000 anchors and 20 anchors node for FB 15k-237, and 500 anchors with 50 anchors node on WN18RR.
depicts
First, we observe that PPR, degree, and mixed (40% PPR. 40% degree, 20% random) strategies generally skew the distribution towards smaller anchor distances compared to random strategies. This fact supports the hypothesis that deterministic strategies improve the chances to find an anchor in closer (-hop neighborhood of target node. Second, varying the way of selecting & anchors per node between nearest (left column) and random (right column), we also observe the skew a distribution of anchor distances.
Next, we fix the anchor selection strategy to the mix, fix the number of anchors per node (50 for WN18RR and 20 for FB15k- 15k-2237), and vary total number of anchors A (50 1000 for WN18RR and 20 to 1000 for FB15k-237) along with the method of sampling anchors per node, i.c., nearest and random. Figure 4 shows that increasing the total number of anchors together with k nearest.
18

---

Published as a conference paper at ICLR 2022
(a) WN18RR
(b) FB15k-237
Figure 3: Distribution of anchor distances under various anchor selection strategies. Top-bottom: mixed, degree-based, PPR-based, random. For each dataset, left: selecting k nearest anchors, right: random anchors. (a) Selecting a fixed 500/50 configuration on WNISRR; (b) Selecting fixed 1000/20 configuration on FB 15k237. Generally, all strategies except random ones skew the distributions towards nearest anchors.
(a) WNI8RR
(b) FB 153
Figure 4: Distribution of anchor distances under the fixed mix anchor selection strategy when varying the total number of anchors A (50-1000 for WNISRR, 20-1000 for Fb15k-237). For each dataset, left column- lo nearest anchors, right- - h random anchors. On both graphs, increase in A with the nearest anchors always leads to shorter anchor distances.
anchors again skews the distribution of anchor distances towards smaller values and, hence, to higher probabilities of finding anchors in closer neighborhood of target node.
We would recommend using centrality-bast -bsse strategies to select A with nearest anchors per node anchor distances and probability of finding anchors in closer neighborhood are of higher importance.
19

---

Published as a conference paper at ICLR 2022
Finally, fix the anchor selection strategy mix, obtain nearest anchors per node, and under this setup study average anchor distances varying & the number of anchors per node various combinations of total anchors A. The results presented WN18RR) benefit more from increasing the number of anchors A, i.e., the delta between distances is much larger than that of dense FB15k-233 The difference in distances Figure might also explain the performance on Figure i.c., generally, smaller A/k configurations like 25/5 are inferior on sparser graphs but perform competitively on denser ones.
Figure S Figure|ssugeest suggest that sparser graphs (like
k
24
13
2.4
10
15
15
20
20
25
85
30
40
4.5
18
4.0
1.6
Total Anchers
(a) WN18RR
(b) FB15k-237
Figure 5: Average node-anchor distances when varying the total number of anchors from 25 to 1000 and & nearest anchors per node from 5 to 50. Note that sparser WN18RR the gap between min and max values much wider than denser FB 15k-2233. Signs of saturation suggest that further increasing A is not beneficial.
D EMBEDDING VISUALIZATIONS
To further study learned representations of anchors and capabilities of the encoder, we build tSNE and UMAP projections from subsamples FB15k-237 and WNISRR based on trained models from the transductive link prediction experiments (hyperparameters listed in Table
randomly sample 1000 entities (out of total 15K) and find their top- most common anchors. The anchor embeddings are extracted from the learned tensor while 1000 entity embeddings are obtained through the NodePiece encoder. Similarly for WN18RK we sample 4000 entities (out of total 40K) keeping their top- most common anchors. As we use the RotatE decoder that assumes entities and anchors are modeled complex space, we visualize their real parts (e.g.. first 100 dimensions out of 200).
For FB15k-231
Recalling that link prediction performance of NodePiece RotatE retains 80-90% the state art models performance, the results Fig. and Fig. demonstrate that (1) NodePiece encoder is able to reconstruct clusters of similar entities; (2) anchors are well-scattered among communities. Albeit entity embeddings are built composition of & anchors, it can be seen that all communities have "specialized" nearby anchors. On a higher level, common anchors tend to be well-scattered in FB15k-237 and Fig. 6 tend group together. However,
the space. Less common anchors, as thanks to the non-linear nature of the NodePiece encoder, resulting entity embeddings still form different clusters and communities not concentrated around one point. We believe this is the effect of a compositional encoder and plan to investigate this phenomenon further.
E TRANSDUCTIVE LINK PREDICTION RESULTS: MRR
In addition Figure that presents Hits @ 10, report variations of mean reciprocal rank (MRR) depending on combinations of and & on Figure [ from the same set of experiments. On sparser WN18RR, smaller A/k combinations like 25/5 50/10 struggle with more precise predictions like
20

---

Published as a conference paper at ICLR 2022
node Friity
Fafity
10p wnchor
Top 100 ancher
-30
-4-
2.5
5
15.0
bang
umap. X
Figure 6: tSNE (left) and UMAP (right) projections of 1000 encoded entities sampled randomly from 2B15k-237 and their top 100 most common anchors.
Entty
rode
12
Ertttty
rade
Top- anchor
1op-100 anchor
10
-00
-40
-20
10
tane
umap. X
Figure 7: iSNE (left) and UMAP (right) projections of 4000 encoded entities sampled randomly from WN18RR and their top 100 most common anchors.
Hits@1 which is captured by low values of MRR. Starting from 500/10, the WN18RR performance starts to saturate. On the other hand, on denser 153-233 the difference between minimum and maximum MRR is less than 4 points, and performance exhibits signs of saturation already 50/10.
F DATASETS CONSTRUCTION
NODE CLASSIFICATION; WD50K NC
The original WD50K (Galkin et al. 2020) contains triple-only KG version on which we base a new dataset for semi-supervised multi-class multi-label node classification. First, we remove all triples containing Wikidata properties 231 (instance of) and P279 (subclass of) as they already contain class information. We then remove nodes that became disconnected after removing those edges. Third, using SPARQL queries, for each remaining node in a graph, we extract a 3-hop class hierarchy of Wikidata classes and their superclasses. We only keep class labels that occur at least 50 times in the training set. Then, we sample 10% of nodes with labels for validation and 10% for test, and of remaining 80% sample set of nodes for the semi-supervised setup, i.e., keep only 5% and
21

---

Published as a conference paper at ICLR 2022
WNISRR
FB FB13k-237
0.26
0.4
A=100
A=500
0.3
0.24
A=1000
MRR
MRR
0.2
0.22
0.2
20
20
30
40
Anchors per node
Anchors per node
Figure 8: Combinations of total anchors and anchors per node. Denser FB 15k-233 saturates faster on smaller A while sparse WNISRR saturates at around 500 anchors. MRR metric captures all ranks. Note that performance gap on 2513--237 is very small indicating that saturation has occurred already with small anchor configurations.
10% of those nodes. The resulting graph has 46k nodes, 526 distinct relation types. and 465 class labels.
F.2 OUF-OF-SAMPLE LINK PREDICTION: OYAGO 3-10
For sampling the out-of -aamle version a bigger YAGO 3-10 we largely follow the same original procedure described in Section 4 of (Albooyeh al. 2020). We first merge the train, validation and test triples from the original dataset for transductive link prediction. Then, from all entities appearing in at least triples, we randomly sample 5% of nodes to be the out-of-sample entities for validation and 5% for test. All triples containing the out-of-sample entities on subject or object positions are put into validation or test, respectively, edges that connect an unseen entity with the seen graph.
G NODE CLASSIFICATION: TRAINING CURVES
Figure 9 depicts train and validation values of Hard Accuracy and PRC-AUC metrics for all the compared models on WD50K NC with 5% of labeled nodes. The NodePiece model has only 50 total anchors with 10 nearest anchors per node, and 5 unique relation types in the relational context. The performance on the dataset with 10% of nodes is almost the same, so we report the charts only on 5% dataset. By the generalization gap we understand the delta between training and validation values.
The MLP baseline quickly overfits but fails to generalize on the validation. The generalization gap of CompGCN is smaller compared to MLP but is still significant, i.e., validation performance is 2-3x x smaller than train. Finally, the NodePicce-enabled model has the smallest generalization gaps, especially along the Hard Accuracy metric where the validation performance is very close to that of train. Similarly, the gap on PRC-AUC is smaller than 10 points.
As shown in the ablation study Table 6 appears that explicit node embeddings do not contribute to the classification performance. Hence, the baseline models tend to be overparameterized where learnable node embeddings add noise, while the NodePiece model has only few anchors (or no an- chors at all when using only the relational context), much fewer parameters, and therefore generalizes better. This hypothesis also explains the observation that the node classification performance does not improve when increasing A/k anchor configurations.
H PROOFS
Proposition 2. The nearest-anchor encoder with (lAI) anchors and (m)) subsampled relations, can be considered a π R-SGD approximation of (k + [m]) -ary Janossy pooling with a canonical ordering induced by the anchor distances.
22

---

Published as a conference paper at ICLR 2022
10-
10-
08
FRCHAUC
hard
04
02-
02-
010
NodePlece CompGCN train
CompGCN MLP NodePPecc-CompoCN
CompGCN
Figure 9: Generalization gap WDS0K (5% labeled nodes). NodePiece-based model has observably smaller generalization gaps compared to the baselines.
Proof.
We begin by providing the definition of Janossy pooling as it was presented in the original paper Murphy al. (2019).
Definition (Janossy pooling). Let HD be the union of all anchors and relations. Consider a function 7 x H² Rd + F on variable-length but finite sequences h, parameterized by O(f) E IR4, d > 0. A permutation-invaree function f J:N: N.N& x H x Rd + E is the Janossy function associated with f if
h: (1b,h:0(/) = h
Σ TETTIN
where Ipp is the set of all permutations of the integers 1 to [h], and b represents a particular reordering of the elements of sequence h according to E Upp- We refer the operation used to construct J from f as Janossy pooling.
While Janossy pooling provides simple approach to construct cormuuattioninvaaiii functions from arbitrary permutation sensitive functions, computationally intractable due to the need to sum over all computations. Three general strategies proposed under this framework to overcome this combinatorial challenge: canonical orderings, k-ary Janossy pooling, and --SGD approximations.
A very effective way of reducing the complexity is to constrain the permutations to a canonical ordering that is independent of a specific adjacency matrix ordering over a given graph. More precisely, defines function CANONICAL H + H such that CANONICAL(b) CANONICAL(b...d VvT E [h] and only considers functions f based the composition f
CANONICAL (Murphy et al. 2019). In the case of NodePiece ordering for the anchors according to their distance to the target node. Assuming that the number of relations is fixed grows slow rate throughout the life-cycle of graph ordering for relations as a canonical ordering for the relational context. However, since anchors can be equidistant such canonical ordering does fully satisfy permutation invariance. We propose trivial relaxation of the original definition of canonical orderings simply requiring that an ordering greatly reduce the number of unique permutations since in practice exact canonical ordering is rarely feasible. Specifically, | |CANONICAL VYT E H << (b, VT E 1|
able to define this
define arbitrary
To further reduce the number of permutations we can truncate our ordered sequence h. This is known as k-ary Janossy pooling pooling (Definition 2 and is implicitly performed by the NodePeice algorithm by varying the anchor per node parameter, k. and the size of the relational context. mm).
Definition (k-ary Janossy pooling). Fix le E N. For any sequence h. define 4e (h) as its projection length l sequence; in particular, if h| 2 k, we keep the first k elements. Then, k-ary
23

---

Published as a conference paper at ICLR 2022
Table 15: Relation prediction results. [V] denotes vocabulary size (anchors + relations).
FB 133-
WNI8RR
YAGO 3-10
[V]
MRR
H@ 10
[V]
MRR
H@ 10
[V
MRR
H@ 10
RotatE
15k 0.5k
0.905
0.979
40k + 22
0.774
0.897
123k + 74
0.909
0.992
NodePiece RotatE
1k + 0.5k
0,874
0.971
500 + 22
0.761
0.985
10k 74
0.951
0.997
no rel. context
Ik + 0.5k
0.876
0.968
500 + 22
0.541
0.958
10k + 74
0.898
0.993
no distances
1k + 0.5k
0.877
0.970
500 +
0.746
0,975
10k + 74
0.943
0,997
no anchors, rels only
0 0.5k
0.873
0.971
0
0.545
0.947
0+
0.951
0.998
permutation-inaarinn Janossy function f given by
J(h), h: 05) h
Σ xEll
L(bb),a(h>);;00
(4)
Since an imperfect truncated canonical ordering may still result in a potentially intractable number of permutations, we use permutation sampling also known as T-SGD to learn arbitrary functions that approximate (A: + |m >-ayy Janossy pooling. This is done by randomly ordering anchors that are equidistant resulting in uniform sampling of possible permutations during training and evaluation. For more details on the formal definition of --SG we point the reader to the original paper (Murphy et al. 2019).
RELATION PREDICTION
Setup. We conduct the relation prediction experiment on the same FB15k-237, WNISRR, and YAGO 3-10 datasets. While link prediction deals with entities, the relation prediction model has to rank correct relation given a (head, ?, tail) query. We report MRR and Hits@ 10 in the filtered setting as evaluation metrics. Similar to the link prediction configuration, we use NodePiece + 2-layer MLP and compare against RotatE of the same total parameter count.
Discussion.
The reported results (Table 15 demonstrate competitive performance of NodePiece- based models with reduced vocabulary sizes bringing more than 97% Hits@ 10 across graphs of different sizes. In the case of WN18RR and YAGO 3-10, NodePiece models with fewer anchors even slightly improve the accuracy upon the shallow embedding baseline. The ablation study suggests that on dense graphs with a reasonable amount of unique relations having explicit learnable node embeddings might not be needed at all for this task. That is, we see that on FB15k-237 and YAGO 3-10 the NodePiece hashes comprised only of the relational context deliver the same performance without any performance drop confirming the findings from the previous experiment.
J INDUCTIVE LINK PREDICTION
Setup. Nodes in the inference graphs do not have any associated feature vectors which makes this benchmark very relevant for graph representation learning. Importantly, the set of relation types in the inference graphs is subset of those seen in the training set. Since the relation embedding matrix can be learned on the training graph, we therefore have a uniform method for constructing node representations both on seen and unseen graphs. As an encoder we try MLP and Transformer.
Evaluation Protocol. Following the original work (Teru et al. 2020). we employ a filtered setting and rank each triple against random negative triples reporting the @its@ 10 metrie. This setup is motivated by computational complexity of GralL inference time, while NodePiece CompGCN is as fast in the inductive inference as the transductive regime reported in other experiments.
Discussion. For each KG, there are 4 splits of increasing size of train and inference nodes and edges. The empirical results on this spectrum of various sizes demonstrates interesting scalability properties of NodePiece in inductive settings. Without anchor nodes, the NodePiece vocabulary size is independent of the number of nodes and edges, depending only on the number of relation types. On dense relation-rich graphs such vocabulary is enough to yield very competitive performance.
24

---

Published as a conference paper at ICLR 2022
Table 16: Hyperparameters for inductive link prediction experiments. Entries are shared among splits of each graph if not particularly specified. V1 I V2 I V3 V4 otherwise.
Parameter
FB 153-237
WNISRR
NELL-995
# Anchors, |A|
# Anchors per node, & Relational context, m Vocabulary dim, d
12
4 1413
4161416
100
100
100
Batch size
512
512
512
Learning rate
0.0001
0.0001
0.0001
Num negatives
32
32
32
Epochs
2500 V1 2000 rest
590 2000 210 2000
2000
NodePiece encoder
MLP
MIPP
MLP MLP MLP Tri 200
NodePicce encoder dim
200
200
NodePiece encoder layers
2
2
NodePiece encoder dropout
0.1
0.1
0.1
CompGCN layers
3
6161610 10 yes 0.1
3 3141313
CompGCN attention
yes 0.1
yes 0.2 0.1 10.1 1 NSSAL 15 I 20 130 20
CompGCN dropout
Loss function
NSSAL
NSSAL
Margin
25 15
15 125
15 15 5 20
Training time, hours
2 1 41 16 19
11 18 141 10
615 18 18
UNIQUENESS OF NODE HASHES K
NodePiece represents nodes as a sequence of tokens and a natural question in this context is how unique such sequences can be in light of different anchor selection and tokenization strategies.
Assuming the input graph is a single connected component, when sampling |A| total anchors and selecting randomly i anchors per node, the number of possible hash combinations is bounded by (l2)) ) In this scenario, uniqueness of hashes achieved by having this number bigger than the number N of nodes in graph, (la)) > N, and this happens with high probability for any reasonably large |A], eg. (50) encodes about 4.7 1003 combinations which covers all existing public KGs combined.
In the deterministic selection of nearest anchors per node we do not have such guarantees. Never- theless, additional sequences of relational contexts and anchor distances help obtain more unique hashes. Collisions are possible in highly regular graphs like Wordnet, but hal-world KGs like Wikidata and DBpedia do not exhibit such a regular structure. Similar homonyms whose meaning depends on the surrounding context in a sentence, we hypothesize that adding message passing layers (that can be seen as encoding of neighboring context for given node) on top of NodePiece hashes might further improve the diversity of node representations. That said, the future work research agenda might include proving tighter theoretical bounds on hashes uniqueness and developing new anchor sampling and tokenization strategies.
25


Reviews:
[{"review_id": "ogEps-UH_Mg", "reviewer": "Reviewer_X7aq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strength\nFinding new deep-learning architectures and strategies that are more efficient and usable with lower computational resources without sacrificing performance is a noble goal, and it can improve the actual applicability of neural knowledge-graph based methods. The paper considers a number of trade-offs and heuristics for constructing compositional-vertex embeddings and presents either SOTA or close to the SOTA results on a number of benchmarks. I believe that this paper will be much appreciated by practicioners.\n\n### Weakness\n1. The paper repeatedly claims the uniqueness of the hashes: based on my reading of the paper none of the hashing strategies considered in the paper can guarantee that two distinct nodes will always have distinct hashes. However the paper claims that the hashes are unique in multiple paragraphs.\n2. Claim of sub-linear vocabulary size: This may be a pedantic objection, but based on my reading of the results in figure 2, and table 4 , the model requires roughly 10% of the nodes. The experiment in section 4.1.1 does suggest that using only 1% of the nodes was sufficient for encoding the 2.5M subset of wikipedia, but I would have preferred that the authors use a larger set of 25M nodes or all 100M of them before making claims of sub-linear growth in parameters. It is useful to maintain the distinction between linear with a small constant factor and sub-linear growth and I don't see compelling evidence for the latter.\n", "summary_of_the_paper": "Conventional methods for learning knowledge graph embeddings often learn separate embeddings for each vertex in a knowledge graph. This paper presents empirical results about a new heuristic for encoding the vertices in a knowledge graph which drastically reduces the number of parameters in a graph, and allows better handling of novel vertices, whose connections were not known at the time of learning/training.\n\n  The basic approach is to encode each vertex through a sketch of its neighborhood. Specifically the paper heuristically selects a subset of training vertices, called \"anchors\". Each vertex is represented by its closest k-anchor vertices, and the types of the outgoing edges starting from the vertex.\n\n  Individual embedding vectors are learnt only for the anchor vertices, and at inference time, the embedding of a novel vertex is composed from the closest k-anchor vertex embeddings using some neural network layer such as an MLP or a transformer.\n", "summary_of_the_review": "The paper presents a novel approach for embedding large knowledge graphs using a small number of parameters. The empirical results strongly support the usefulness of the proposed approach and I believe that even though this won't be the final word on creating compositional representations of KG vertices, but it will be appreciated by ICLR readers.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EhIvputWoj2", "reviewer": "Reviewer_KuBz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper is clearly written and the NodePiece approach is well-motivated. The diverse range of experiments is a strong point of the work, as they demonstrate the usefulness of NodePiece for a range of important tasks including link prediction, relation prediction, and node classification, including in the inductive setting.\n\nThe primary shortcoming of the work is the limited number of comparisons to alternative methods in the experiments. In each case, only one or two existing methods are compared to NodePiece in terms of both performance and parameter cost, although the baselines do seem to be methods that are competitive with state-of-the-art approaches for each task. The ablation analyses performed in each setting could also have been limited to a few relevant tasks, in order to be able to include results that explore other design choices such as how sampling strategies for anchor nodes and outgoing relations affect downstream task performance (some of this analysis seems to have been moved to the appendix).", "summary_of_the_paper": "This paper presents NodePiece, a method inspired by subword embeddings in NLP that is designed for constructing compositional representations of entities in a knowledge graph using a fixed-size entity and relation vocabulary. This allows for learning and storing entity representations with a number of parameters that does not scale with the size of the knowledge graph, as well as being able to construct representations for unseen entities. The method uses a vocabulary that combines relation embeddings for all relations in the knowledge graph with a limited set of anchor entities, typically much fewer than the total number of entities. To construct an entity representation, a subset of that entity's nearest neighbor anchor entities (along with embeddings of the lengths of the shortest paths to those entities) are combined with a sampled set of adjacent relation embeddings and passed through an encoder (either an MLP or a Transformer) to output a fixed-size embedding. These compositional entity representations can then be used in classicial knowledge graph tasks such as link prediction, relation prediction, and node classification. Across all of these tasks and a range of datasets, NodePiece representations are shown to achieve a large fraction of the performance of strong baselines and in some cases even outperform them, all while using a fraction of their parameter count. Ablation analyses show that increasing the total number of anchors and number of anchors per entity improves performance up to a saturation point, and that in some cases a vocabulary of relations without anchor entities is sufficient (or even preferable) for constructing well-performing entity representations for certain downstream tasks.", "summary_of_the_review": "Though the experiments could include more baselines and further analysis of how design decisions for NodePiece affect task performance, the current set of results seems to sufficiently demonstrate the utility and versatility of the method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "6VKHDISCnNp", "reviewer": "Reviewer_2qcD", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "More specifically the proposed method (NodePiece)  first (randomly) selects a fraction of all entities as anchors, which have learnable embeddings. Then the representation of a target entity consists of a concatenation of its nearest (sampled) anchors' embeddings (shifted by distance embeddings) and embeddings of (sampled) relations which this entity possesses. The concatenated representation is transformed by either a MLP (for model quality) or Transformer (for model compactness).\n\nFor link prediction, MRR and H@10 for NodePiece is much worse than RotatE on small and bigger KGs. On a large scale KG (OGB WikiKG 2) of 2.5M nodes NodePiece improves a full embedding based baseline (AutoSF) in both model size and MRR.\n\nFor node classification, NodePiece is competitive to an existing approach (RotatE) with more compact models.\n\nFor relation prediction, NodePiece is significantly better than previous approach (CompGCN) on WD50K with either 5% or 10% labeled data. However, under the out-of-sample link prediction setting, NodePiece is significantly worse than the previous approach oDistMult-ERAvg on oFB15k-237.   The comparison on oYAGO 3-10 (117k) was not achieved due to memory issues.\n\n\nOverall this work represents a promising direction with some promising results. However, the proposed approach seems to be flawed and shows degraded quality in some of the situations.  It seems that the proposed randomized anchor selection can lead to suboptimal representation. Since some of the key nodes (e.g., entity types) might be missed. It is probably better to have a learning based approach for anchor selection.\n\nMinor issues:\n\nEq 1 and Eq 2: why are they called \"hashes\"? these representations are just learnable embeddings right?\n\nIs it a typo for \"injective encoder function enc\"? I am not sure that it is possible to have injective functions  for R(k+m)×d → Rd.\n\nDetail is needed on how the proposed node representations are used for link predictions. Do we concatenate the presentation of two nodes?\n\nDetail is needed on how  the link prediction metrics are calculated. \nWhat negative triples are we ranking against? How are the true triples corrupted? \n\n", "summary_of_the_paper": "Previous KG representation learning approaches learn an embedding for each entity in KG, which leads to a lot of parameters in the models. This work aims to avoid this problem by dynamically generating the embedding of an entity based on its local neighborhood. ", "summary_of_the_review": "A promising direction with mixed results.\n\nAfter author response: I am satisfied with the answers to all my questions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "11JOonQYlJF", "reviewer": "Reviewer_CpaB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n1. Experiment on a large-scale link prediction dataset (Table 5) shows encouraging results on the effectiveness of NodePiece.\n\nWeakness:\n1) The paper has only focused on graphs with multi-type relations (knowledge graphs). If the main idea of NodePiece is to compress embeddings, why not test it on graphs with only one type of relationship (e.g., large citation networks)? It would be great to see if such heuristic apply to single-type datasets and whether it could help methods such as transductive unsupervised embedding learners (e.g., DeepWalk).  \n\n2) When NodePiece shows improvement over baselines, i.e., node classification and relation classification (Tables 6-7), relational context alone does well too. The fact that anchor nodes are not useful in these tasks is probably an indicator of the triviality of the tasks. – Based on this, I doubt if NodePiece will do well on single-type relation graphs (first weakness).\n\n3) The paper emphasizes that the goal of NodePiece is not to improve performance of the baselines but rather highlight efficiency in memory and maintaining a reasonable accuracy. However, I think the paper doesn’t do justice in explaining the experimental observations. For instance, it is not clear why increasing the anchor nodes does not improve the performance beyond a point (saturation happens). That is, by increasing the number of parameters and memory, shouldn’t the performance also get better? Analogously, what is special about WikiKG dataset that leads to such good result?\n\nQuestion:\n1. What is the reason to create inverse edges? It is mentioned that it is due to maintaining reachability and the balancing of in and out degrees. Could you please elaborate?\n\n2. Did any of the experiments include node features?\n\n", "summary_of_the_paper": "This paper presents NodePiece, a method to scale up GNNs by means of removing their dependence on individual node embeddings which grow linearly in size and are inefficient in huge graphs. The method uses a set of anchor nodes, which are picked from the graph itself, for the NodePiece representations. Concretely, NodePiece embedding is derived by the embeddings of the closest anchor nodes and the hop-based distance to these nodes which are also represented by vectors. – the maximum distance between two nodes in a graph is Diameter(G), so the number of distance/position embeddings is Diameter(G). Additionally, NodePiece is augmented by a sample of embeddings of the relationship types the node is involved in. Apart from induced efficiency, NodePiece can be especially useful in inductive learning where an unseen node’s embedding can be created through the anchor nodes.", "summary_of_the_review": "The paper is inspired by the use of subwords in NLP and aims to leverage similar techniques for GNNs. Evidently, the proposed method is not behaving like subwords, as NodePiece could potentially degrade the performance a lot. There are missing experiments, and the paper has weaknesses in its analysis of the performance of NodePiece, i.e., we don't know when it works and when it does not.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a technique for compositionally constructing embeddings for nodes in knowledge graphs, hence reducing the memory requirements as well as allowing inductive learning. The reviewers find the direction promising and the approach novel and well-motivated. There were some concerns about the experiment results — Reviewer KuBz suggests including more baselines, Reviewer CpaB suggests trying NodePiece on single-relation graphs and Reviewer 2qcD notes that NodePiece lags behind the other approaches on some tasks. Most of these concerns seem to have been addressed in the author response and I tend to agree with the authors that single-relation graphs are out of the scope of this work. Reviewer X7aq also raised a concern about the claims made regarding (i) uniqueness of the hashes and (ii) sub-linearity of the approach. It is good to see that claim (ii) has been removed, but (i) is still present in many places — it would be good to add a discussion about why the hashes are highly likely to be unique in the final version.
Decision: Accept (Poster)