Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.
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.

The 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_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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: Strength:

1. Experiment on a large-scale link prediction dataset (Table 5) shows encouraging results on the effectiveness of NodePiece.

Weakness:
1) 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).  

2) 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).

3) 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?

Question:
1. 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?

2. Did any of the experiments include node features?


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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 
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).

For 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.

For node classification, NodePiece is competitive to an existing approach (RotatE) with more compact models.

For 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.


Overall 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.

Minor issues:

Eq 1 and Eq 2: why are they called "hashes"? these representations are just learnable embeddings right?

Is 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.

Detail is needed on how the proposed node representations are used for link predictions. Do we concatenate the presentation of two nodes?

Detail is needed on how  the link prediction metrics are calculated. 
What negative triples are we ranking against? How are the true triples corrupted? 


summary_of_the_review: A promising direction with mixed results.

After author response: I am satisfied with the answers to all my questions.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.

  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.

  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.

main_review: ### Strength
Finding 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.

### Weakness
1. 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.
2. 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.

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.
review_title: null

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)